chelianglujingwenti1

车辆路径问题的禁忌搜索算法研究

郎茂祥，胡思继

（北方交通大学交通运输学院，北京100044）

摘要：论文在对车辆路径问题进行简单描述的基础上，通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法，并进行了实验计算。计算结果表明，用本文设计的禁忌搜索算法求解车辆路径问题，不仅可以取得很好的计算结果，而且算法的计算效率较高，收敛速度较快，计算结果也较稳定。

关键词：车辆路径问题；禁忌搜索算法；优化

Study on the Tabu Search Algorithm for Vehicle Routing Problem

LANG Mao-xiang，HU Si-ji

（School of Traffic and Transportation，Northern Jiaotong University，Beijing 100044，China）

Abstract：On the basis of describing the vehicle routing problem briefly, this paper presents a new solution indicating method then builds a new tabu search algorithm for the problem and make some experimental computations. The computational results demonstrates that the high quality solutions to the vehicle routing problem can be obtained by using the new tabu search algorithm, and the new algorithm is also efficient and robust.

Keywords：vehicle routing problem; tabu search algorithm; optimal

1 引言

车辆路径问题（VRP，Vehicle Routing Problem）是由Dantzig和Ramser于1959年提出的[1]。该问题一直是运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。研究车辆路径问题具有重要的理论和现实意义。

车辆路径问题作为一个NP难题，随着客户数量的增加，可选的车辆路径方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。求解车辆路径问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法[2]、分区配送算法[3]、方案评价法等。

禁忌搜索算法的出现，为求解车辆路径问题提供了新的工具。Gendreau、Jiefeng、Barbarosoglu、蔡延光等都曾利用禁忌搜索算法求解车辆路径问题[4-8]，并取得了一些研究成果。但现有研究成果多将车辆路径问题描述为一个网络图问题，因此在设计其禁忌搜索算法时多采用有向边排列的解的表示方法，基于这种解的表示方法所构造的禁忌搜索算法具有以下缺点：（1）由于解的表示不太直观，使得算法策略不仅较为复杂，而且不易理解；（2）解中的元素较多，不仅占用的计算机存储量较大，而且求解时计算时间较长，搜索效率较低；（3）算法迭代过程中产生的解中不可行解很多，从而大大影响了算法的收敛速度。为了克服现有禁忌搜索算法的缺点，本文在对车辆路径问题进行简单描述的基础上，提出了一种新的解的表示方法——客户直接排列的解的表示方法，并基于这种解的表示方法构造了求解车辆路径问题的一种新的禁忌搜索算法，并通过实验计算证明了这种新的禁忌搜索算法的良好寻优性能。

2 车辆路径问题的禁忌搜索算法的设计

2.1 车辆路径问题的描述

为了使问题易于理解，本文用一个配送车辆调度问题描述车辆路径问题。该问题可以描述为：从某物流中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使配送总里程最短，并满足以下约束条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。

2.2 禁忌搜索算法的原理和实现步骤

利用禁忌搜索算法求解组合优化问题时，首先按照随机方法产生一个初始解作为当前解，然后在当前解的邻域中搜索若干个解，取其中的最好解作为新的当前解。为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这使得算法可在一定程度上避开局部最优点，从而开辟新的搜索区域。

用禁忌搜索算法求解组合优化问题时，其实现步骤为（以目标函数求最小为例）：

第一步：选定一个初始解x now；令禁忌表H=φ；

第二步：若满足终止准则，转第四步；否则，在x now的邻域N（x now）中选出满足禁忌要求的候选集C-N（x now），转第三步；

第三步：在C-N（x now）中选一个评价值最好的解x best，令x now = x best，更新禁忌表H，转第二步；

第四步：输出计算结果，停止。

2.3 车辆路径问题的禁忌搜索算法的设计

用禁忌搜索算法求解车辆路径问题时，确定解的表示方法是一项非常关键的工作，它直接决定算法实现的难易程度和算法性能的优劣。针对现有文献中有向边排列的解的表示方法的缺点，根据车辆路径问题的特点，作者提出了一种新的解的表示方法，即客户直接排列的解的表示方法。对于一个有L个客户的车辆路径问题，这种解的表示方法是直接产生L 个1~L间的互不重复的自然数的排列，表示客户顺序，然后按照车辆路径问题的约束条件，依次将解的元素（客户）划入各条配送路径中。例如，对于一个用2台车辆向5个客户送货的车辆路径问题，设某解中的客户排列为41235，可用如下方法得到其对应的配送路径方案：首先将客户4作为第一个客户加入到配送路径1中，然后判断能否满足问题的约束条件，即客户4的需求量是否超过第一台车辆的最大载重量，且路径0-4-0的总长度是否超过第一台车辆一次配送的最大行驶距离，设能够满足，这时可将客户1作为第二个客户加入到路径1中，然后判断能否满足问题的约束条件，即客户4和1的需求量之和是否超过第一台车辆的最大载重量，且路径0-4-1-0的总长度是否超过第一台车辆一次配送的最大行驶距离，设仍能满足，这时可再将客户2作为第三个客户加入到路径1中，设仍能满足问题的约束条件，这时可再将客户3作为第四个客户加入到路径1中，设此时不能满足问题的约束条件，这说明客户3不能加入到路径1中，由此可得第一条配送路径：0-4-1-2-0；然后，将客户3作为第一个客户加入配送路径2中，若能满足问题的约束条件，则可将客户5作为第二个客户加入到路径2中，若仍能满足问题的约束条件，则可得配送路径2为：0-3-5-0。采用这种表示方法时，若某个解对应的配送路径数大于配送车辆总台数，则说明该解为一个不可行解。

基于上述客户直接排列的解的表示方法，结合车辆路径问题的特点，作者构造了求解该问题的一种新的禁忌搜索算法，其算法策略如下。

（1）解的评价方法。用禁忌搜索算法求解组合优化问题时，需要对解进行评价，使算法在迭代过程中，不断搜索到质量更优的解。根据对车辆路径问题的描述，对于某个解要判

定其优劣，首先要得到该解所对应的配送路径方案，然后要判断该配送路径方案是否满足问题的约束条件，同时计算该配送路径方案的目标函数值，在满足问题的约束条件的前提下，其目标函数值越优，则解的质量越高。采用客户直接排列的表示方法产生的解所确定的配送路径方案，隐含能够满足每个客户都得到配送服务及每个客户仅由一台车辆配送的约束条件，也能满足每条路径上各客户需求量之和不超过配送车辆的最大载重量及每条配送路线的长度不超过车辆一次配送的最大行驶距离的约束条件，但不能保证配送路径条数小于配送车辆总台数。对于某个解，设其对应的配送路径方案的配送路径条数与配送车辆总台数之差为M（若配送路径条数≤配送车辆总台数，则取M=0，表示该解为可行解；若配送路径条数>车辆总台数，则M>0，表示该解为一个不可行解），其目标函数值为Z，可将M看成该解对应的配送路径方案的不可行路径条数，设对每条不可行路径的惩罚权重为Pw（该权重可根据目标函数的取值范围取一个相对较大的正数），则该解的评价值E可用公式（1）计算。

E=Z+M×Pw （1）（2）邻域操作方法。禁忌搜索算法是一种基于邻域搜索技术的算法，确定邻域操作方法是构造该算法的一个重要步骤。本文采用两交换法实施邻域操作。该方法是指随机选择解中的两个元素，并交换其值的邻域操作方法。现举例说明之。设某解为S=123456789，随机产生的交换点为第4位和第7位，则实施两交换后可得原解的一个邻居S’=123756489。

（3）禁忌对象的确定。禁忌对象是指禁忌表中被禁的那些局部最优解。本文将每次迭代得到的最好解作为禁忌对象放入禁忌表中。

（4）禁忌长度的确定。禁忌长度是指被禁对象不允许被选取的迭代步数。本文取禁忌长度为一个常数，其值应根据问题的规模确定。

（5）候选集合的确定。本文将从当前解的邻域中随机选择若干个邻居作为候选集合。

（6）终止准则的确定。本文采用迭代指定步数的终止准则。

与基于有向边排列的解的表示方法的禁忌搜索算法相比，本文设计的上述基于客户直接排列的解的表示方法的禁忌搜索算法具有以下优点：（1）解的表示十分直观，且算法策略较为简单和易于理解；（2）解中的元素少，占用的计算机存储量小，且计算效率较高；（3）由于这种解的表示方法充分利用了问题的知识，使得算法在迭代过程中产生的解大多为可行解，因而算法的收敛速度较快。

3 实验计算和结果分析

作者用C语言程序实现了上述车辆路径问题的禁忌搜索算法，并对一个由计算机随机生成的实例（见实例1）在主频为133MHz、内存为16MB的计算机上进行了实验计算。

实例1：设在某物流中心有5台配送车辆，车辆的最大载重量均为8t，车辆一次配送的最大行驶距离都为50km，需要向20个客户送货。作者利用计算机随机产生了物流中心和20个客户的位置坐标以及各客户的货物需求量，其中物流中心的坐标为（14.5km，13.0km），20个客户的坐标及其货物需求量见表1。要求合理安排配送车辆的行车路线，使配送总里程最短。为简便起见，本文设各客户相互之间及物流中心与客户之间的距离均采用直线距离，该距离可根据客户和物流中心的坐标计算得到。

该实例包括20个客户，客户的全排列数多达2.433×1018个，受计算时间的限制，用穷举法根本无法求解。根据该问题的特点，作者在用禁忌搜索算法对其求解时采用了以下参数：对不可行路径的惩罚权重取300km，迭代步数取400，每次迭代共搜索当前解的40个邻居，禁忌长度取10。用禁忌搜索算法对实例1随机求解10次，得到的计算结果见表2。

表1 实例1的已知条件

表2 实例1的禁忌搜索算法计算结果

从表2可以看出：用禁忌搜索算法对实例1的10次求解中，都得到了质量很高的解，其解的平均值为107.4km，平均使用的车辆数为3.8辆。其中第3次计算得到的解的质量最高，其配送总里程为103.3km，对应的4条配送路径分别为：路径1：0-1-7-16-13-6-11-20-0；路径2：0-12-2-9-15-19-8-5-0；路径3：0-10-18-17-3-4-0；路径4：0-14-0。禁忌搜索算法的计算结果也较稳定，10次求解中，最差的解的配送里程仅比最好的解高8.4%。从计算效率看，10次求解的平均计算时间仅为1.70s，计算效率较高。

为了便于比较，作者还分别用爬山算法、遗传算法和模拟退火算法对实例1求解了10次[9]，在每次求解对解的搜索次数都为16000次的前提下，四种算法计算结果的比较见表3。

由表3可以看出，上述算法中，从寻优结果看，禁忌搜索算法的计算结果略优于模拟退火算法，而明显优于爬山算法和遗传算法；从计算效率看，禁忌搜索算法的计算效率不及爬山算法，但高于遗传算法和模拟退火算法；从算法的稳健性看，禁忌搜索算法计算结果的稳定性高于遗传算法、模拟退火算法和爬山算法。

通过以上实验计算，可以总结出本文构造的车辆路径问题的禁忌搜索算法的以下特点：（1）算法求得的解的质量较高；（2）算法的收敛速度较快，计算效率较高；（3）算法的稳健性较强。

4 结论

（1）本文在对车辆路径问题进行简单描述的基础上，为求解该问题提出了一种新的解的表示方法，即客户直接排列的解的表示方法，进而基于这种解的表示方法构造了一种求解车辆路径问题的新的禁忌搜索算法。与现有文献中基于有向边排列的解的表示方法的禁忌搜索算法相比，本文设计的禁忌搜索算法具有解的表示自然直观，算法策略易于理解，计算效率较高，收敛速度较快的优点。

（2）实验计算结果表明，用本文设计的禁忌搜索算法求解车辆路径问题，不仅可以得到质量很高的解，而且算法的收敛速度较快、计算效率较高，计算结果也较稳定，显示了良好的寻优性能。

（3）本文构造车辆路径的禁忌搜索算法的思路以及在算法中设计的新的解的表示和评价方法及其它算法策略，对解决类似的组合优化问题有一定的参考价值。

[参考文献]

1 Dantizig G.，Ramser J.. The truck dispatching problem. Management Science，1959，6：80~91

2 Gillett B. E. and Miller L R. . A Heuristic Algorithm for the Vehicle Dispatch Problem. Opns. Res.，1974，22：340~349

3 罗上远，徐天亮，陈代芬. 零售业库存分布模型及分区配送算法研究. 物流技术，2000，5：22~25.

4 Gendreau M.，Hertz A.，Laporte G.. A tabu Search Heuristics for the Vehicle Routing Problem. Management Science，1994，40：1276~1290.

5 Gendreau M.. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operation Research， 1996，44（3）：469~477

6 Jiefeng Xu，James P.K.. A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem. Transportation Science，1996，30（4）：379~393

7 Barbarrosoglu，Gulay，Ozgur. Tabu Search Algorithm for the Vehicle Routing Problem. Computers & Operations Research，1999，26（3）：255~270

8 蔡延光，钱积新，孙优贤. 多重运输调度问题基于双表的并行表搜索算法. 系统工程理论与实践，1998，18（11）：20~26

9 郎茂祥. 物流配送车辆调度问题的模型算法研究：[学位论文]. 北京：北方交通大学，2002