有时间窗车辆路径问题

什么是有时间窗车辆路径困难

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

受于VRP困难的连续发展，考虑需求点对于车辆到达的时间有所要求之下，在车辆途程困难当中加入时窗的制约，便形成有时间窗车辆路径困难（VRP with Time 万得ows, VRPTW）^[2]。有时间窗车辆路径困难（VRPTW）是在VRP上加之了客户的被访问的时间窗约束。在VRPTW困难中，除了行驶成本之外, 成本函数还要包含受于早到某个客户而引起的等候时间和客户需要的服务时间^[3]。

在VRPTW中，车辆除了要满足VRP困难的制约之外，还务必要满足需求点的时窗制约，而需求点的时窗制约可以分为两种，一种是硬时窗（Hard Time 万得ow），硬时窗要求车辆务必要在时窗内到达，早到务必等候，而迟到则拒收；其他是软时窗（Soft Time 万得ow），不一定要在时窗内到达，但是在时窗之外到达务必要处罚，以处罚替代等候与拒收是软时窗与硬时窗最大的不同^[2]。

Bodin^[4]和Solomon^[5]分别对VRP及其变形困难和VRPTW困难作了较具体的总括。生产事实中很多困难都可以归结为VRPTW来处理, 如钢铁厂编制热轧带钢轧制计划困难事实上就是一个VRPTW困难。一部分服务性行业中也广泛存在如此的困难, 如邮政投递，飞机、火车及公共汽车的调度等。自从Savelsbergh^[6]确认了VRPTW是一个NP难困难之后, 对其算法的研究就首要集中到各种启发式算法上。遗传算法、禁忌搜索法和模拟退火法等智能化启发式算法的显现为求解VRPTW困难给予了新的工具。Thangiah^[7]和Joe^[8]都曾应用遗传算法求解VRPTW困难, 前者的目标是使总体服务成本最小, 而后者的目标有两个, 首先是运用最少的车辆, 其次是在运用最少车辆的前提下使总成本最小^[3]。

时间窗车辆路径困难的求解方法^[2]

含时窗制约之车辆途程困难（VRPTW）相对于车辆途程困难（VRP），务必额外顾虑到运送时间与时间窗口，其首要的原因来自顾客有服务时间的最后期限和最早开始服务时间的制约。故在此制约条件之下，原先VRP困难除了空间方面的路径（Routing）考虑之外，还务必要加之时间上的排程（Scheduling）考虑，同期受于场站也有时间窗的制约，也间接产生路径长度的制约，自此可知VRPTW的总巡行成本不仅包含运送成本，仍需要考虑时间成本，以及未在时间窗制约内送达的处罚成本。所以，若要得到一个好的解答，时间和空间（Temporal andSpatial）困难的探讨是非常重要的。

受于VRPTW比VRP困难多考虑了一样时窗的原因，所以在解法上较VRP困难更为复杂，而依据Taillard（1997）等人的分类，求解VRPTW的方法可以分为六种，分述如下。

1、以分枝界限法求算之精确解法（Exact Algorithm Based on Branch-and-BoundTechniques）：Kolen（1987）利用该种方式可以求得精确解，但是只能处理六至十五个节点的困难，所以求解的规模过小，仅适用于小型困难。

2、途程建构启发式算法（Route Construction Heuristics）：在一困难中，以某节点选择原则或是路线安排原则，将需求点一一纳入途程路线的解法。如Soloman（1987）的循序建构法（Sequential Insertion Heuristics）。

3、途程改观启发式算法（Route Improvement Heuristics）：先决定一个可行途程，也就是一个起始解，之后对这个起始解一直做改观，直到不能改观为止。而常见的是节线交换法（Edge Exchange Procedure），如Lin（1965）所提出的K-Optimal，以及Potvin与Rousseau（1993）提出一考虑旅游方向的交换算法。

4、合成启发式算法（Composite Heuristics）：此种解法混合了途程建构启发式算法与途程改观启发式算法，如Russell（1995）所提出的Hybrid Heuristics便是混合了Potvin与Rousseau（1993）所提出的平行插入法，并在当中加入路线改观法的合成启发式算法；Roberto(2000)也提出的属于平行插入法与内部交换改观法的合成启发式解法来求解VRPTW的困难。

5、根据最佳化之启发式算法（Optimization-Based Heuristics）：如Koskosidis（1992）等人利用混合整数规划模块，再透过启发式算法，将原始困难分解成指派/分群的子困难的一连串的巡行以及排程困难。

6、通用启发式算法（Metaheuristics）：传统区域搜寻方法的最佳解常因起始解的特性或搜寻方法的制约，而只能得到局部最佳解，为了改观此一缺点，近年来在此领域有巨大发展，是新一代的启发式解法，包含禁忌法（Tabu Search）、模拟退火法（Simulated Annealing）、遗传算法（Genetic Algorithm）和门坎接受法（Threshold Accepting）等，可以有效处理局部最佳化的困扰。如Potvin（1996）等人、Taillard（1997）等人均利用Tabu Search的方式来求解VRPTW的困难。

参考文献

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

↑ ^2.02.12.2 邓宇佑(硕士).求解医院运输部门运输中心个数最佳化之研究(D).成功大学工业治理研究所硕士论文，1991年

↑ ^3.03.1 李大卫,王莉,王梦光.遗传算法在有时间窗车辆路径困难上的应用[J].系统工程理论与实践,1999,(8):65～69

↑ Bodin L, Golden B,A ssad A and Ball M. Routing and Scheduling of Vehicles and Crews: The State of the Arts. Computers %26amp; Operations Research, 1983, 10: 62～ 212

↑ Solomon M , Desrosiers J. Time 万得ow Constrained Routing and Scheduling Problems :A Survey. Trans sportation Science, 1988, 22 (1): 1～11

↑ Savelsbergh M. Local Search for Routing Problems with Time 万得ows. Annals of Operations Research ,1985, 4: 285～305

↑ Thangiah S,Nygard K and Juell P. Gideon. A Genetic Algorithm System for Vehicle Routing with Time 万得ows. Proceedings of the Seventh Conference on Artificial Intelligence Applications ,Miami, Florida,

1991: 322～325

↑ Joe L.and Roger L. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms. Proceedings of the Fifth International Conference on Genetic Algorithms,1993,452～459