车辆路径问题及其优化算法研究综述.docx

《车辆路径问题及其优化算法研究综述.docx》由会员分享，可在线阅读，更多相关《车辆路径问题及其优化算法研究综述.docx（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、车辆路径问题及其优化算法研究综述 打开文本图片集 摘 要：车辆路径问题是物流管理与运输组织优化中的核心问题，是运筹学中一类经典的组合优化问题。文章比较系统地总结了常见的VRP问题的分类和基本的数学模型，并通过查阅学者们的探讨状况，总结了求解VRP问题常用和高效的启发式算法及相应的探讨现状；最终总结了探讨存在的问题，并对今后VRP问题的探讨和求解方法进行了展望。 关键词：车辆路径问题；启发式算法；优化 中图分类号：U116.2 文献标识码：A Abstract： Vehicle routing problem is the core problem in logistics management

2、 and in the organization and optimization of transportation， and is a classic combinatorial optimization problem in operations research. This article systematically summarized the common classifications and the basic model of VRP problems. And through referring to scholars research situation， summar

3、ized the commonly used and efficient heuristic algorithms of solving VRP problems and the present situation of the corresponding research. Finally， summarized the problems in the research of VRP problems and discussed the future research and the solving methods for VRP problems. Key words： vehicle r

4、outing problem； heuristic algorithm； optimization 0 引 言 随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题是制约物流行业发展的一个关键要素，其探讨也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满意肯定的约束条件下，通过对一系列收货点与发货点客户合理支配行车路途，在客户的需求得到满意的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由Dantzig和Ramser1于195

5、9年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学中一类经典的组合优化问题，是典型的NP-难题。 企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效削减车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。VRP作为物流系统优化环节中关键的一环，其探讨成果已经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化探讨具有很好的现实意义。 1 车辆路径问题的分类与基本模型 VRP的构成要素通常包括车辆、客户点、货物、配送中心、道路网络、目标函数和约束条件等，依据侧重

6、点的不同，VRP可以分为不同的类型。依据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；依据任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；依据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；依据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；依据客户对货物接收与发送有无时间窗约束可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；依据客户需求是否可拆分可分为需求可拆分车辆路径问题和需求不行拆分车辆路径问题；依据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；依据配送与取货完成后车辆是否须要返回动身点可分为开放式车辆路径问题和闭合

7、式车辆路径问题；还可以将上述两个或更多约束条件结合起来，构成一些更困难的车辆路径问题。 由于VRP的约束条件不同引起了其分类多种多样，而不同类型的VRP其模型构造及求解算法有很大差别。VRP的一般数学模型为： 在上述模型中，式表示目标函数，式表示约束条件。其他VRP模型大致都是在此模型的基础上依据约束条件完善形成的。 2 VRP的求解算法与探讨现状 VRP的求解方法，基本上可分为精确算法和启发式算法两大类。由于精确算法的计算难度与计算量随着客户点的增多呈指数级增加，在实际中应用范围有限，而启发式算法则具有全局搜寻实力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分探讨者们主要

8、把精力集中在如何构造高质量的启发式算法上，本文也主要探讨一些近年来探讨比较多的启发式优化算法。针对VRP问题目前已提出了大量的启发式算法，其中探讨较多的主要包括以下算法： 2.1 遗传算法 GA是一种通过模拟生物进化过程来搜寻最优解的方法，该方法通过对群体进行选择、交叉和变异等操作，产生代表新的解集的种群，依据个体适应度大小选择个体，通过迭代逐步使群体进化到近似最优解状态。但是该算法具有搜寻速度慢、易早熟、总体可行解质量不高等缺点。 采纳遗传算法探讨VRP问题的探讨现状包括：蒋波2设计了遗传算法求解以配送总成本最小为目标函数和带有惩处函数的VRPTW模型；赵辰3基于遗传算法求解了从生产中心到仓

9、库之间的路径优化问题，设计了配送路径优化决策；张群和颜瑞4建立了多配送中心、多车型车辆路径问题混合模型，并采纳一种新的模糊遗传算法求解该问题。 2.2 模拟退火算法 SA同禁忌搜寻算法一样，也属于局部搜素算法，但是模拟退火算法是仿照金属加工中退火的过程，通过一个温度函数作为目标函数，使其趋于最小值，是一种基于概率的算法。 采纳模拟退火算法探讨VRP问题的探讨现状包括：郎茂祥5探讨了装卸混合车辆路径问题，并构造了模拟退火算法求解该问题；穆东等6提出了一种并行模拟退火算法，并将该算法的应用领域扩展到其他车辆路径问题和组合优化问题；魏江宁和夏唐斌7以模拟退火算法为基础，探讨了单个集散点与多个客户之间

10、的运输问题；Mirabi和Fatemi Ghomi等8提出了一种基于模拟退火思想的三步启发式算法求解最小化配送时间的多配送中心VRP模型。 2.3 蚁群算法 蚁群算法是人们受蚂蚁可以快速找到食物的自然现象启发提出的。蚁群算法所建立的机制，主要包括蚂蚁的记忆、蚂蚁利用信息素进行交互通信及蚂蚁的集群活动三个方面。单个蚂蚁缺乏智能，但整个蚁群则表现为一种有效的智能行为。通过这种群体智能行为建立的路径选择机制可使蚁群算法的搜寻向最优解靠近。 采纳蚁群算法探讨VRP问题的探讨现状包括：马建华等9探讨了基于动态规划方法的多车场最快完成车辆路径问题的变异蚁群算法；辛颖10通过对MMAS蚁群算法进行了三种策略

11、的改造，指出蚁群算法可以找到相对较好的解和很强的鲁棒性；陈迎欣11针对蚁群算法的缺点，分别对信息素更新策略、启发因子进行改进，引入搜寻热区机制，有效解决车辆路径优化问题；段征宇等12通过最小成本的最邻近法生成蚁群算法和局部搜寻操作设计了一种求解TDVRP问题的改进蚁群算法。 2.4 粒子群算法 PSO算法是通过对鸟群觅食行为的探讨而得出的一种群体并行优化算法，它从随机解动身，通过迭代找寻最优解。蚁群算法具有简单实现、收敛速度快、精度高等优点，在多种优化问题上均取得了较好的效果。但是由于PSO算法是通过粒子之间的相互作用来找寻最优解，缺乏像遗传算法那样的变异机制，因而PSO算法简单陷入局部最优。

12、 采纳粒子群算法探讨VRP问题的探讨现状包括：马炫等13提出了一种基于粒子交换原理的整数粒子更新方法求解有时间窗约束的车辆路径问题；吴耀华和张念志14以处理集货或送货非满载带时间窗车辆路径优化问题为背景，提出了带自调整机制的局部近邻粒子群算法解决VRP问题。 2.5 蝙蝠算法 蝙蝠算法是剑桥高校学者Yang15于2022年提出的一种新型群智能进化算法，模拟自然界中蝙蝠通过超声波搜寻、捕食猎物的生物学特性，是一种基于种群的随机寻优算法。截至目前，蝙蝠算法主要用于求解连续域的函数优化问题，只有少数学者将其用来求解离散型问题，具有很好的探讨前景。 采纳蝙蝠算法探讨VRP问题的探讨现状包括：马祥丽等1

13、6将蝙蝠算法应用于求解VRP问题，在蝙蝠速度更新公式中引入了惯性权重，对基本蝙蝠算法进行了改进，克服了基本蝙蝠算法的不足之处；马祥丽等16针对VRPTW问题的详细特性重新定义了蝙蝠算法的操作算子，设计了求解VRPTW 问题的蝙蝠算法，并采纳罚函数的方式对目标函数进行了简化求解。 3 总结与展望 车辆路径问题由于约束条件的不同其分类多种多样，数学模型与求解算法也层出不穷。本文总结了近几年一些相关学者对VRP问题的探讨和求解算法，通过较为系统地总结VRP问题，本文总结出以下当前探讨存在的问题和今后可能的探讨方向： 探讨目标太过志向化。目前学者探讨VRP的探讨过于注意成本最小和路径最短，大部分是单目

14、标优化，而在实际应用中，配送的驾驶员也可能会因很多缘由耽搁安排的行程，顾客的需求各异甚至冲突，顾客满足度与企业成本最小化目标之间存在效益悖反的冲突。今后的探讨可以将成本、路程、驾驶员休息、顾客满足度等多个目标联合起来进行探讨，并可以通过线性加权的方式进行综合求解。 单个约束的VRP问题由于探讨时间较长，现在已经探讨的较为成熟，而且其应用局限也比较大，应当考虑将多个约束条件结合起来，建立符合实际的多约束条件的车辆路径问题，更好地解决企业的配送优化。 虽然启发式算法具有全局搜寻实力强，运算便利等优点，但是也存在着局部搜寻实力差、收敛时间过长、易陷于局部最优等问题。运用单一的群智能算法不是求解VRP

15、的最有效算法，将两种和多种群智能算法结合起来探讨车辆路径问题，取长补短，是今后应当考虑的问题；同时，应考虑寻求更多的智能优化算法来求解VRP问题。 参考文献： 1 GB. Dantzig， JK. Ramser. The truck dispatching problemJ. Management Science， 1959，6：80-91. 2 蒋波. 基于遗传算法的带时间窗车辆路径优化问题探讨D. 北京：北京交通高校，2022. 3 赵辰. 基于遗传算法的车辆路径优化问题探讨D. 天津：天津高校，2022. 4 张群，颜瑞. 基于改进遗传算法的混合车辆路径问题J. 中国管理科学，2022，

16、20：121-128. 5 郎茂祥. 装卸混合车辆路径问题的模拟退火算法探讨J. 系统工程学报，2022，20：485-491. 6 穆东，王超，王胜春，等. 基于并行模拟退火算法求解时间依懒型车辆路径问题J. 计算机集成制造系统，2022，21：1626 -1636. 7 魏江宁，夏唐斌. 基于混合模拟退火算法的多阶段库存路径问题探讨J. 工业工程与管理，2022，20：1-8. 8 M Mirabi， SMTF Ghomi， F Jolai. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing

17、problemJ. Robotics and Computer-Integrated Manufacturing， 2022，26：564-569. 9 马建华，房勇，袁杰. 多车场多车型最快完成车辆路径问题的变异蚁群算法J. 系统工程理论与实践，2022，31：1508 -1516. 10 辛颖. 基于蚁群算法的车辆路径规划问题求解探讨D. 长春：吉林高校，2022. 11 陈迎欣. 基于改进蚁群算法的车辆路径优化问题探讨J. 计算机应用探讨，2022，29：2031-2034. 12 段征宇，杨东援，王上. 时间依靠型车辆路径问题的一种改进蚁群算法J. 限制理论与应用，2022，27：15

18、57-1563. 13 马炫，彭芃，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法J. 计算机工程与应用，2022，45：200-204. 14 吴耀华，张念志. 带时间窗车辆路径问题的改进粒子群算法探讨J. 计算机工程与应用，2022，46：230-235. 15 Yang X S. A new metaheuristic bat-inspired algorithmC / Nature-Inspired Coopreative Strategies for Optimization， 2022：65 -74. 16 马祥丽，张惠珍，马良. 蝙蝠算法在物流配送车辆路径优化问题中的应用J. 数学的实践与相识，2022，45：80-86. 第10页 共10页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页