基于禁忌搜索算法的线路规划方案求解

廖大强，邬依林，印 鉴

（1.中山大学 信息科学与技术学院，广东 广州510507；2.南华工商学院，广东 广州510507；3.广东第二师范学院 计算机科学系，广东 广州510310；4.中山大学 信息科学与技术学院，广东 广州510275）

0 引 言

有时间窗和车辆限制的开放式车辆线路问题 （open vehicle routing problem with time window and vehicle limits，m－OVRPTW）主要应用在铁路运输、公共交通、航空运输等领域［1］。对此，Fu 和Wright研究了一个实际案例［2］：英国铁路为过海峡隧道的货物提供运输服务，案例提供了起始地和目的地的信息和火车运力等资料，要求设计方案使得火车通过隧道的次数最少、运输的路程最短、车辆的编组最少。对于运输部门，车辆资源通常是有限的。在车辆数量受到约束的情况下，使最多客户的需求得到满足，就成了这些部门最重要的目标。同时考虑到运输成本，在满足同等客户的情况下，使总运输路程最少成了另一个重要目标。所以m－OVRPTW 问题具有重要的现实意义。

虽然OVRPTW 问题有不少实际应用的案例，但到目前为止，研究OVRPTW 问题的文献却不多，而研究m－OVRPTW 问题的文献更是难以找到。文献［3］给出了OVRPTW 问题的综述，并提出一种启发式算法，采用Solomon基准测试数据［4］和Homberger的大型数据集［5］，对比了该算法与其它几种算法的结果；文献［6］研究了一个报纸分派的案例，把该案例建模成一个带区域限制的OVRPTW 问题，并提出了一种禁忌搜索算法对该案例进行求解；文献［7］针对OVRPTW 问题设计一种遗传算法，对一个随机数据集进行了测试并给出了运算结果。

另外，通过枚举m－OVRPTW 问题的车辆数并求解m－OVRPTW 问题，也能解决OVRPTW 问题，这也是研究m－OVRPTW 问题的重要意义之一。m－OVRPTW 问题可以转化为广义多约束的背包问题，由于背包问题已被验证为NP－Hard难题，所以m－OVRPTW 问题也是NP－Hard 难题，使用高效的近似算法来解决m－OVRPTW 问题是一个很好的研究方向。

1 问题的描述

1.1 符号说明

首先引入两个0－1决策变量

模型使用到的记号：V 表示车辆的集合；L 表示客户的集合并上车场的集合，其中编号为1的是车场，编号为2到｜L｜的是客户。m 是问题给定的车辆数量；λ是一个大系数，用来保证第一个目标先于第二个目标被考虑；η是一个大系数，用来实现式 （10）、式 （11）的条件选择。dij表示从点i到点j 的距离

1.2 数学模型

本文将研究有时间窗和车辆限制的开放式车辆线路问题，它是一类特殊的开放性车辆线路问题 （OVRP）。它规定有一个存有货物的车场 （depot），通过m 辆车辆 （vehicle）把货物配送到若干客户 （customer）里。客户与客户之间的距离和行程时间、客户和车场之间的距离和行程时间、客户的货物需求量、每个客户可接受服务的时间窗（开始时间和截止时间）、每个客户的服务时间长度、车辆的数量、每辆车辆的最大货物容量都是已知的。车辆从车场出发，一个接一个地配送货物给客户，每个客户至多被配送一次。在截止时间之内，车辆的派送到达，如果过早的话，那么车辆将会等待。车辆所载货物总量不能大于其容量，每次服务完一个客户后，车中的货物量等于服务前的货物量减去该客户的货物需求［8］。

m－OVRPTW 问题跟一般的车辆线路问题 （VRP）不同的是，它不要求车辆完成所有客户的配送后要回到车场，车辆在最后一个客户的服务完成后就结束任务，可以自由选择停泊的地方，而且m－OVRPTW 问题限定了只能使用m 辆车辆配送货物。问题的首要目标是使尽可能多的客户得到服务，第二目标是所有车辆的总路程尽可能短［9］。下面是数学模型的目标函数

约束条件

式 （3）目标函数的第一部分乘以一个大系数λ，保证了客户数量这个第一目标要优先考虑，只有当车辆数目相同的情况下再考虑车辆总路程的第二目标。式 （4）是m－OVRPTW 问题特有的车辆数量限制，限定只有m 辆车进行配送。式 （5）、式 （6）保证每个客户点最多只能被访问一次。式 （7）保证每车辆的行驶路线是连续的。式 （8）保证每辆车的运行路线中不会存在环。式 （9）保证车辆配送的货物总量不会超过车辆的容量。式 （10）、式 （11）保证车辆的离开时刻、到达时刻和两点间的行程时间，这三者满足时间约束要求。其中使用大系数η把带有条件选择的非线性约束，转变成线性约束。

1.3 禁忌搜索简介

禁忌搜索 （Tabu search）算法是局部邻域搜索算法的推广，Glover在1986年首次提出这一概念，并形成一套完整的算法［10］。禁忌搜索算法跟一般局部搜索算法不同的是利用了禁忌表来记录最近遇到的局部最优解，然后通过查询禁忌表来避免重复搜索以前已经搜索的状态，从而跳出局部最优解，搜索更多的状态空间［11］。禁忌搜索算法的一般流程如图1所示。

图1 禁忌搜索算法基本流程

2 禁忌搜索算法在线路规划中的应用

本文提出一种基于禁忌搜索框架的算法来解决m－OVRPTW 问题，通过改进的局部搜索方法，快速得到m－OVRPTW 问题的高质量近似解。

2.1 邻域变换规则

由于禁忌搜索是局部邻域搜索的扩展，邻域的变换规则决定了邻域解的分布和质量，而且变换规则的选取既影响算法的爬山能力又影响了算法跳出局部解的能力，因此邻域变换规则是影响禁忌搜索质量和效率的一个重要因素。为了提高解的质量，本算法引入了以下几种邻域变换规则：选取一个不在当前解内的结点x，然后再选取当前解中的一个结点b（结点b可以是车场），在结点b后插入结点x，如图2所示。这个变换规则，可以使得更多的结点加入到当前解中，它可以快速提高当前解的质量，是最重要的变换规则。

图2 新结点插入规则

“当前解结点插入规则”与 “新结点插入规则”本质上都是结点插入变换，但由于 “新结点插入规则”涉及到新结点的加入，可以更有效地提高解的质量，而 “当前解结点插入规则”并没有增加当前解的总客户数，所以本文将他们区分开来，并在邻域搜索中给予分配独立的发生概率。

变换规则的发生概率见表1，4种变换规则的发生概率都设为25%，而对于有内部分类的规则 （当前解结点插入规则和结点交换规则），其内部分类按等概率处理。

表1 4种变换规则的发生概率/%

2.2 禁忌对象及禁忌表

本算法采用状态的变化作为禁忌对象，具体禁忌对象为一对数对 （m，n），其中m 和n 都为整数，分别对应两个不同的客户编号，且保证m 小于n。算法运行过程中，如果通过某个邻域变换规则得到了一个最优的邻域可行解，则取该邻域可行解的两个特征客户 （本算法的邻域变换规则都是基于两个客户作变化的，所以该两个客户就是特征客户）的编号作为m 和n，然后把 （m，n）作为禁忌对象加入禁忌表，在以后的一段时间内，尽量避免再次对 （m，n）这两个客户进行变换。

本算法采用的禁忌表是一个先进先出队列 （FIFO），最早进入禁忌表的禁忌对象在禁忌表长度超过限制时就会被最先清除出禁忌表。

禁忌长度是影响禁忌搜索算法质量的一个很重要的因素。对于不同的数据，用相同的禁忌长度进行禁忌搜索，其运算结果的质量可能会相差很大。如果要选择合适的禁忌长度，通常需要研究数据的地理特点和时间窗特点，并经过多次的测试才能确定。

为了避免单一禁忌长度的缺陷，本算法采用多禁忌长度反复迭代的方法，即设定8个禁忌长度：20、40、80、160、320、640、1280、2560，然后分别按照这8个禁忌长度运行8次禁忌搜索算法，取最优的结果作为最终结果。

2.3 解的表示方法

算法采用一个链表来代表解中的一条路径，链表里存储着的整数代表着该路径经过的客户的编号。对于一个m－OVRPTW 问题，一共有m 条路径，所以一个可行解就由m 个这样的链表组成的数据结构来表示。本算法采用空解作为初始解，即不采用其它特定算法来生成初始解，初始解中每条路径中只有一个元素：车场结点。

2.4 终止准则

本算法采用如下的终止准则：当算法的迭代次数大于某一预先设定的值时，则停止搜索，结束算法，这有利于平衡算法的搜索质量和算法的运行时间。

3 实验与数据分析

3.1 Solomon基准测试数据

由于到目前为止，还没有m－OVRPTW 问题的权威数据，考虑到m－OVRPTW 问题和VPRTW 问题的相似性，本文的实验数据使用基于VRPTW 问题的Solomon基准测试数据［12］（Solomon’s VRPTW benchmark problem），它在VRPTW 问题的研究中具有很高的地位。

Solomon基准测试数据总共有6类56组测试数据，见表2。其中R 类数据 （R1和R2）的地理坐标是由服从均匀分布的伪随机数产生，因此R 类数据的点坐标是随机分布的；对于C类数据 （C1和C2），首先将客户点分组，每组的点坐标由服从均匀分布的伪随机数产生，因此C 类数据的组内客户是聚集性的；而对于RC 类数据 （RC1和RC2）则是将部分客户点分组，每组的点的坐标由服从均匀分布的伪随机数产生，其余所有的客户点的坐标都由服从均匀分布的伪随机数产生，所以RC 类的客户坐标既有随机的特点又有聚集的特点。每一类数据包含了若干组测试数据，不同组的数据的时间窗位置和时间窗宽度也各不相同。

表2 Solomon基准测试数据的特点

另外R1类，C1类，RC1类数据被设计成允许每辆车辆只服务少量客户 （大约5～10 个客户），而R2 类，C2类，RC2类数据则被设计成允许每辆车辆服务多于30 个客户。

3.2 Solomon基准测试数据的已知最优车辆数目

由于Solomon基准测试数据是基于VRPTW 问题的，并没有m－OVRPTW 问题所需的车辆数目信息，所以本文采用了Solomon基准测试数据基于VRPTW 问题的已知最优结果［13］中的车辆数目作为本文m－OVRPTW 问题的车辆数目的数据来源。由于OVRPTW 问题不需要车辆完成任务后返回车场，比VRPTW 问题少了返回车场的要求，所以对于同样的Solomon基准测试数据，VRPTW 问题的最优车辆数目会是OVRPTW 问题最优车辆数目的下界［14］。因此取用Solomon基准测试数据基于VRPTW 问题的已知最优车辆数目作为本文的车辆数据，可以更有效地检验算法的效率和搜索质量。

3.3 运算结果

本文的运算结果是在以下计算机系统下运算所得：程序是在Visual C＋＋6.0上编译生成；CPU 为AMD Athlon 64＊2Dual 4000＋2.1GHz；内存为1024MB；32位的Windows XP操作系统。其中参数设置如下：迭代次数为1000000次；邻域集的大小为100。

表3到表8分别为R1，C1，RC1，R2，C2，RC2六类数据使用本文的算法运算出来的结果 （详细实验结果见附录B）。其中的 “最优结果”是指使用8个禁忌长度分别运算后选取其中最优的结果。“平均结果”是指使用8个禁忌长度分别运算后的平均结果。而 “车辆数量”是Solomon基准测试数据基于VRPTW 问题的已知最优车辆数目。每组数据的运算时间大概为10－20分钟。

分析表3可以得出，R1 类12 组数据的最优结果都能达到100个受服务客户，其中大部分数据的平均结果高于98个客户，平均结果最低的R112数据也有96.75个客户受服务。

表3 R1类数据运算结果

分析表4可以得出，C1类9组数据的最优结果都能达到100个受服务客户，而且平均结果也全部达到100个受服务客户。

分析表5可以得出，RC1类8组数据的最优结果都达到100个受服务客户。平均结果最高的是RC107数据，受服务客户数是99.88个。而平均结果最低的RC106数据也达到96.5个受服务客户。

分析表6可以得出，R2 类11 组数据的最优结果都达到100个受服务客户，其中7组数据的平均结果能达到100个受服务客户，平均结果最低的R207数据也达到98.25个受服务客户。

表4 C1类数据运算结果

表5 RC1类数据运算结果

表6 R2类数据运算结果

分析表7可以得出，C2类8组数据的最优结果都达到100个受服务客户，而且平均结果也全部达到100个受服务客户。

表7 C2类数据运算结果

分析表8可以得出，RC2类8组数据的最优运算结果都能达到100个受服务客户，其中有6组数据的平均结果达到100个受服务客户，平均结果最低的RC202数据也有98.63个客户得到服务。

表8 RC2类数据运算结果

从以上的实验结果可以得出，本算法对所有56组数据的最优结果都能达到100个受服务客户，而且超过50%数据的平均结果也能达到100个受服务客户，平均结果最低的RC106数据也有96.5个平均受服务客户，这表明本算法求解m－OVRPTW 问题能力很强。本算法运算出来的56组结果的最少车辆数目都达到Solomon 基准测试数据在VRPTW 问题中的最优结果的车辆数目，这表明本算法运算出来的56组结果达到了最优解的下界。但由于枚举这些数据的全部搜索空间需要极多时间，因此不能证明这56组结果就是全局最优解。

3.4 结果对比

Repoussis PP等提出了一种解决OVRPTW 问题的贪心策略向前看路径构建启发式算法 （greedy look－ahead route construction heuristic algorithm，GLRCH），而且给出了GLRCH 算法在Solomon 基准测试数据上的运行结果，并对比了I1算法和IMPACT 算法的结果。其中I1算法和IMPACT 算法本来是基于VRPTW 问题的算法，进行的结果对比中，已经对I1算法和IMPACT 算法作了适当的修改以使它们适应OVRPTW 问题的开放性特点，并保留了原始算法的特性。图3，图4 对比了本文算法的运算结果和Repoussis PP等提出的GLRCH 算法、IMPACT 算法、I1算法3种算法给出的R1类和RC1类结果。其中NV 表示能使全部100个客户得到服务的最小车辆数量，TD 表示在NV 辆车的情况下的车辆最小总行程。

图3 本文算法对比其它算法在R1类数据NV中的结果

图4 本文算法对比其它算法在R1类数据中的TD结果

分析图3，图4可以得出，R1类12组结果本算法有8组结果的车辆数目比其它算法结果要少1辆以上，特别是R110数据中，本算法得出的车辆数目比其它3种算法都要少了2 辆。而对于另外4 组数据 （R101，R103，R105，R106），运算结果车辆数目跟其它算法最少车辆数目相同，但本算法运算结果车辆总行程都大幅少于其它算法结果。

图5，图6对比了本文算法与GLRCH 算法、IMPACT算法、I1算法中6类数据的统计结果。其中ANV 表示能使全部100个客户得到服务的最小车辆数量的平均值，ATD表示车辆最小总行程的平均值。

图5 本文算法对比其它算法在6类数据中ANV的结果

图6 本文算法对比其它算法在6类数据中ADT的结果

分析图5，图6可以得出，6类数据中，本算法有5类的结果的平均车辆数目比其它算法要少。而对于C1 类结果，本算法跟其它算法都是平均需要10辆车，但本算法的平均车辆总行程比其它算法要少290个单位以上。

从以上结果可以得出，对于GLRCH 算法、IMPACT算法、I1算法的所有结果，本文算法运算结果都要比其要好，这表明本文算法的运算结果是非常优秀的。

本算法是解决m－OVRPTW 问题的算法，通过反复选取车辆数量m，也能解决OVRPTW 问题。而且通过实验结果对比可以发现，这种方法得出来的结果比GLRCH 算法、IMPACT 算法、I1算法中直接求解OVRPTW 问题的算法还要优秀。

4 结束语

m－OVRPTW 问题是一个新的OVRP 问题分支，本文为这个新问题提出了多禁忌长度，针对m－OVRPTW 问题的4种邻域变换规则的禁忌搜索算法。在Solomon基准测试数据中，本文算法运算结果达到了全部56组数据的最优解下界。本文算法虽然是针对m－OVRPTW 问题，但通过反复选取车辆数量，多次求解m－OVRPTW 问题，也能解决OVRPTW 问题。而且通过实验发现，利用本文算法求解出来的结果的质量较大幅度优于GLRCH、IMPACT、I1等3种针对OVRPTW 问题的算法。

［1］CHEN Yiqun，MOU Laiyan，CHEN Guoming，et al.A path open vehicle to limit the number of accelerated algorithm of［J］.Computer Engineering，2012，38 （24）：96－98 （in Chinese）.［陈忆群，牟来彦，陈国明，等.有数量限制的开放式车辆路径加速算法［J］.计算机工程，2012，38 （24）：96－98.］

［2］Fu Z，Wright M.Train plan model for the british rail freight services through the channel tunnel［J］.Journal of the Operational Research Society，2011，45 （4）：384－391.

［3］Li LYO，Fu Z.The school bus routing problem：A case study［J］.Journal of the Operational Research Society，2012，53（10）：552－558.

［4］Sariklis D，Powell S.A heuristic method for the open vehicle routing problem ［J］.Journal of the Operational Research Society，2012，51 （2）：564－573.

［5］Tarantilis CD，Diakoulaki D，Kiranoudis CT.Combination of geographical information system and effective routing algorithms for real life distribution operations［J］.European Journal of Operational Research，2011，152 （7）：437－453

［6］SUN Guohua.Open with time windows vehicle routing problem model and algorithm of ［J］.System Engineering Theory ＆Practice，2012，41 （8）：163－169 （in Chinese）.［孙国华.带时间窗的开放式满载车辆路径问题建模及其求解算法 ［J］.系统工程理论与实践，2012，41 （8）：163－169.］

［7］LI Sanbin，WANG Liming.Solution of the OVRPTW multi start tabu search algorithm for the ［J］.Computer Engineering，2011，37 （6）：142－147 （in Chinese）. ［李三彬，王黎明.求解OVRPTW 的多开始禁忌搜索算法 ［J］.计算机工程，2011，37 （6）：142－147.］

［8］Russell R，Chiang WC，Zepeda D.Integrating multi－product production and distribution in newspaper logistics ［J］.Computers ＆Operations Research，2008，35 （9）：1576－1588.

［9］Repoussis PP，Tarantilis CD，Ioannou G.The open vehicle routing problem with time windows ［J］.The Journal of the Operational Research Society，2007，58 （3）：355－367.

［10］CHAI Yumei.Study on open vehicle routing problem ［J］.Split Demand of Computer Engineering，2011，37 （6）：106－111 （in Chinese）.［柴玉梅.需求可拆分的开放式车辆路径问题研究 ［J］.计算机工程，2011，37 （6）：106－111.］

［11］PAN Lijun，FU Zhuo，LIU Ximei.Open vehicle routing problem with working time and the time window ［J］.Computer Engineering，2012，38 （4）：120－125 （in Chinese）. ［潘立军，符卓，刘喜梅.带工作时间与时间窗的开放式车辆路径问题［J］.计算机工程.2012，38 （4）：120－125.

［12］ZHONG Shiquan，DU Gang，HE Guoguang.Open vehicle routing problem with time window and its genetic algorithm［J］.Engineering and Computer Applications，2012，42（34）：201－204 （in Chinese）.［钟石泉，杜纲，贺国光.有时间窗的开放式车辆路径问题及其遗传算法 ［J］.计算机工程与应用，2012，42 （34）：201－204.］

［13］SUN Bo，WEI Ming，YAO Juan.Collaborative vehicle route problem of vehicle based on mission reliability ［J］.Application of Computer，2013，41 （8）：109－112 （in Chinese）.［孙博，魏明，姚娟.基于车辆任务可靠性的协同车辆路径问题 ［J］.计算机应用研究，2013，41 （8）：109－112.］

［14］YE Dongfen，FAN Wei，YANG Caiyun.The solution for vehicle path problem with constraints ［J］.Digital Technology and Application，2013，32 （11）：76－79 （in Chinese）.［叶冬芬，范伟，杨彩云.有能力约束车辆路径问题的求解算法研究 ［J］.数字技术与应用，2013，32 （11）：76－79.］