车辆路径规划问题研究综述

摘 要：为了提高车辆路径规划能力，阐明路径优化问题的发展趋势。国内外学者从理论以及实际应用的角度对该问题进行研究。路径优化问题的研究已经发生了重大转变。研究环境转变为需求的不确定、道路状况的动态变化;研究目标转变为车辆总成本、能耗和污染物排放的权衡;研究客体转变为多能源、多车型的车辆选择;研究方法转变为多模型、多算法、多学科融合的综合系统。

关键词：路径规划;算法;仿真

中图分类号：TB 文献标识码：Adoi：10.19311/j.cnki.1672-3198.2019.26.104

Vehicle Routing Problem，即车辆路径规划问题，自1959年由Ramser和Dantzing提出，经过60年来的研究与发展，研究的目标、对象、限制条件等均有所变化，已经从最初的简单车辆安排调度问题转变为复杂的系统问题。本文对近五年来具有代表性的路径优化文献进行分析、总结，从算法和模型的研究角度出发，揭示车辆路径问题优化的发展方向，对日后该问题的研究提出相应地建议。

如今，路径优化算法除了传统的遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法之外，而且演变出多学科融合的创新算法，如：模拟植物生长算法、粒子群优化算法、细菌觅食优化算法等，主要应用Matlab、Python等软件来模拟算法结果，验证算法的有效性。

范厚明（2018）等提出一种半开放式的多配送中心联合配送模式，考虑到生鲜品运输的时效性要求，设计了相应的时间窗及惩罚成本，建立了车辆运输总成本、调度成本和时间惩罚成本最小的优化模型，并设计了蚁群算法对其进行求解。Nekooghadirli（2014）等针对不确定需求的LIRP問题，以最小化总成本和最大化供应时间为目标，建立了多目标优化模型，并结合禁忌搜索和模拟退火算法求解算例。曹庆奎（2013）等针对港口集卡问题，利用蚁群算法在解决组合优化问题方面的优势和遗传算法的全局寻优能力，设计了遗传蚁群算法，建立了面向“作业面”的港口集卡路径成本优化模型。最后通过实例验证遗传蚁群算法的可行性。程博（2013）]等针对大件公路运输路径选择优化难题，以最小化运输成本为目标，在考虑客户服务和配送时限、惩罚超载车辆、车辆载重和容积限制的基础上，针对大件公路运输路径规划问题，改进了遗传模拟退火算法对此类问题进行优化。葛显龙（2013）等针对跨区域多配送中心的动态需求，提出了基于实际情况的配送车辆共享和联合配送策略，建立了适合实际情况的车辆路径优化模型，并利用云模型理论对交叉概率和变异概率的设置模式进行了改进。并设计了云遗传算法来求解模型。最后，通过实例对模型和算法进行了验证和分析。

韩亚娟（2018）等引入对客户容忍水平的考虑，构造出一种折线型软时间窗的车辆路径问题的通用数学模型，设计了一种具有一定通用性的超启发式遗传算法，在该算法中以遗传算法作为上层搜索算法，以三种启发式算法——CW 节约法、MJ 插入法和 Kilby 插入作为底层搜索规则，通过预排序、局部搜索和全局优化来改进算法。刘艳秋（2016）等基于仓储集货运输与路径可行性的回收车辆路径特性，对传统蚁群算法的编码方式、概率选择方式进行改进，提出一种逆选择操作蚁群算法。最后通过算例证明模型与算法的有效性。侯玉梅（2015）等基于整车物流配送问题，以总成本最小化为目标，构建了带软时间窗约束的整车物流路径优化模型，并设计了自适应遗传算法，用算例对其进行了验证。葛显龙（2013）等基于不同车型线路优化的匹配问题，根据综合费用的不同制定车型分配原则，建立多车型车辆调度问题的数学模型，设计了一种高效的量子遗传算法，并通过实例验证了该模型和算法的有效性。

杨翔（2018）等基于模糊可信性理论建立了模糊需求模型，利用随机模拟算法进行客户需求预测，并设计了一种两阶段禁忌搜索算法进行仿真，并通过实例验证了该模型和算法的有效性。实验表明，决策保守程度对配送总成本存在明显影响，过于保守或过于冒险均不能获得较好的路径安排方案。肖建华（2017）等将根据城市道路的限制因素，如区域和车辆类型，引入了车辆路径问题。以碳排放和运输总成本最小为目标，建立了基于城市道路约束的多能源多车型混合汽车路径优化模型。提出了一种变邻域搜索算法来求解该模型，并通过实例和大规模基准验证了该模型和算法的有效性。王茜（2016）等考虑了多车槽、多车型双重属性，在构建HFFMCVRP的三下标流数学模型基础上，将在反应机理与导引机理相结合的基础上，提出了一种混合导引反应禁忌搜索算法，予以求解。马华伟（2016）等建立了多卡车、单挂车的甩挂运输路径规划模型，设计禁忌搜索算法改进初始解，并通过实例验证算法的可行性和有效性。Nourinejad（2015）等针对单向车辆共享不平衡问题，提出了车辆搬迁与员工联合优化模型，并利用禁忌搜索算法进行计算。通过实验得出结论：车队规模对需求的敏感性大于员工规模，员工规模与车辆数成反比，车辆搬迁时间与车辆成本成正比。李进（2013）等建立了以低碳为目标的多车型路径规划模型，利用多起点禁忌搜索算法进行求解，并通过实例验证了算法的可行性，证明了多起点策略的有效性。

王伟（2018）等基于车辆速度限制，建立了危险货物运输网络优化的两层规划模型，设计了粒子群优化算法来求解两层规划模型。最后，通过两个实例对模型和算法进行了验证。证明车辆限速是兼顾企业利益，同时可以有效降低危险品运输总风险的有效途径。周和平（2017）等建立了区间阻抗下的鲁棒最短路模型，基于模型设计了分支定界算法，并对一个大型路网进行了仿真测试。结果表明：相对于最短路径法，该方法求解得到的最短路径具有更强的鲁棒性，且求解结果准确高效。牟向伟（2016）等针对车货匹配问题建立模型，并设计改进量子进化算法对模型进行求解，结果表明，改进的量子进化算法可以高效地搜索到高质量的车货匹配方案，为车主和货主推荐较为合理的匹配信息。Adam（2015）等基于车辆容量限制对多商品运输问题进行研究，提出了连续松弛整数规划模型，建立了列生成算法，经过对比验证了所建模型和算法的有效性，为多货种车辆路径优化提供新方向。谭立静（2015）等提出了一种通过对自适应细菌觅食优化算法的学习，并将其应用于带时间窗的车辆路径问题。通过模拟实验，证明该算法具有收敛速度快、搜索精度高的特点。潘国强（2015）等采用微粒群算法解决多客户、多供应商、多产品的路径选择问题，在建立复杂供应链的复杂映射关系的基础上，引入综合运输概念，选择运输方式，设计配送路径。

模拟植物生长算法是李彤在2005年所提出来的，其本质思想就是迭代运算。算法参数设计简单，且具有很强的适用性，尤其对网络优化有着十分理想的效果。曹庆奎（2015）等基于客户需求的随机性特点，考虑外包车辆和配送人员加班等限制因素，建立了机会约束规划模型，并设计了模拟植物生长算法求解模型，证明了算法可以高效地获得最优解。Guerrero（2013）等针对零售企业复杂的末端配送系统，设计了混合整数线性规划模型，提出了一种精确式混合启发算法，通过实验证明与分解方法相比，该算法具有较好的解决该问题的能力。

车辆路径规划问题算法逐渐细化，愈发贴近实际生活。在追求降本增利的总目标时，充分考虑“顾客需求稳定性”、“城市运输车辆限制”以及“顾客的容忍程度”等客观因素，并且作为算法的立足点。这样的算法在实际应用时更容易给组织带来利益。

关于路径优化问题的研究已经发生了重大的转变。研究环境变化：由传统的单一车辆的调度问题，转变为需求的不确定性、道路状况的动态性的复杂环境;研究目标变化：由单纯追求成本最小化，转变为权衡车辆总成本、能耗和污染物排放等，考虑距离、运量和车速对成本、能耗和污染物排放的影响;研究客体转变为多能源、多车型的车辆选择;研究方法变化：由早期的简单分析方法，转变为多模型、多算法、多学科融合的综合系统研究。

参考文献

[1]范厚明，杨翔，李阳.基于生鲜品多中心联合配送的半开放式车辆路径问题[J].计算机集成制造系统，2016，（01）.

[2]Nekooghadirli N，Tavakkoli-Moghddam R，Ghezavati V R，et al.Solving a new bi-objective location-routing-inventory problem in a distribution network by meta-heuristics[J].Computers & Industrial Engineering，2014，（76）：204-221.

[3]曹庆奎，赵斐.基于遗传蚁群算法的港口集卡路径优化[J].系统工程理论与实践，2013，（077）：1820-1828.

[4]程博，杨育，刘爱军，等.基于遗传模拟退火算法的大件公路运输路径选择优化[J].计算机集成制造系统，2013，（04）：879-887.

[5]葛显龙，王旭，邓蕾.基于联合配送的开放式动态车辆路径问题及算法研究[J].管理工程学报，2013，（03）：60-68.

[6]韩亚娟，彭运芳，魏航，等.超启发式遗传算法求解带软时间窗的车辆路径问题[J].计算机集成制造系统，2015，（01）.

[7]刘艳秋，徐世达，张颖，等.考虑路径可行性与仓储集货模式下的回收车辆路径问题研究[J].中国管理科学，2016，（12）：98-107.

[8]侯玉梅，贾震环，田歆，等.带软时间窗整车物流配送路径优化研究[J].系统工程学报，2015，（02）：240-250.

[9]葛显龙，许茂增，王伟鑫.多车型车辆路径问题的量子遗传算法研究[J].中国管理科学，2013，（01）：125-133.

[10]杨翔，范厚明，徐振林，等.模糊需求下多中心开放式车辆路径优化[J].计算机集成制造系统，2017，（01）.

[11]肖建华，王超文，陈萍，等.基于城市道路限行的多能源多车型车辆路径优化[J].系统工程理论与实践，2017，（05）：1339-1348.

[12]王茜，吉清凯，胡祥培.多车型多车槽VRP的混合导引反应式禁忌搜索算法[J].管理工程学报，2016，（03）：179-187.

[13]马华伟，范奉伟，胡笑旋.基于禁忌搜索算法的甩挂运输路径规划问题研究[J].中国管理科学，2016，（S1）：194-198.

[14] Nourinejad M，Zhu S，Bahrami S，et al.Vehicle relocation and staff rebalancing in one-way carsharing system[J].Transportation Research Part E：Logistics and Transportation Review，2015，（81）：98-113.

[15]李进，傅培华.具有固定车辆数的多车型低碳路径问题及算法[J].计算机集成制造系统，2013，（06）：1351-1362.

[16]王伟，张宏刚，丁黎黎，等.考虑车辆限速和風险公平性的危险品运输网络双目标优化模型[J].系统工程，2018，36（07）：91-104.

[17]周和平，冯轩，彭巍.区间阻抗下的鲁棒最短路算法[J].系统工程，2017，35（12）：121-125.

[18]牟向伟，陈燕，高书娟，等.基于改进量子进化算法的车货供需匹配方法研究[J].中国管理科学，2016，（12）：166-176.

[19] Adam N L，Juan S.Stronger multi-commodity flow formulations of the capacitated vehicle routing problem[J].European Journal of Operational Research，2015，244（3）：730-738.

[20]谭立静，王红，牛奔.基于ACLBFO算法的车辆路径规划[J].系统工程，2015，33（04）：120-125.

[21]潘国强，胡俊逸，洪敏.面向综合运输网络的复杂供应链问题建模与耦合求解算法[J].计算机集成制造系统，2015，（11）：3041-3053.

[22]曹庆奎，刘新雨，任向阳.基于模拟植物生长算法的车辆调度问题[J].系统工程理论与实践，2015，（06）：1449-1456.

[23] Guerrero W J，Prodhon C，Velasco N，et al.Hybird heuristic for inventory location-routing problem with deterministic demand[J].International Journal of Production Economics，2013，146（1）：359-370.