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

打开文本图片集

摘 要：车辆路径问题是物流管理与运输组织优化中的核心问题，是运筹学中一类经典的组合优化问题。文章比较系统地总结了常见的VRP问题的分类和基本的数学模型，并通过查阅学者们的研究状况，总结了求解VRP问题常用和高效的启发式算法及相应的研究现状；最后总结了研究存在的问题，并对今后VRP问题的研究和求解方法进行了展望。

关键词：车辆路径问题；启发式算法；优化

中图分类号：U116.2 文献标识码：A

Abstract： Vehicle routing problem is the core problem in logistics management 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， summarized 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 routing problem； heuristic algorithm； optimization

0 引 言

随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题（Vehicle Routing Problem， VRP）是制约物流行业发展的一个关键要素，其研究也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满足一定的约束条件（如时间限制、车载容量限制、交通限制等）下，通过对一系列收货点与发货点客户合理安排行车路线，在客户的需求得到满足的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由Dantzig和Ramser[1]于1959年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学中一类经典的组合优化问题，是典型的NP-难题。

企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。VRP作为物流系统优化环节中关键的一环，其研究成果已经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化研究具有很好的现实意义。

1 车辆路径问题的分类与基本模型

VRP的构成要素通常包括车辆、客户点、货物、配送中心（车场）、道路网络、目标函数和约束条件等，根据侧重点的不同，VRP可以分为不同的类型。根据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；根据任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；根据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；根据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；根据客户对货物接收与发送有无时间窗约束可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；根据客户需求是否可拆分可分为需求可拆分车辆路径问题和需求不可拆分车辆路径问题；根据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；根据配送与取货完成后车辆是否需要返回出发点可分为开放式车辆路径问题和闭合式车辆路径问题；还可以将上述两个或更多约束条件结合起来，构成一些更复杂的车辆路径问题。

由于VRP的约束条件不同引起了其分类多种多样，而不同类型的VRP其模型构造及求解算法有很大差别。VRP的一般数学模型为：

在上述模型中，式（1）表示目标函数，式（2）表示约束条件。其他VRP模型大致都是在此模型的基础上根据约束条件完善形成的。

2 VRP的求解算法与研究现状

VRP的求解方法，基本上可分为精确算法和启发式算法两大类。由于精确算法的计算难度与计算量随着客户点的增多呈指数级增加，在实际中应用范围有限，而启发式算法则具有全局搜索能力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分研究者们主要把精力集中在如何构造高质量的启发式算法上，本文也主要讨论一些近年来研究比较多的启发式优化算法。针对VRP问题目前已提出了大量的启发式算法，其中研究较多的主要包括以下算法：

2.1 遗传算法（Genetic Algorithm，GA）

GA是一种通过模拟生物进化过程来搜索最优解的方法，该方法通过对群体进行选择、交叉和变异等操作，产生代表新的解集的种群，根据个体适应度大小选择个体，通过迭代逐步使群体进化到近似最优解状态。但是该算法具有搜索速度慢、易早熟、总体可行解质量不高等缺点。

采用遗传算法研究VRP问题的研究现状包括：蒋波[2]设计了遗传算法求解以配送总成本最小为目标函数和带有惩罚函数的VRPTW模型；赵辰[3]基于遗传算法求解了从生产中心到仓库之间的路径优化问题，设计了配送路径优化决策；张群和颜瑞[4]建立了多配送中心、多车型车辆路径问题混合模型，并采用一种新的模糊遗传算法求解该问题。

2.2 模拟退火算法（Simulated Annealing，SA）

SA同禁忌搜索算法一样，也属于局部搜素算法，但是模拟退火算法是模仿金属加工中退火的过程，通过一个温度函数作为目标函数，使其趋于最小值，是一种基于概率的算法。

采用模拟退火算法研究VRP问题的研究现状包括：郎茂祥[5]研究了装卸混合车辆路径问题，并构造了模拟退火算法求解该问题；穆东等[6]提出了一种并行模拟退火算法，并将该算法的应用领域扩展到其他车辆路径问题和组合优化问题；魏江宁和夏唐斌[7]以模拟退火算法为基础，研究了单个集散点与多个客户之间的运输问题；Mirabi和Fatemi Ghomi等[8]提出了一种基于模拟退火思想的三步启发式算法求解最小化配送时间的多配送中心VRP模型。

2.3 蚁群算法（Ant Colony Optimization，ACO）

蚁群算法是人们受蚂蚁可以快速找到食物的自然现象启发提出的。蚁群算法所建立的机制，主要包括蚂蚁的记忆、蚂蚁利用信息素进行交互通信及蚂蚁的集群活动三个方面。单个蚂蚁缺乏智能，但整个蚁群则表现为一种有效的智能行为。通过这种群体智能行为建立的路径选择机制可使蚁群算法的搜索向最优解靠近。

采用蚁群算法研究VRP问题的研究现状包括：马建华等[9]研究了基于动态规划方法的多车场最快完成车辆路径问题的变异蚁群算法；辛颖[10]通过对MMAS蚁群算法进行了三种策略的改造，指出蚁群算法可以找到相对较好的解和很强的鲁棒性；陈迎欣[11]针对蚁群算法的缺点，分别对信息素更新策略、启发因子进行改进，引入搜索热区机制，有效解决车辆路径优化问题；段征宇等[12]通过最小成本的最邻近法生成蚁群算法和局部搜索操作设计了一种求解TDVRP问题的改进蚁群算法。

2.4 粒子群算法（Particle Swarm Optimization，PSO）

PSO算法是通过对鸟群觅食行为的研究而得出的一种群体并行优化算法，它从随机解出发，通过迭代寻找最优解。蚁群算法具有容易实现、收敛速度快、精度高等优点，在多种优化问题上均取得了较好的效果。但是由于PSO算法是通过粒子之间的相互作用来寻找最优解，缺乏像遗传算法那样的变异机制，因而PSO算法容易陷入局部最优。

采用粒子群算法研究VRP问题的研究现状包括：马炫等[13]提出了一种基于粒子交换原理的整数粒子更新方法求解有时间窗约束的车辆路径问题；吴耀华和张念志[14]以处理集货或送货非满载带时间窗车辆路径优化问题为背景，提出了带自调节机制的局部近邻粒子群算法解决VRP问题。

2.5 蝙蝠算法（Bat Algorithm，BA）

蝙蝠算法是剑桥大学学者Yang[15]于2010年提出的一种新型群智能进化算法，模拟自然界中蝙蝠通过超声波搜索、捕食猎物的生物学特性，是一种基于种群的随机寻优算法。截至目前，蝙蝠算法主要用于求解连续域的函数优化问题，只有少数学者将其用来求解离散型问题，具有很好的研究前景。

采用蝙蝠算法研究VRP问题的研究现状包括：马祥丽等[16]将蝙蝠算法应用于求解VRP问题，在蝙蝠速度更新公式中引入了惯性权重，对基本蝙蝠算法进行了改进，克服了基本蝙蝠算法的不足之处；马祥丽等[16]针对VRPTW问题的具体特性重新定义了蝙蝠算法的操作算子，设计了求解VRPTW 问题的蝙蝠算法，并采用罚函数的方式对目标函数进行了简化求解。

3 总结与展望

车辆路径问题由于约束条件的不同其分类多种多样，数学模型与求解算法也层出不穷。本文总结了近几年一些相关学者对VRP问题的研究和求解算法，通过较为系统地总结VRP问题，本文总结出以下当前研究存在的问题和今后可能的研究方向：

（1）研究目标太过理想化。目前学者研究VRP的研究过于注重成本最小和路径最短，大部分是单目标优化，而在实际应用中，配送的驾驶员也可能会因许多原因耽误计划的行程，顾客的需求各异甚至冲突，顾客满意度与企业成本最小化目标之间存在效益悖反的矛盾。今后的研究可以将成本、路程、驾驶员休息、顾客满意度等多个目标联合起来进行研究，并可以通过线性加权的方式进行综合求解。

（2）单个约束的VRP问题由于研究时间较长，现在已经研究的较为成熟，而且其应用局限也比较大，应该考虑将多个约束条件结合起来，建立符合实际的多约束条件的车辆路径问题，更好地解决企业的配送优化。

（3）虽然启发式算法具有全局搜索能力强，运算方便等优点，但是也存在着局部搜索能力差、收敛时间过长、易陷于局部最优等问题。使用单一的群智能算法不是求解VRP的最有效算法，将两种和多种群智能算法结合起来研究车辆路径问题，取长补短，是今后应该考虑的问题；同时，应考虑寻求更多的智能优化算法来求解VRP问题。

参考文献：

[1] GB. Dantzig， JK. Ramser. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 蒋波. 基于遗传算法的带时间窗车辆路径优化问题研究[D]. 北京：北京交通大学（硕士学位论文），2010.

[3] 赵辰. 基于遗传算法的车辆路径优化问题研究[D]. 天津：天津大学（硕士学位论文），2012.

[4] 张群，颜瑞. 基于改进遗传算法的混合车辆路径问题[J]. 中国管理科学，2012，20（2）：121-128.

[5] 郎茂祥. 装卸混合车辆路径问题的模拟退火算法研究[J]. 系统工程学报，2005，20（5）：485-491.

[6] 穆东，王超，王胜春，等. 基于并行模拟退火算法求解时间依懒型车辆路径问题[J]. 计算机集成制造系统，2015，21（6）：1626

-1636.

[7] 魏江宁，夏唐斌. 基于混合模拟退火算法的多阶段库存路径问题研究[J]. 工业工程与管理，2015，20（3）：1-8.

[8] M Mirabi， SMTF Ghomi， F Jolai. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing， 2010，26（6）：564-569.

[9] 马建华，房勇，袁杰. 多车场多车型最快完成车辆路径问题的变异蚁群算法[J]. 系统工程理论与实践，2011，31（8）：1508

-1516.

[10] 辛颖. 基于蚁群算法的车辆路径规划问题求解研究[D]. 长春：吉林大学（硕士学位论文），2015.

[11] 陈迎欣. 基于改进蚁群算法的车辆路径优化问题研究[J]. 计算机应用研究，2012，29（6）：2031-2034.

[12] 段征宇，杨东援，王上. 时间依赖型车辆路径问题的一种改进蚁群算法[J]. 控制理论与应用，2010，27（11）：1557-1563.

[13] 马炫，彭芃，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法[J]. 计算机工程与应用，2009，45（27）：200-204.

[14] 吴耀华，张念志. 带时间窗车辆路径问题的改进粒子群算法研究[J]. 计算机工程与应用，2010，46（15）：230-235.

[15] Yang X S. A new metaheuristic bat-inspired algorithm[C] // Nature-Inspired Coopreative Strategies for Optimization， 2010：65

-74.

[16] 马祥丽，张惠珍，马良. 蝙蝠算法在物流配送车辆路径优化问题中的应用[J]. 数学的实践与认识，2015，45（24）：80-86.