塔布启动式搜索车辆路径问题

1、塔布启动式搜索车辆路径问题摘要 本文回顾了十个最重要的解决车辆路径规划问题的塔布启发式搜索算法。首先描述一些主要的塔布搜索特性：邻里关系结构、短期记忆、长期记忆、强化。然后描述各种塔布搜索的算法，最后给出计算结果和结论。关键词：车辆路径问题、塔布搜索、启动式。简介1. 介绍 传统的车辆路径问题（VRP）可以定义为一个无向图，其中表示顶点，表示边。顶点代表一个车站建立以米为单位的相同的车辆容量Q,其余顶点代表城市或客户。一个非负成本，距离或出行时间的矩阵定义在上。每个客户有一个非负的需求和一个非负的服务时间。VRP需要在m条车辆路径上做出决策满足一系列条件，i）最低总成本；ii）以车站为开始和结

2、束的点；iii）每个客户恰好使用一辆车经过一条路径；iv）任何路径的总需求不超过Q；v）任何路线的总持续时间超过一个预设D。车辆的数量是一个输入值或一个决策变量。在后一种情况下车辆固定成本有时纳入目标函数。 VRP是一个重要的组合优化问题。VRP在分布式管理中占有重要地位。据Toth 与Vigo (2002)报道，在分配过程中运用计算机的处理方法可以节约运输成本从5%到20%不等。Golden, Assad,与 Wasil (2002) 与Barker (2002) 研究了几个案例中运用VRP算法会节约非常可观的成本。 VRP是由Dantzig 与Ramser (1959)在40多年前提出的。

3、此后稳步发展成为解决该类问题的一种有效的解决方案和设计方法，既可以求精确的也可以求近似的解。对于这个问题，当客户数多于50个时，目前仍然没有一个精确算法能够有效的解决该问题（Golden etal., 1998; Naddef and Rinaldi, 2002）。在实践中通常采用启发式方法。 启发式方法包括建设性的启示（例如 Clarke 和 Wright, 1964）逐步建立一个可行解试图保持解决方案成本尽可能低。第二阶段的客户启发式首先被聚合成可行的路线和实际路线然后构造(例如, Gillett 与Miller, 1974; Fisher 和Jaikumar, 1981)改进方法,按照单

4、一的路线通过应用启发式的旅行商问题(TSP)，或者几个路线通过执行客户的再分配和交换。(例如, Thompson 与Psaraftis, 1992; Van Breedam, 1994; Kinderwater 与Savelsbergh, 1997)。据Laporte和Semet(2002),经典启发式通常有一个很低的执行速度因此往往产生的解决方案与最著名的有一个很大的差距（通常在3%至7%之间）。 在过去的十五年里，一些启发式算法为了解决VRP而被提出来。这些通常执行一个全面解决方案的探索空间，允许恶化甚至不可行中间解决方案。很多方法保持一个良好的解决方案是为了重新结合产生跟好的方案。Gen

5、dreau, Laporte，与 Potvin (2002)为了VRP已经确定了六个家庭的启发式演算法：模拟退火，确定性退火，塔布搜索，遗传算法，蚂蚁系统和神经网络。虽然任何特定的成功与其执行特性相关，但是很公平的说塔布搜索很明显优于竞争对手的方法。这是一些研究人员通过独立进行大量的计算实验确认的，与Christofides, Mingozzi,的计算结果比较，Toth (1979) (CMT)在十四基准情况下，看到Gendreau, Laporte, 与 Potvin (2002)。我们的目的是比较和VRPd的十个最好的TS实现分析，我们将首先在第2节中描述四个重要特征的TS算法。这将在第3

6、节中关于这些特性分析个体的TS算法和通过评估和第4节中的结论.2. 塔布搜索特征塔布搜索是Glover(1986)提出的,它已经迅速成为一个最好的和最广泛的本地搜索的组合优化方法。该方法执行的解空间的探索从解决确定迭代对最优解的一个子集的领域。由于并不一定改善，一个塔布原理是放在适当位置以防止骑行在一个序列的解决方案。这是一种幼稚的方法来防止骑行,为的是禁止这一过程回到以前遇到的解决方案。但这样做通常会需要额外的簿记。然而，过去解决方案的一些属性是记名的与任何解决方案的这些属性可能不被认为是为了的迭代，这种原理通常被称为短期储存。其他特征比如多样化和强化通常被执行，多样化的目的是确保在搜索过程

7、中不会限制解空间有限的那一部分。它保持跟踪过去的解决方案和频繁执行动作的不利，这通常称为长期储存。强化包含执行一个强调搜索周围最好的解决方案。一些调查论文和书记都写在TS上。其中我们推荐Glover 和Laguna (1993, 1997)，和Hertz 与 de Werra(1991)。接下来，我们研究领域结构，短期和长期记忆策略，并且强化方法在VRP上下文中。2.1领域结构 在TS算法中有两种主要的方法定义VRP的领域结构。首先，Osman (1991, 1993)把互换称为包含在两条路径间交换到客户。其次，把在同一时间作用于两个以上的路径称为射链(Rego 和Roucairol,1996

8、）。在互换中，为了限制价值的数量的可能性通常会被限制在1或2。这种交换最好的描述是由一对（）代表一个由路径1移动到路径2的客户的运算和由路径2移动到路径1的的客户的运算。因此，忽略对称性，接下来可能的移动在两个互换中：（2,2），（2,1），（2,0），（1,1），（1,0）。注意互换包括简单的互换（1,1）和简单的移动（1,0）。这个方案的几种改变时可行的，比如对路径的限制或者顶点考虑到互换，或者在执行局部优化时插入和删除来产生优化路径。弹射链(Xu 与 Kelly, 1996; Rego 与Roucairol, 1996; Rego, 1998)包含循环识别路径和移动顶点在路径1到2上，路

9、径2到3等等。他们推广互换超过2个路径。设计高效的TS算法需要在有效的领域和计算的有效性之间有显著的平衡。由于更多的方案考虑到在每一次的迭代因此更复杂的领域会有更丰富的搜索，但是同时需要的是大量的计算。另一个相关的问题是在搜索过程中考虑到领域中是否有不可行解。允许这样移动的一个优点是他们使该类型的序列，是可行的，但是是不可行的并且的可行度大于。处理不可行的一种方法是由Gendreau,Hertz,与Laporte(1994)提出通过使用一个惩罚类型的目标函数表示可行解的路径的成本，分别表示测量总的超额需求和所有路线总的多余的时间，是自动调节的参数。初始条件为，如果最后的解是可行的（不可行）则这

10、些参数是周期性的减少（增加），并且是用户控制的参数。在简单领域结构使用的上下文中考虑不可行移动的优势会更明显，比如（1，0）位置变动。当顶点领域结构方案被采用时，如弹射链，搜索过程可以直接从到，可以不经不可行解。2.2短期储存搜索 为了防止循环，它是禁止反向移动迭代常见的方法。因此一个客户从路径到路径重复次可能被禁止直到重新插入路径然后重复次，或者没有重复次时客户不可能离开路径。Taillard(1991)根据离散均匀分布提出了在区间随机选择，但是一些算法使用固定的值。 如果这会导致没有风险的循环，那么使用特赦原则是取消塔布地位的一种常见的措施，例如，如果这个的产生更好的整体现任的可行解，或者

11、更好的整体现任的在具有某一属性的属性集中。2.3 长期储存搜索为使搜索多样化，很多TS频繁执行移动实现惩罚。这种做法是通过添加路径成本的惩罚项相当于三个因素的产物；1）一个因素测量过去移动的频率；2）一个因素测量实例的大小（比如）；3）一个用户控制比例的因素。实际上，实现这样的原理是有效的并且计算也很简便。这个原理首先是被Glover (1989）提出的，被Taillard (1992)仔细整理的。2.4强化搜索 强化包含强调搜索有前景的地域。周期性的路径改进的TSP算法可归类为强化技术，另一种方式进行强化搜索时使用广泛的领域结构周围的一些显著的解决方案。 Rochat 和Taillard (

12、1995)为TS所提出的自适应储存的概念可能是最有说服力的强化工具。自适应储存室在解决人口问题的搜索过程中遇到的一个很好的方案。与在遗传算法类似，我们的想法是将解决方案元素与解决人口的方案相结合来构建新的解决方案。如果他们的价值小于这些人口的一些解决方案。他们从人口解决方案中保留好的方案，丢弃不好的方案。在VRP的背景下，一个新的方案的初始步骤是从好的解决方案中很多不重叠路线提出来的。通常这些路线不会覆盖所有的顶点，否则会有重叠。然后搜索时从选定的路线和选定的路径的顶点开始。3.TS算法的概述 我们现在对十大最受欢迎的TS算法的车辆路径问题的概述，重点是对每一种算法做出创新的特点的概述。 3.

13、1sman算法是Osman (1991, 1993)提出了互换的概念。在他的想法中他用，这样允许夹杂单顶点和双顶点的移动，并且单顶点个双顶点可以在车辆路径之间互换。Osman测试两种方案，选择了领域的解决方案。首先，称作最好的可采纳的（BA）不是塔布搜索的方案被选定。其次，称为第一最好的可采纳的(FBA)，第一的可采纳的改善解决方案如果存在就被选定，否则最好的可采纳的解决方案将被保留。Osman通过实验证明在相同的停止条件下FBA的解决方案产生的效果稍微好些。但是它的转变却比BA的转变慢很多。Osman的TS实现使用固定的塔布占有权，没有长期储存原理也没有强化方案。3.2Gendreau, H

14、ertz 与 Laporte的塔布路径算法 在塔布路径(Gendreau, Hertz, 与Laporte, 1994)获得领点解决方案是通过移动一个顶点从目前的路径r到另一个包含其最近一个领域的路径s。插入路径s的值与一个本地重新优化同时进行， 使用GENI机制TSP(Gendreau, Hertz, 与Laporte, 1992).这可能导致创建一个新的路径或删除其中一个。为了限制邻域大小，只有使一个顶点随机选择的子集被认为是安插在其他路线。这个客观的处罚的概念被引进Taburoute.参数和以10次迭代为调整期：如果10之前关于能力（路线时间）的解决方案是切实可行的，然后除以2，如果他们

15、都不可行，那么乘以2，否则保持不变。任一顶点的删除从路线r在迭代t直到 ，是为了防止被重新插入该路径迭代，其中是随机选定的在区间5，10之间，当然，除非这样做会产生新现任的解决方案。连续的多元化方案也适用。塔布路线采用美国后优化启发式的TSP(Gendreau,Hertz, 与 Laporte, 1992)。两种类型的功能的加强使用。错误的开始是从几个解决方案开始执行有限的搜索，然后运行主要搜索过程从而获得的最佳解决方案开始。此外，经过一个给定的 迭代没有改进多少，更激烈执行搜索起点与现任，但这时允许更多的顶点从他们目前的路线移动。3.3 Taillard算法 虽然它比塔布路线早出版一年，但是

16、 Taillard （1993）的算法在同一时期开发的。它采用了1 -交换机制没有本地重新优化，并没有允许不可行性。这种方案使用简单得多。在塔布路线允许更多的迭代相同的运行时间.塔布机制过程中要执行和长期记忆策略是相同的塔布路径。每隔一段时间，路径的确切使用是Volgenant 与 Jonker(1983)通过TSP算法重新优化。通过Taillard开发的搜索程序采用了适合于使用并行计算的分解方案。在平面问题，客户群首先划分为部门集中在仓库，并且还为同心圆。搜索是在每个分区由一个异纽处理器执行。该次区域的边界会定期更新，以提供多元化的效果。在非平面的问题，区通过植根于车厂最短的跨越树形图的计算

17、定义。 Taillard的算法仍然是这一天最有效的TS启发式的一VRP 。在14 CMT的情况下，它已经产生的最知名的解决方案12 。3.4 The Rochat 与 Taillard自适应存储过程 罗查特和Taillard的自适应内存程序（AMP）是根据所提出的标题概率多样化和集约化。如果在定期的应用 搜索过程中，它提供了一个多样化的过程，允许新的高品质的解决方案 涌现。如果作为一个后优化应用，它最好被看成是一种集约化的过程。 该方法不应被视为VRP的启发式本身，而是作为一般 程序适用于多种环境，并与几个启发式方案结合使用。 例如，它由Bozkaya, Erkut and Laporte (

18、2002)是适用于优化后政治通过TS启发式方法获得。将其应用到VRP帮助提高Taillard对CMT的情况下产生的解决方案，从而产生最有名的现任各14实例。3.5 Xu与Kelly算法 在他们的TS算法，Xu与Kelly (1996)由两条路线之间喷出链和顶点之间的互换振荡定义的邻居。喷射链的最小化由下式确定，如图1中所描绘的那种类型的网络上的流量。2级和3级的弧有1或0的流量以指示从一个路径（第2级）或顾客是否被删除重新插入路由（3级）。 1 路径节点 客户模式 路径节点 1 1 t s t m m n 1级 2级 3级 4级 图1：对于Xu and Kelly的算法网络流量问题。因为几个客

19、户可以从相同的路线被移除或重新插入到同样的路线，所有的弧成本仅为约数。如在以前的一些算法，单个条路由3步最优和2步最优操作方式定期重新优化。中级不可行的解决方案对于容量是允许的（带有=1），固定塔布任期的使用，以及一个长期的基础频率的内存被应用。 最知名的解决方案进行维护和搜索过程是周期性 应用于该池的解决方案产生更好的人的希望。总体而言， 该算法已经产生的产能受限的VRP几个很好的解决方案，但是相当复杂的，并且需要的几个参数的设置。3.6 Rego与 Roucairol算法Rego 与 Roucairol (1996)使用涉及级，或路线喷出链，界定邻域。基本上是一个弹射过程中颠簸一个顶点从一

20、个层次到连续级，从第1级和第级结束。最后被撞的顶点，从1级， 有可能搬迁的顶点从1级删除的位置，而且还可能在其他地方（图2）。喷出链被认为是只有在没有弧（边）出现 不止一次地在溶液中，但违反容量或时间约束的路由 被接受。此算法的并行版本由作者来实现。 1 2 3 图2：一个1级喷出链。三个顶点都显示为每个路由。中间的一个被排出。3.7 Rego的鲜花算法 由Rego（1998）中描述的鲜花算法采用弹射过程中，从移动由几个花（或路由），以另一种解决方案通过一个适当的VRP解决方案删除和引入边缘。应用这些操作创建的中间结构包括一个路径，称为干，从仓库发出的，和几个花连接到它。因此，一个花可转化为干

21、细胞（图3a）或分成花和茎（图3b）。在这个过程中，车辆主动路线数目可以变化。 a)转化一个花到干去除 b)转化一个花到花然 边缘入射到库。 后除一条边干并引 入另一个 图三：两个喷射链规则的花算法。在这两种情况下，软件仓库 由黑色顶点表示候选解花朵只包括通过执行该保持花的结构弹射移动获得的。这是通过适当地删除边缘的结构和插入新的完成。这个过程是通过声明塔布刚刚被删除的边缘的重新引入嵌入在TS机制。如在以前的一些算法，可变塔布任期的使用和基于移动频率的长期多元化策略被应用。这里，惩罚期是随机的间隔内，其长度与生成的。3.8 Toth 与 Vigo颗粒状塔布搜索算法Toth 与 Vigo (19

22、98)提出的粒度的概念并不只适用于VRP或变性人的算法，而是对整个离散优化。像AMP，它是一种高度 便携式机制。我们的想法是永久考虑长边删除有属于一个最佳解决方案只有很小的可能性。更具体地说，阈值被定义和搜索上的限制边集其中是一家集定义为入射到库重要的边缘。值被设置为等于，其中被称为稀疏化参数，是在迅速获得良好的可行解的平均边成本，例如，由Clarke and Wright (1964)的算法。在实践中，选择在区间1:0;2:0的结果中消除80至90的所有的边。这个想法Toth 与 Vigo已与塔布路径结合应用。(Gendreau, Hertz, 与 Laporte, 1994).3.9 Ba

23、rbaroso¸glu 与 ÄOgÄur算法Barbaroso¸glu 与 ÄOzgÄur (1999) TS启发式的开发设计是一个分销公司在土耳其的送货路线。邻域解决方案由一个交换机制来定义，车辆的路线是定期用2步，最优优化后和解决方案始终是可行的。塔布路线的塔布机制才能被应用，但没有长期记忆的多元化进程实施。如塔布路线，全搜索过程被施加到最好几个起始溶液和加剧相运行从搜索过程中所遇到的最佳解决方案开始。3.10 Cordeau,Gendreau,Laporte 与 Mercier的统一塔布搜索算法统一塔布搜索算法（UTSA）最早是

24、在多站的VRP（Cordeau, Gendreau 与Laporte, 1997）的定期VRP和为它产生竞争激烈的结果的背景下开发的。它后来被应用到相关网站VRP带时间窗（(Cordeau 与Laporte, 2001），以周期的VRP与和多仓库VRP有时间窗（Cordeau, Laporte 与 Mercier, 2001），最后，以经典的VRP容量和线路长度的限制（Cordeau et al., 2002）。UTSA使用的几个塔布路线，即同一领域结构的特点，GENI插入，长期频率的处罚基于它不同于在一个塔布路径方法数。搜索被添加到一个单一的初始解决方案，固定塔布的持续时间是使用，没有应用强

25、化阶段。 虽然UTSA还允许中间不可行的解决方案，在每次迭代中它要么除以或乘以和的一个因素根据以前的解决方案是否可行，来判别量或路线的持续时间。塔布机制的运作属性集是由车辆走访在解决方案中。邻居的解决方案是由的去除和替换它取得，其中。属性为塔布的迭代次数，并且吸入标准是指相对于属性。UTSA的两个有趣的特点是它相对简单（这与极少数经营 参数）和它的灵活性。它已成功地应用于各种大型的VRP通过始终保持其参数为相同值的变异体。4. 评估和结论 塔布搜索作为VRP最好的启发式。在过去的十年一些已经被开发和测试。可以说他们已经在解决这个棘手的问题非常成功。在这个部分的成功是由于一些所含的几种关键概念：

26、在搜索过程中对不可行解的补充，使用自调整参数，连续的多样化，喷射链自适应存储器和粒度。比起任何其他功能，这些想法都促成TS启发式的成功和经受住了时间的考验。 目前，在14 CMT基准实例，我们在表1的比较计算结果在第3节实施，。而第一个成熟的最佳的实例是著名的例子，由Rochat 与 Taillard (1995) 获得最知名的解决方案被认为是接近最优的，并用于评估的程度其他启发式的准确性。在不到1的最著名的收益率的比较平均偏差中使用的大多数的TS实现。计算的时间都难以对比，因为它们不总是出现结果，不同的计算机被使用时，两种实现方式使用并行计算（Taillard, 1993; Rego 与 R

27、oucairol, 1996），它始终不清楚要进行多少次试验。我们相信，小范围的精确度主要在CMT实例的改进。相反，即使开发精简实施，一些应该致力于使用更少的参数和简单的设计，精度稍微变差的结果。此外，算法应该是很容易适应处理过程中出现的实际环境方面的制约因素的多重性。正如Cordeau et al. (2002)所指出的研究界是用来评估启发式相对于单独的准确性和速度，但简单性和灵活性往往被忽视。然而，这些两个属性是由最终用户必须采用并且设计下一代的算法应该是中心。致谢AcknowledgementsThis research was partly funded by the Canadian

28、 Natural Sciences and Engineering Research Council (NSERC) under grants 22783700 and OGP0039682, and by the Fonds pour la Formation de chercheurs et l'aide la recherche (FCAR) under grant 2002-ER-73080.This support is gratefully acknowledged.这项研究部分由加拿大自然科学和工程再投资 搜索理事会（NSERC）的赠款22783700和OGP003968

29、2，并通过 Fonds pour la Formation de chercheurs et l'aide µa la recherche (FCAR下授出2002ER73080的支持表示感谢。参考文献G. Barbaroso¸glu and D. ÄOzgÄur. A Tabu Search Algorithm for the Vehicle Routing Problem.Computers & Operations Research, 26:255-270, 1999.E.K. Barker. Evolution of Microc

30、omputer-Based Vehicle Routing Software: Case Studies in United States. In The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 353-362, 2002.B. Bozkaya, E. Erkut and G. Laporte. A Tabu Search Heuristic and Adaptive Memory Pro

31、cedure for Political Districting. European Journal of Operational Research. Forthcoming,2002.N. Christofides, A. Mingozzi, and P. Toth. The Vehicle Routing Problem. In Combinatorial Optimization, N. Christofides, A. Mingozzi and P. Toth (eds), Wiley, Chichester, 315-338, 1979.G. Clarke and J.W. Wrig

32、ht. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12:568-581, 1964.J.-F. Cordeau, M. Gendreau, and G. Laporte. A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems. Networks, 30:105119, 1997.J.-F. Cordeau, M. Gendreau, G. La

33、porte, J.-Y. Potvin, and F. Semet. A Guide to Vehicle Routing Heuristics. Journal of the Operational Research Society. Forthcoming, 2002.J.-F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin, and F. Semet. A Guide to Vehicle Routing Heuristics. Journal of the Operational Research Society. Forthcoming

34、, 2002.J.-F. Cordeau and G. Laporte. A Tabu Search Algorithm for the Site Dependent Vehicle Routing Problem with Time Windows. INFOR, 39:292-298, 2001.J.-F. Cordeau, G. Laporte and A. Mercier. A Uni¯ed Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Journal of the Operatio

35、nal Research Society,52:928-936, 2001.G.B. Dantzig and J.H. Ramser. The Truck Dispatching Problem. Management Science,6:80-91, 1959.M.L. Fisher and R. Jaikumar. A Generalized Assignment Heuristic for the Vehicle Routing Problem. Networks, 11:109-124, 1981.M. Gendreau, A. Hertz, and G. Laporte. New I

36、nsertion and Postoptimization Procedures for the Traveling Salesman Problem. Operations Research, 40:1086-1094, 1992.M. Gendreau, A. Hertz, and G. Laporte. A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, 40:1276-1290, 1994.M. Gendreau, G. Laporte, and J.-Y. Potvin. Metah

37、euristics for the VRP. In The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 129-154, 2002.B.E. Gillett and L.R. Miller. A Heuristic Algorithm for the Vehicle Dispatch Problem.Operations Research, 22:340-349, 1974.F. Glover

38、. Future Paths for Integer Programming and Links to Artificial Intelligence.Computers & Operations Research, 13:533-549, 1986.F. Glover. Tabu Search Part I. ORSA Journal on Computing, 1:190-206, 1989.F. Glover and M. Laguna. Tabu Search. In Modern Heuristic Techniques for Combinatorial Problems,

39、 C.R. Reeves (ed.), Blackwell, Oxford, 70-150, 1993.F. Glover and M. Laguna. Tabu Search. Kluwer, Boston, 1997.B.L. Golden, A.A. Assad, and E.A. Wasil. Routing Vehicles in the Real World: Applications in the Solid Waste, Beverage, Food, Dairy, and Newspaper Industries. In The Vehicle Routing Problem

40、, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 245-286, 2002.B.L. Golden, E.A. Wasil, J.P. Kelly, and I-M. Chao. Metaheuristics in Vehicle Routing. In Fleet Management and Logictics, T.G. Crainic and G. Laporte (eds), Kluwer, Boston,33-56, 1998.A

41、. Hertz and D. de Werra. The Tabu Search Metaheuristic: How We Used It. Annals of Mathematics and Artificial Intelligence, 1:111-121, 1991.G.A.P. Kinderwater and M.W.P. Savelsbergh. Vehicle Routing: Handling Edge Exchanges.In Local Search in Combinatorial Optimization, E.H.L. Aarts and J.K. Lenstra

42、(eds).Wiley, Chichester, 337-360, 1997.G. Laporte and F. Semet. Classical Heuristics for the Capacitated VRP. In The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 109-128, 2002.D. Naddef and G. Rinaldi. Branch-and-Cut Algo

43、rithms for the VRP. In The Vehicle Routing Problem, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 53-84, 2002.I.H. Osman. Metastrategy Simulated Annealing and Tabu Search Algorithms for Combinatorial Optimization Problems. Ph.D. Thesis, The Manage

44、ment School, Imperial College,London, 1991.I.H. Osman. Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research, 41:421-451, 1993.C. Rego. A Subpath Ejection Method for the Vehicle Routing Problem. Management Science, 44:1447-1459, 19

45、98.C. Rego and C. Roucairol. A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem. In Meta-Heuristics: Theory and Applications, Kluwer,Boston, 661-675, 1996.Y. Rochat and ¶E.D. Taillard. Probabilistic Diversification and Intensification in Local Search for Vehicle Rout