车辆路径问题

什么是车辆路径困难

车辆路线困难（VRP）最早是由Dantzig和Ramser于1959年第一次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户供应货物，由一个车队负责分送货物，组织适当的行车路线，目标是致使客户的需求得到满足，并能在适当的约束下，高达诸如路程最短、成本最小、耗费时间最少等目的^[1]。

自此定义不难看出，旅游商困难（Traveling Saleman Problem,TSP）是VRP的特殊情况，受于Gaery^[2]已确认TSP困难是NP难题，所以，VRP也属于NP难题。

车辆路线困难从1959年提出以来，一直是网络优化困难中最基本的困难之一，受于其应用的普遍性和经济上的巨大价值，一直承受国内外学者的普遍关注。车辆路线困难可以描述如下（如图1）：

设有一场站（depot），共有M 辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户执行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违背车辆容量的制约，目的是所有车辆路线的总距离最小。车辆路线的事实困难包含配送中心配送、公共汽车路线策划、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

车辆路径困难的类型^[3]

一般来说车辆路线困难大差不差可以分为下方三种类型（Ballou，1992）：

1、相异的单一起点和单一终点。

2、相同的单一起点和终点。

3、多个起点和终点。

车辆路径困难的方法^[3]

有关车辆路线困难之学术研究文献大量，也提出了相当多的求解策略与方法，Bodin and Golden（1981）将大量之求解方法归纳成下方七种：

数学解析法（Exact Procedure）；

人机互动法（Interactive Optimization）；

先分群再排路线（Cluster First–Route Second）；

先排路线再分群（Route First–Cluster Second）；

节省法或插入法（Saving or Insertion）；

改观或交换法（Improvement or Exchanges）；

数学规划近似法（Mathematical programming）。

车辆路线困难研究现况^[4]

经历几十年的研究发展，车辆路线困难研究获得了大批成果。下面从车辆路线困难的现有研究型态和求解方法两个方面介绍车辆路线困难的研究现况。

车辆路线困难型态

在基本车辆路线困难（VRP）的基础上，车辆路线困难在学术研究和事实应用上造成了很多不同的延伸和改变型态，包含时窗制约车辆路线困难（vehicle routing problems with time windows，VRPTW）、追求最佳服务时间的车辆路线困难（VRPDT）、多车种车辆路线困难（fleet size and mix vehicle routing problems，FSVRP）、车辆多次运用的车辆路线困难（vehicle routingproblems with multiple use of vehicle，VRPM）、考虑收集的车辆路线困难（vehicle routingproblems with backhauls，VRPB）、随机需求车辆路线困难（vehicle routing problem with stochastic demand，VRPSD）等。

求解方法

1、求解方法演进

综合以往相关车辆路线困难的求解方法，可以分为精确算法（exact algorithm）与启发式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher^[5]曾将求解车辆路线困难的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包含有各种局部改观启发式算法和贪婪法（Greedy）等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包含指派法、集合分割法和集合涵盖法；第三阶段是从1990开始迄今，属于较新的方法，包含利用严谨启发式方法、人工智能方法等。

2、启发式算法

受于VRP是NP-hard困难，很难用精确算发求解，启发式算法是求解车辆运输困难的首要方法，多年来很多学者对车辆运输困难执行了研究，提出了各种各样的启发式方法。车辆运输困难的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。

简单启发式方法包含节省法或插入法、路线内／间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法（savings or insertion）是在求解过程中运用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依靠其余方法造成一个起始路线，然后以迭代的方式利用交换改观法降低路线距离，直到不能改观为止。1960年，Clarke和Wright^[6]首先提出一种启发式节省法（savings methods）来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP困难。

两阶段方法包含先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别执行路线排序；后者则是先将所有的需求点建组成一条路线，再依据车辆的容量将这一路线分割成很多适合的单独路线。

1990年至今，人工智能方法在处理组合优化困难上表明出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线困难的求解中，并构造了大批的基于人工智能的启发式算法。禁忌搜索法（TS）差不多是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP ，随后亦有很多位学者也发表了求解VRP的TS 算法。西南交通大学的袁庆达^[7]等设计了考虑时间窗口和不同车辆类型的禁忌算法，该种算法首要采取GENIUS方法造成初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman^[8]对VRP的模拟退火算法执行了研究，他提出的模拟退火方法首要适合于处理路线分组。遗传算法具有求解组合优化困难的不错特性，Holland首先采取遗传算法（GA）编码处理VRPTW 困难。当下多数学者采取混合策略，分别采取两种人工智能方法执行路线分组和路线优化。Ombuki^[9]提出了用遗传算法执行路线分组，然后用禁忌搜索方法执行路线优化的混合算法。Bent和Van Hentenryck^[10]则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。

归纳几种人工智能方法可以看出，TS算法所得到的解最靠近最优解，但其运算时间也最长，是GA算法的2～3倍，SA算法的差不多20倍；受于GA算法也能较好的接近最优解，同期使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的成长前途的方法；SA算法求解速度非常快，也能供应一定程度上的优化方案在求解较小范围困难上具有较好效果。

参考文献

↑ Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM[M]。Society for Industrial and Applied Mathematics philadephia.2002

↑ 祝崇俊,刘民,吴澄.供给链中车辆路径困难的研究进度及前景[J].计算机集成制造系统－CMS.2001,7(11):1-6

↑ ^3.03.1 邱志鸿.物流配送中心货车路线困难之研究

↑ 张强,荆刚,陈建岭.车辆路线困难研究现况及发展方向[J].交通科技,2004(1):60-62

↑ Fisher M L，Vehicle Routing．Handbooks in Operations Research ＆ Management Science Vol 8，1995.1～33

↑ Clarke G，Wright J．Scheduling of vehicles from central depot to a number of delivery points［J].Operations Research,1964,12:568～581

↑ 袁庆达，闫昱,周再玲．Tabu Search算法在优化配送路线困难中的应用.计算机工程,2001(11):86～89

↑ Osman I H.Meta-strategy simulated annealing an Tabu search algorithms for the vehicle routin problem.Annu Oper Res,1993,41:77～86

↑ Ombuki.B M，Nakamura M，Osamu M．Ahybri search based on genetic algorithm s and tabu search for vehicle routing.Brock University T echnica Report:#CS-02-07,2002,5:1～7

↑ R .Bent and P.Van Hentenryck.A two-stage hybri local search for the vehicle routing problem with tim windows.Technical Report,CS-01-06,Brown University,2001,9:1～30