首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 93 毫秒
1.
车辆路径问题(Vehicle Routing Problem,VRP)是组合优化问题中一个典型的NP难题.蝙蝠算法(Bat Algorithm,BA)是一种新型的智能优化算法,尚未被应用到求解VRP问题中去.根据物流配送中VRP问题的数学模型及其具体特征,设计了求解VRP问题的蝙蝠算法,并通过仿真实例和与其他算法进行比较的方式验证了蝙蝠算法求解VRP问题的有效性与可行性.  相似文献   

2.
带集货和配送的多站点VRP优化算法研究   总被引:2,自引:0,他引:2  
带集货和配送的多站点车辆路线问题(M DVRPPD)是经典VRP的扩展,是多个站点和若干客户既有需求又有供给的VRP问题.研究了该问题的模型并提出了求解该问题的多阶段启发式算法,即先用临界客户的思想把多站点转换为单一站点问题,再使用基于SFC的分组方法来构造初始解,并运用3-opt算法优化回路,之后采用插入算法改善解的可行性,从而得到最终优化解.最后通过实例计算证明了该方法解决M DVRPPD问题的实用可行性和科学有效性.  相似文献   

3.
根据车辆路径问题的数学模型,分析了它的具体特征,从而对BA的操作算子又进行了重新定义,设计了求解VRP问题的离散蝙蝠算法,并通过实例测试将离散蝙蝠算法与其他算法进行比较,验证了该算法求解VRP问题的有效性与可行性.  相似文献   

4.
针对离散蝴蝶优化算法求解TSP问题时精度低和收敛速度慢等问题,提出一种改进离散蝴蝶优化算法.为了提升搜索效率,利用贪婪机制初始化种群,同时结合2-opt算子、改进的2-opt算子和模拟退火等策略来提高寻优能力.通过标准TSPLIB数据库中几十个实例仿真实验,并与一些经典、新型的智能算法比较,结果表明提出的算法在寻优能力和鲁棒性方面表现优越.  相似文献   

5.
研究了一般意义下同时送取货的车辆路径VRPSPD问题,建立VRPSPD的整数规划模型.考虑到VRPSPD车辆不断变化的负载量,使得问题难以求解,设计了一种将蚁群系统(ACS)与2-opt方法相结合的启发式算法.通过在蚁群系统(ACS)中引入候选集合的策略,将启发因子设为目标函数值,同时利用2-opt算法的思想得到适用于VRPSPD的2-opt方法,使得设计的启发式算法对于求解VRPSPD是有效的.最后,实例运算的结果也证明了算法是一种较好的算法,能够得到满意的解.  相似文献   

6.
周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。  相似文献   

7.
车辆路径问题(Vehicle Routing Problem,VRP)在物流与供应链领域是一个非常有研究价值的NP-Hard问题.蝙蝠算法(Bat Algorithm,BA)是一种新兴的智能优化算法,有着广阔的应用前景.然而它不能直接用于求解离散问题,并且如同大多数智能优化算法一样,容易陷入局部最优,后期收敛速度慢.本文针对VRP问题的具体特性,重新定义了蝙蝠的编码方式并利用GRASP启发式算法生成蝙蝠算法初始种群来改进算法,然后应用于求解VRP问题.  相似文献   

8.
针对当前算法在求解带时间窗车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)时存在精度、效率方面的不足,提出一种改进的离散花朵授粉算法.算法在基本花朵授粉算法的基础上进行离散化,使其适合求解带时间窗车辆路径问题,重新定义花朵授粉算子操作.为了提高求解精度和效率,设计了随机插入、路径内的2-opt、交换和逆序操作,为了增加种群间信息的交互,结合改进的遗传算子.通过11个测试算例表明,改进的离散花朵授粉算法在求解VRPTW是行之有效的,与文献中其他算法比较,算法在精度、效率和鲁棒性方面具有优势.  相似文献   

9.
针对冷链物流配送的特殊性,探索冷链物流车辆路径问题(VRP)优化方案.首先,在保证货物不超载的条件下,建立基于时间和品质因素的顾客满意度约束的多配送中心VRP(MDVRP)模型;其次,采用重心分区法和改进的精英单亲遗传算法,求解顾客在配送中心的分配,确定配送车辆数以及顾客服务次序;最后,用Matlab工具编程对模型进行求解分析.结果表明构建基于满意度的冷链物流MDVRP模型更适合冷链物流配送最优路径选择,并且改进单亲遗传算法能够有效求解这类问题.  相似文献   

10.
随机需求的车辆路线问题的新模型   总被引:7,自引:0,他引:7  
倪勤  袁健  刘晋 《运筹与管理》2001,10(3):74-79
本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。  相似文献   

11.
Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.  相似文献   

12.
This paper introduces a new class of problem, the disrupted vehicle routing problem (VRP), which deals with the disruptions that occur at the execution stage of a VRP plan. The paper then focuses on one type of such problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs. Two Tabu Search algorithms are developed to solve the problem and are assessed in relation to an exact algorithm. A set of test problems has been generated and computational results from experiments using the heuristic algorithms are presented.  相似文献   

13.
This paper presents a new heuristic algorithm for the vehicle routing problem (VRP) which makes use of Lagrangean relaxation to transform the VRP into a modified m-traveling salesman problem. Application of the proposed algorithm to test problems from the literature has produced new best-known solutions.  相似文献   

14.
The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. This paper proposes an improved ant colony optimization (IACO), which possesses a new strategy to update the increased pheromone, called ant-weight strategy, and a mutation operation, to solve VRP. The computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches.  相似文献   

15.
煤矿物资多车型配送的改进遗传算法求解   总被引:1,自引:0,他引:1  
首先根据郑州煤电物资供销有限公司的实际情况建立单车场多车型车辆路径问题的模型,在此模型的基础上,用本文提出的改进遗传算法(IGA)对其求解,最后通过和传统的启发式算法(CHA)、扫描法(SA)的求解从配送费用、配送车辆数和运算时间上进行了综合比较,得出IGA算法求得的总运输费用最低,SA算法次之,CHA算法最高;但从所需参与配送的车辆数目来看,CHA求得的最好解所需的车辆数最少,其次是SA,IGA最多;在平均计算时间上,CHA的优势最明显,仅为SA的,IGA的.  相似文献   

16.
Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.  相似文献   

17.
We examine neighborhood structures for heuristic search applicable to a general class of vehicle routing problems (VRPs). Our methodology utilizes a cyclic-order solution encoding, which maps a permutation of the customer set to a collection of many possible VRP solutions. We identify the best VRP solution in this collection via a polynomial-time algorithm from the literature. We design neighborhoods to search the space of cyclic orders. Utilizing a simulated annealing framework, we demonstrate the potential of cyclic-order neighborhoods to facilitate the discovery of high quality a priori solutions for the vehicle routing problem with stochastic demand (VRPSD). Without tailoring our solution procedure to this specific routing problem, we are able to match 16 of 19 known optimal VRPSD solutions. We also propose an updating procedure to evaluate the neighbors of a current solution and demonstrate its ability to reduce the computational expense of our approach.  相似文献   

18.
This paper discusses neighborhood search algorithms where the size of the neighborhood is very large” with respect to the size of the input data. We concentrate on such a very large scale neighborhood (VLSN) search technique based on compounding independent moves (CIM) such as 2-opts, swaps, and insertions. We present a systematic way of creating and searching CIM neighborhoods for routing problems with side constraints. For such problems, the exact search of the CIM neighborhood becomes NP-hard. We introduce a multi-label shortest path algorithm for searching these neighborhoods heuristically. Results of a computational study on the vehicle routing problem with capacity and distance restrictions shows that CIM algorithms are very competitive approaches for solving vehicle routing problems. Overall, the solutions generated by the CIM algorithm have the best performance among the current solution methodologies in terms of percentage deviation from the best-known solutions for large-scale capacitated VRP instances.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号