基于禁忌搜索算法的線路規劃方案求解

廖大強，鄔依林，印 鑒

（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.］