物流配送中车辆路径问题的模型及算法研究
摘要：本文介绍了车辆路径问题的分类及限制条件，重点论述了国内外关于车辆路径问题的模型及算法研究现状，分析了各种算法的优缺点和适用范围，并指出了车辆路径问题的研究前景。
关键词：车辆路径问题；精确算法；启发式算法
中图分类号：TP301.6文献标识码：A
文章编号：1002-3100(2007)01-0092-03
Abstract: This paper presents the classifications and constraint conditions about the Vehicle Routing Problem, and discourses emphases upon achievements of models and algorithms for vehicle routing problem at homeland and abroad, and analyzes advantage or disadvantage and its applicable cope of these algorithms. Then it prospects future research orientations of it.
Key words: vehicle routing problem; accurate algorithm; heuristic algorithm
配送中心作为物流活动中专职从事配送工作的组织者，具有规模大、配送能力强的特点，从而使得由配送中心对用户进行需求物品配送成为物流配送的主要形式，而其中配送车辆的路径合理与否，对于配送速度、配送费用、运力配备以及配送成本与效益的影响均很大，采用科学合理的方法来确定车辆路径便成为配送中心进行配送活动的一项重要工作。车辆路径问题（Vehicle Routing Problem，VRP）是由G．Dantzig和 J．Ramser[1]于1959年首先提出来的，很快引起运筹学、管理学、计算机应用、组合数学、图论等学科的专家学者的高度重视。他们对此问题进行了大量的理论研究和实验分析，取得了很大进展。其研究结果在运输系统、物流配送系统、快递收发系统中都已得到广泛应用。现在，对车辆路径问题的研究仍然相当活跃。车辆路径问题一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等）。由此定义不难看出，旅行商问题（Traveling Salesman Problem，TSP）是VRP的一个特例：由于Gaery已证明TSP问题是NP难题，因此，VRP也是NP难题。
1车辆路径问题的分类
在经典VRP的基础上，车辆路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括TSP（当VRP只包括一条路径，且没有能力约束时就成为TSP）、带能力约束的车辆路径问题（CVRP）、带时间窗的车辆路径问题（VRPTW）、追求最佳服务时间的车辆路径问题（VRPDT）、多车种车辆路径问题（FSVRP）、车辆多次使用的车辆路径问题（VRPM）、考虑收集的车辆路径问题（VRPB）、随机需求车辆路径问题（VRPSD）、动态车辆路径问题（DVRP）、满载/非满载VRP、双向VRP等。虽然VRP具有多种变化型态，事实上，根据研究重点的不同，VRP存在多种分类方式，但总的来说，在VRP中，最常见的附加条件有：
（1）能力约束。与每个客户或城市对应的需求是个非负的值，任意车辆路径的总重量不能超过该车辆的能力负荷。
（2）任意路径所含城市数的上界为q。
（3）总时间约束。任意路径的长度不能超过预先给定的界L；该长度由车辆在城市间的旅行时间和在该路径里的每个城市i的停留时间所构成。
（4）时间窗口。必须在时间区间,里访问城市i，并允许在城市i等待。
（5）多个城市间存在优先级关系，必须在访问城市i之前访问城市j。
基于此，文献[2]按已知信息的特征将VRP分为确定性VRP和非确定性VRP，其中非确定性VRP可进一步分为随机VRP（SVRP）和模糊VRP（FVRP）；按约束条件可分为CVRP（带能力约束）、DVRP（带时间距离约束）、VRPTW（带时间窗口）；按需求是否可切分，又可分为可切分的VRP和不可切分的VRP。
2车辆路径问题的算法
在VRP中，问题的算法与所建立的模型密切相关。由于在现有的文献中，大部分文献是研究确定性VRP和非确定性VRP的，因此，下文将对确定性VRP和非确定性VRP的算法作详细介绍。
2.1确定性VRP
确定性VRP是现实中最常见的类型。它指的是这样一类VRP：（1）在路径规划开始之前，规划人员对有关路径规划的所有信息都是清楚的；（2）在路径构建以后，与路径规划有关的信息不再变化。所谓相关信息，包括顾客的所有特征，如顾客的地理位置、所需服务时间、每个顾客的需求量等。解决这类问题的方法一般分为精确算法和启发式算法两类。
2.1.1精确算法
精确算法指可求出最优解的算法。到目前为止，已提出的精确算法种类较多，有分支定界法、割平面法、整数规划算法和动态规划算法等。
Laporte等用VRP与多重旅行商之间的关系，将VRP变形为旅行商问题后，再用分枝定界法求得问题最优解。随后，Laporte等又将该方法拓展到具有其他边约束的问题中。与这种方法略有不同，Christofides等先将问题转化为“K-度中心树”后，再采用分枝定界法进行求解。
求解确定性VRP的动态规划算法最早由Eilon等提出。但由于他们提出的动态规划方法需要考虑相当庞大的状态数，故只能精确求解规模非常小的问题。Christofides等通过运用状态空间松弛技术大大减少了状态数，使动态规划算法的性能得到了很大程度上的改善。他们的实验表明，该方法可有效求解顶点数不超过50的有容量约束VRP。
确定性VRP也可以表示为整数线性规划模型，主要有三种：集分割模型、货物流模型和车辆流模型。Balinsk等最早利用集分割模型来研究VRP。然而，这个模型与一般的动态规划模型有着相同的缺点，即使对于规模较小的问题，模型的变量数在大多数情况下亦是天文数字，比如问题的规模若为10，那么模型中出现的变量数最多可达到1010。除此之外，确定目标函数中的值往往先要求解大量的NP难题（如旅行商问题），这也给问题精确求解带来困难。采用列生成技术可部分解决这些困难，如Agarwal等，Desrosiers等采用列生成技术求解了规模较小有容量和时间窗约束的确定性VRP。
货物流模型和车辆流模型是整数线性规划模型中的另外两种：货物流模型明确地考虑通过每条路径的货物量，车辆流模型则体现了系统中车辆的最优运行方案。在以往的研究中，采用的流变量主要包括两类——双下标变量和三下标变量，如 和 分别表示通过弧i,j的货物量和通过弧i,j驶往顾客l的货物量。使用双下标和三下标变量各有优劣。双下标变量的特点是简便，涉及的变量较少，然而却不能反映不同车辆的成本与特征，因此只适用于车辆类型相同的情况。Desrosiers等，Laporte等分别采用了双下标变量来建摸，其中Laporte等提出了一种约束松弛算法，应用于约束条件较松的问题，效果较好。相比之下，三下标的VRP模型更通用一些，然而涉及的变量一般较多。Fisher等研究了有容量和时间窗约束VRP的三下标模型，并且基于Bender分解，通过交替求解一般指派问题和有时间窗的旅行商问题来求解该问题。后来Martello等又对该算法进行了一些改进。
2.1.2启发式算法
启发式算法是一种寻找近忧解的算法，目前已提出的启发式算法很多，分类也相当多。按传统的VRP启发式算法分类，可分为构造算法、两阶段法、不完全优化算法和改进算法4类。
（1）构造算法
构造算法是根据一定的准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止。如Clarke-Wright节约算法、Solomon插入法，Salhi等提出的簇插入法，Gendreau等提出GENI插入法，Altinkemer和Gavish提出的并行节约算法以及Paessens提出的节约算法等。
（2）两阶段法（Two-phase Algorithm）
两阶段法的基本做法是在第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，每次迭代产生一个解用以替代原来的解，力图使目标函数值得以改进，一直继续到不能再改进目标函数时为止。如Gillett和Miller的Sweep算法，Renaud等的Petal算法，Toth和Vigo提出的先聚类再安排路径的算法，Lin提出的2-opt和3-opt交换，Or提出的Or-opt交换以及Breedam提出的串重置和串交换，Cordone等提出的改进算法等。
一些基于数学规划的算法也属于两阶段法，首先把问题表达成一个数学规划模型，根据其模型的特殊构形，利用一定技巧进行分划，进而求解易于处理的子问题。如Kohld等先利用Lagrangian松弛技术将有时间窗的VRP变为较简单的指派问题，然后用列生成技术来获得问题的近似解。
另外，还有一些两阶段算法在求解过程中常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中。如Cullew、Jarvis和Ratliff提出的两阶段法。
（3）不完全优化算法
以启发式准则代替精确算法中的决策准则，以缩小搜索空间，如Christofides, Mingozzi和Toth提出的算法。
（4）改进算法
从一初始解开始，通过对当前的解进行反复地局部扰乱以达到较好的解。基于启发式的并行算法和亚启发式算法都属于此类。
亚启发式算法包括禁忌搜索算法、模拟退火算法、神经网络和遗传算法等方法。进入20世纪90年代，这些亚启发式算法的应用成为VRP研究中的新趋势。如Gendreau、Hertz和Laporte，Jiefeng和James，Duhamel、Christophe和Potvin，Barbarosoglu、Gulayhe和Ozgur等将禁忌搜索算法应用于VRP的求解，并取得了较好的效果。另外，模拟退火算法、神经网络以及遗传算法等亚启发式算法也已经较成功地解决了确定性VRP中的一些问题。
2.2非确定性VRP
对应于确定性VRP，非确定性VRP指的是：（1）在路径规划开始之前，不是有关路径规划的所有信息，计划人员都是确切知道的，部分信息可能是不确定的、模糊的，甚至是未知的；（2）初始路径构建以后，信息可能会发生变化。很明显，与传统确定型VRP相比，非确定型VRP是一个更一般化的VRP问题。非确定性VRP又可分为随机VRP（SVRP）和模糊VRP（FVRP）。
2.2.1随机VRP
对这种类型的问题，目前出现的算法大部分可以归纳为以先验（即定）序列为基础的方法。该方法分为两个阶段：在信息不完全（随机）的情况下确定先验序列；在获得确定性信息的情况下进行决策。因此，其随机模型的选择基于两点：第一阶段的成本和第二阶段的期望成本。先验序列的确定方法又有两类：一类是按二元可能性理论来确定，另一类则是基于机会约束规划。
第一类方法的思想最早是在Jaillet的博士论文中提出的，并在Bertimas的博士论文中基本建立完整的体系。在该方法中，假定需求分布是二元（即在第i点有单位需求的概率为n，则没有单位需求的概率为）、离散的。根据该假定，可推出先验序列的期望长度，相应的上下界和渐进特性。Michel Gendreau等人以该理论为基础，得到目标函数和罚函数，以Clark-Wright算法生成初始解，然后用禁忌搜索算法对初始解进一步优化，可以求解规模为46的问题。而Laporte基于L-Shaped方法，提出一个精确算法，可解决规模小于50的问题。
另一类方法是Stewart，Laporte等人分别使用机会约束规划，在一定的假定条件下，将SVRP转化为等价的、确定性的VRP，并找到了解的界，其方法的核心是让出错返回的概率不超过一定的界限。机会约束规划模型均以确定性VRP的三下标流和二下标流模型为基础，添加可能性约束条件和罚函数后建立起来的。所用的算法，也与确定性的算法有不少相通之处。如M. Dror就是在建立三下标流机会约束规划模型和罚函数模型后，利用Clark-Wright算法进行求解的。
第二阶段的策略为：按照先验序列，跳过需求为零的客户，直接访问下一个客户，如果车辆负荷超过了车辆最大载重量，则返回出发点卸载，并回到出现超载的地方，继续提供服务。
2.2.2模糊VRP
D. Teodorovic等人是最早着手研究这类问题的人。他以模糊数表示客户点的需求信息，以倾向度为基础建立模糊判定规则，其核心是基于Sweep算法，并省略了Sweep算法的第二阶段，即初始化子路径后对它们的优化过程。
祝崇俊、刘民、吴澄等人以模糊可能性分布，建立了VRP的基于置信度的三下标流模型，并提出了基于可能性分布的2-OPT算法。该算法引入了伪出发点，建立了以置信度为基础的判定规则，以遍历为终止条件，从而在全局层次上进行优化，同时避免过多地扩大搜索空间。该算法已可解决较大规模的问题（大于200个客户）。
3各种算法比较
（1）关于精确算法：由于这些算法都基于严格的数学手段，在可以求解的情况下其解通常要优于人工智能算法。但引入严格的数学方法后，则无法避开指数爆炸问题，从而使该类算法只能有效求解中小规模的确定性VRP。
（2）关于启发式算法：在求解中小规模VRP时，启发式算法与精确算法相比，在精度上不占优势。但在求解大规模VRP时，启发式算法总可以在有限时间里，找到满意的次优解/可行解，这是精确算法难以做到的。因此，在实际应用中，启发式算法要更广泛。
（3）确定性VRP是非确定性VRP研究的基础。目前，我国对复杂的VRP研究还仍处于起步状态。但现实生活中最常见的还是不确定VRP，大部分确定性VRP是不确定性VRP的简化。现有的SVRP的成果己经可以解决小规模的SVRP，但不能胜任较大规模的SVRP。解决较大规模的SVRP的现实途径仍然是人工智能方法，不过要获得通用的高效算法是困难的，因此应结合邻域特征来研究并对具有不同邻域特征的问题提出不同的算法。对于FVRP，应结合模糊可能性理论来进行研究。
4结束语
目前VRP模型方面虽有许多研究，但缺少综合方面的研究。现代物流中，要求尽量减少库存，及时配送变得越来越重要，所以今后满足客户的时间窗口是制定车辆路线优先考虑的重点。还有现有的配送路线的研究多为开发静态的模型，很少分析参数随时间变化的特性，而在现代物流日趋快速化、信息化、实时化的情况下已经有些不适应。例如，仓库位置的成本将随时间变化；在一定的时间范围内，公司需要根据情况的变化来重新决策配送中心及销售网点的分布。因此，在配送路线模型中加入动态特性，实现实时或在线物流管理，会极大地提高与现实接近的程度。
参考文献：
[1]Dantzig G, Ramser J. The truck dispatching problem[J]. Managment Science, 1959(6):80-91.
[2] 祝崇隽，刘民，吴澄. 供应链中车辆路径问题的研究进展及前景[J]. 计算机集成制造系统，2001,7(11):1-6.
[3] 张强，荆刚，陈建岭. 车辆路线问题研究现状及发展方向[J]. 交通科技，2004(1):60-62.
[4] 荆海霞. 物流配送中双向运输车辆路径优化问题研究[D]. 武汉：武汉大学（硕士学位论文），2004.
[5] 肖增敏，李军. 动态网络车辆路径问题：研究现状及展望[J]. 系统工程，2004,22(7):68-71.
[6] 尚华艳. 物流配送中车辆路径问题研究[D]. 武汉：武汉理工大学（硕士学位论文），2005.
[7] 谢秉磊，郭耀煌，郭强. 动态车辆路径问题：现状与展望[J]. 系统工程理论方法应用，2002,11(2):116-120.
[8] 张建勇. 模糊信息条件下车辆路径问题研究[D]. 成都：西南交通大学（博士学位论文），2004.
下一篇：整合生物信息学