廖大強，鄔依林，印 鑒

（1.中山大學 信息科學與技術學院，廣東 廣州510507；2.南華工商學院，廣東 廣州510507；3.廣東第二師范學院 計算機科學系，廣東 廣州510310；4.中山大學 信息科學與技術學院，廣東 廣州510275）

0 引 言

有時間窗和車輛限制的開放式車輛線路問題 （open vehicle routing problem with time window and vehicle limits，m－OVRPTW）主要應用在鐵路運輸、公共交通、航空運輸?shù)阮I域［1］。對此，F(xiàn)u 和Wright研究了一個實際案例［2］：英國鐵路為過海峽隧道的貨物提供運輸服務，案例提供了起始地和目的地的信息和火車運力等資料，要求設計方案使得火車通過隧道的次數(shù)最少、運輸?shù)穆烦套疃獭④囕v的編組最少。對于運輸部門，車輛資源通常是有限的。在車輛數(shù)量受到約束的情況下，使最多客戶的需求得到滿足，就成了這些部門最重要的目標。同時考慮到運輸成本，在滿足同等客戶的情況下，使總運輸路程最少成了另一個重要目標。所以m－OVRPTW 問題具有重要的現(xiàn)實意義。

雖然OVRPTW 問題有不少實際應用的案例，但到目前為止，研究OVRPTW 問題的文獻卻不多，而研究m－OVRPTW 問題的文獻更是難以找到。文獻［3］給出了OVRPTW 問題的綜述，并提出一種啟發(fā)式算法，采用Solomon基準測試數(shù)據(jù)［4］和Homberger的大型數(shù)據(jù)集［5］，對比了該算法與其它幾種算法的結果；文獻［6］研究了一個報紙分派的案例，把該案例建模成一個帶區(qū)域限制的OVRPTW 問題，并提出了一種禁忌搜索算法對該案例進行求解；文獻［7］針對OVRPTW 問題設計一種遺傳算法，對一個隨機數(shù)據(jù)集進行了測試并給出了運算結果。

另外，通過枚舉m－OVRPTW 問題的車輛數(shù)并求解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 是問題給定的車輛數(shù)量；λ是一個大系數(shù)，用來保證第一個目標先于第二個目標被考慮；η是一個大系數(shù)，用來實現(xiàn)式 （10）、式 （11）的條件選擇。dij表示從點i到點j 的距離

1.2 數(shù)學模型

本文將研究有時間窗和車輛限制的開放式車輛線路問題，它是一類特殊的開放性車輛線路問題 （OVRP）。它規(guī)定有一個存有貨物的車場 （depot），通過m 輛車輛 （vehicle）把貨物配送到若干客戶 （customer）里?？蛻襞c客戶之間的距離和行程時間、客戶和車場之間的距離和行程時間、客戶的貨物需求量、每個客戶可接受服務的時間窗（開始時間和截止時間）、每個客戶的服務時間長度、車輛的數(shù)量、每輛車輛的最大貨物容量都是已知的。車輛從車場出發(fā)，一個接一個地配送貨物給客戶，每個客戶至多被配送一次。在截止時間之內，車輛的派送到達，如果過早的話，那么車輛將會等待。車輛所載貨物總量不能大于其容量，每次服務完一個客戶后，車中的貨物量等于服務前的貨物量減去該客戶的貨物需求［8］。

m－OVRPTW 問題跟一般的車輛線路問題 （VRP）不同的是，它不要求車輛完成所有客戶的配送后要回到車場，車輛在最后一個客戶的服務完成后就結束任務，可以自由選擇停泊的地方，而且m－OVRPTW 問題限定了只能使用m 輛車輛配送貨物。問題的首要目標是使盡可能多的客戶得到服務，第二目標是所有車輛的總路程盡可能短［9］。下面是數(shù)學模型的目標函數(shù)

約束條件

式 （3）目標函數(shù)的第一部分乘以一個大系數(shù)λ，保證了客戶數(shù)量這個第一目標要優(yōu)先考慮，只有當車輛數(shù)目相同的情況下再考慮車輛總路程的第二目標。式 （4）是m－OVRPTW 問題特有的車輛數(shù)量限制，限定只有m 輛車進行配送。式 （5）、式 （6）保證每個客戶點最多只能被訪問一次。式 （7）保證每車輛的行駛路線是連續(xù)的。式 （8）保證每輛車的運行路線中不會存在環(huán)。式 （9）保證車輛配送的貨物總量不會超過車輛的容量。式 （10）、式 （11）保證車輛的離開時刻、到達時刻和兩點間的行程時間，這三者滿足時間約束要求。其中使用大系數(shù)η把帶有條件選擇的非線性約束，轉變成線性約束。

1.3 禁忌搜索簡介

禁忌搜索 （Tabu search）算法是局部鄰域搜索算法的推廣，Glover在1986年首次提出這一概念，并形成一套完整的算法［10］。禁忌搜索算法跟一般局部搜索算法不同的是利用了禁忌表來記錄最近遇到的局部最優(yōu)解，然后通過查詢禁忌表來避免重復搜索以前已經(jīng)搜索的狀態(tài)，從而跳出局部最優(yōu)解，搜索更多的狀態(tài)空間［11］。禁忌搜索算法的一般流程如圖1所示。

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

2 禁忌搜索算法在線路規(guī)劃中的應用

本文提出一種基于禁忌搜索框架的算法來解決m－OVRPTW 問題，通過改進的局部搜索方法，快速得到m－OVRPTW 問題的高質量近似解。

2.1 鄰域變換規(guī)則

由于禁忌搜索是局部鄰域搜索的擴展，鄰域的變換規(guī)則決定了鄰域解的分布和質量，而且變換規(guī)則的選取既影響算法的爬山能力又影響了算法跳出局部解的能力，因此鄰域變換規(guī)則是影響禁忌搜索質量和效率的一個重要因素。為了提高解的質量，本算法引入了以下幾種鄰域變換規(guī)則：選取一個不在當前解內的結點x，然后再選取當前解中的一個結點b（結點b可以是車場），在結點b后插入結點x，如圖2所示。這個變換規(guī)則，可以使得更多的結點加入到當前解中，它可以快速提高當前解的質量，是最重要的變換規(guī)則。

圖2 新結點插入規(guī)則

“當前解結點插入規(guī)則”與 “新結點插入規(guī)則”本質上都是結點插入變換，但由于 “新結點插入規(guī)則”涉及到新結點的加入，可以更有效地提高解的質量，而 “當前解結點插入規(guī)則”并沒有增加當前解的總客戶數(shù)，所以本文將他們區(qū)分開來，并在鄰域搜索中給予分配獨立的發(fā)生概率。

變換規(guī)則的發(fā)生概率見表1，4種變換規(guī)則的發(fā)生概率都設為25%，而對于有內部分類的規(guī)則 （當前解結點插入規(guī)則和結點交換規(guī)則），其內部分類按等概率處理。

表1 4種變換規(guī)則的發(fā)生概率/%

2.2 禁忌對象及禁忌表

本算法采用狀態(tài)的變化作為禁忌對象，具體禁忌對象為一對數(shù)對 （m，n），其中m 和n 都為整數(shù)，分別對應兩個不同的客戶編號，且保證m 小于n。算法運行過程中，如果通過某個鄰域變換規(guī)則得到了一個最優(yōu)的鄰域可行解，則取該鄰域可行解的兩個特征客戶 （本算法的鄰域變換規(guī)則都是基于兩個客戶作變化的，所以該兩個客戶就是特征客戶）的編號作為m 和n，然后把 （m，n）作為禁忌對象加入禁忌表，在以后的一段時間內，盡量避免再次對 （m，n）這兩個客戶進行變換。

本算法采用的禁忌表是一個先進先出隊列 （FIFO），最早進入禁忌表的禁忌對象在禁忌表長度超過限制時就會被最先清除出禁忌表。

禁忌長度是影響禁忌搜索算法質量的一個很重要的因素。對于不同的數(shù)據(jù)，用相同的禁忌長度進行禁忌搜索，其運算結果的質量可能會相差很大。如果要選擇合適的禁忌長度，通常需要研究數(shù)據(jù)的地理特點和時間窗特點，并經(jīng)過多次的測試才能確定。

為了避免單一禁忌長度的缺陷，本算法采用多禁忌長度反復迭代的方法，即設定8個禁忌長度：20、40、80、160、320、640、1280、2560，然后分別按照這8個禁忌長度運行8次禁忌搜索算法，取最優(yōu)的結果作為最終結果。

2.3 解的表示方法

算法采用一個鏈表來代表解中的一條路徑，鏈表里存儲著的整數(shù)代表著該路徑經(jīng)過的客戶的編號。對于一個m－OVRPTW 問題，一共有m 條路徑，所以一個可行解就由m 個這樣的鏈表組成的數(shù)據(jù)結構來表示。本算法采用空解作為初始解，即不采用其它特定算法來生成初始解，初始解中每條路徑中只有一個元素：車場結點。

2.4 終止準則

本算法采用如下的終止準則：當算法的迭代次數(shù)大于某一預先設定的值時，則停止搜索，結束算法，這有利于平衡算法的搜索質量和算法的運行時間。

3 實驗與數(shù)據(jù)分析

3.1 Solomon基準測試數(shù)據(jù)

由于到目前為止，還沒有m－OVRPTW 問題的權威數(shù)據(jù)，考慮到m－OVRPTW 問題和VPRTW 問題的相似性，本文的實驗數(shù)據(jù)使用基于VRPTW 問題的Solomon基準測試數(shù)據(jù)［12］（Solomon’s VRPTW benchmark problem），它在VRPTW 問題的研究中具有很高的地位。

Solomon基準測試數(shù)據(jù)總共有6類56組測試數(shù)據(jù)，見表2。其中R 類數(shù)據(jù) （R1和R2）的地理坐標是由服從均勻分布的偽隨機數(shù)產生，因此R 類數(shù)據(jù)的點坐標是隨機分布的；對于C類數(shù)據(jù) （C1和C2），首先將客戶點分組，每組的點坐標由服從均勻分布的偽隨機數(shù)產生，因此C 類數(shù)據(jù)的組內客戶是聚集性的；而對于RC 類數(shù)據(jù) （RC1和RC2）則是將部分客戶點分組，每組的點的坐標由服從均勻分布的偽隨機數(shù)產生，其余所有的客戶點的坐標都由服從均勻分布的偽隨機數(shù)產生，所以RC 類的客戶坐標既有隨機的特點又有聚集的特點。每一類數(shù)據(jù)包含了若干組測試數(shù)據(jù)，不同組的數(shù)據(jù)的時間窗位置和時間窗寬度也各不相同。

表2 Solomon基準測試數(shù)據(jù)的特點

另外R1類，C1類，RC1類數(shù)據(jù)被設計成允許每輛車輛只服務少量客戶 （大約5～10 個客戶），而R2 類，C2類，RC2類數(shù)據(jù)則被設計成允許每輛車輛服務多于30 個客戶。

3.2 Solomon基準測試數(shù)據(jù)的已知最優(yōu)車輛數(shù)目

由于Solomon基準測試數(shù)據(jù)是基于VRPTW 問題的，并沒有m－OVRPTW 問題所需的車輛數(shù)目信息，所以本文采用了Solomon基準測試數(shù)據(jù)基于VRPTW 問題的已知最優(yōu)結果［13］中的車輛數(shù)目作為本文m－OVRPTW 問題的車輛數(shù)目的數(shù)據(jù)來源。由于OVRPTW 問題不需要車輛完成任務后返回車場，比VRPTW 問題少了返回車場的要求，所以對于同樣的Solomon基準測試數(shù)據(jù)，VRPTW 問題的最優(yōu)車輛數(shù)目會是OVRPTW 問題最優(yōu)車輛數(shù)目的下界［14］。因此取用Solomon基準測試數(shù)據(jù)基于VRPTW 問題的已知最優(yōu)車輛數(shù)目作為本文的車輛數(shù)據(jù)，可以更有效地檢驗算法的效率和搜索質量。

3.3 運算結果

本文的運算結果是在以下計算機系統(tǒng)下運算所得：程序是在Visual C＋＋6.0上編譯生成；CPU 為AMD Athlon 64＊2Dual 4000＋2.1GHz；內存為1024MB；32位的Windows XP操作系統(tǒng)。其中參數(shù)設置如下：迭代次數(shù)為1000000次；鄰域集的大小為100。

表3到表8分別為R1，C1，RC1，R2，C2，RC2六類數(shù)據(jù)使用本文的算法運算出來的結果 （詳細實驗結果見附錄B）。其中的 “最優(yōu)結果”是指使用8個禁忌長度分別運算后選取其中最優(yōu)的結果。“平均結果”是指使用8個禁忌長度分別運算后的平均結果。而 “車輛數(shù)量”是Solomon基準測試數(shù)據(jù)基于VRPTW 問題的已知最優(yōu)車輛數(shù)目。每組數(shù)據(jù)的運算時間大概為10－20分鐘。

分析表3可以得出，R1 類12 組數(shù)據(jù)的最優(yōu)結果都能達到100個受服務客戶，其中大部分數(shù)據(jù)的平均結果高于98個客戶，平均結果最低的R112數(shù)據(jù)也有96.75個客戶受服務。

表3 R1類數(shù)據(jù)運算結果

分析表4可以得出，C1類9組數(shù)據(jù)的最優(yōu)結果都能達到100個受服務客戶，而且平均結果也全部達到100個受服務客戶。

分析表5可以得出，RC1類8組數(shù)據(jù)的最優(yōu)結果都達到100個受服務客戶。平均結果最高的是RC107數(shù)據(jù)，受服務客戶數(shù)是99.88個。而平均結果最低的RC106數(shù)據(jù)也達到96.5個受服務客戶。

分析表6可以得出，R2 類11 組數(shù)據(jù)的最優(yōu)結果都達到100個受服務客戶，其中7組數(shù)據(jù)的平均結果能達到100個受服務客戶，平均結果最低的R207數(shù)據(jù)也達到98.25個受服務客戶。

表4 C1類數(shù)據(jù)運算結果

表5 RC1類數(shù)據(jù)運算結果

表6 R2類數(shù)據(jù)運算結果

分析表7可以得出，C2類8組數(shù)據(jù)的最優(yōu)結果都達到100個受服務客戶，而且平均結果也全部達到100個受服務客戶。

表7 C2類數(shù)據(jù)運算結果

分析表8可以得出，RC2類8組數(shù)據(jù)的最優(yōu)運算結果都能達到100個受服務客戶，其中有6組數(shù)據(jù)的平均結果達到100個受服務客戶，平均結果最低的RC202數(shù)據(jù)也有98.63個客戶得到服務。

表8 RC2類數(shù)據(jù)運算結果

從以上的實驗結果可以得出，本算法對所有56組數(shù)據(jù)的最優(yōu)結果都能達到100個受服務客戶，而且超過50%數(shù)據(jù)的平均結果也能達到100個受服務客戶，平均結果最低的RC106數(shù)據(jù)也有96.5個平均受服務客戶，這表明本算法求解m－OVRPTW 問題能力很強。本算法運算出來的56組結果的最少車輛數(shù)目都達到Solomon 基準測試數(shù)據(jù)在VRPTW 問題中的最優(yōu)結果的車輛數(shù)目，這表明本算法運算出來的56組結果達到了最優(yōu)解的下界。但由于枚舉這些數(shù)據(jù)的全部搜索空間需要極多時間，因此不能證明這56組結果就是全局最優(yōu)解。

3.4 結果對比

Repoussis PP等提出了一種解決OVRPTW 問題的貪心策略向前看路徑構建啟發(fā)式算法 （greedy look－ahead route construction heuristic algorithm，GLRCH），而且給出了GLRCH 算法在Solomon 基準測試數(shù)據(jù)上的運行結果，并對比了I1算法和IMPACT 算法的結果。其中I1算法和IMPACT 算法本來是基于VRPTW 問題的算法，進行的結果對比中，已經(jīng)對I1算法和IMPACT 算法作了適當?shù)男薷囊允顾鼈冞m應OVRPTW 問題的開放性特點，并保留了原始算法的特性。圖3，圖4 對比了本文算法的運算結果和Repoussis PP等提出的GLRCH 算法、IMPACT 算法、I1算法3種算法給出的R1類和RC1類結果。其中NV 表示能使全部100個客戶得到服務的最小車輛數(shù)量，TD 表示在NV 輛車的情況下的車輛最小總行程。

圖3 本文算法對比其它算法在R1類數(shù)據(jù)NV中的結果

圖4 本文算法對比其它算法在R1類數(shù)據(jù)中的TD結果

分析圖3，圖4可以得出，R1類12組結果本算法有8組結果的車輛數(shù)目比其它算法結果要少1輛以上，特別是R110數(shù)據(jù)中，本算法得出的車輛數(shù)目比其它3種算法都要少了2 輛。而對于另外4 組數(shù)據(jù) （R101，R103，R105，R106），運算結果車輛數(shù)目跟其它算法最少車輛數(shù)目相同，但本算法運算結果車輛總行程都大幅少于其它算法結果。

圖5，圖6對比了本文算法與GLRCH 算法、IMPACT算法、I1算法中6類數(shù)據(jù)的統(tǒng)計結果。其中ANV 表示能使全部100個客戶得到服務的最小車輛數(shù)量的平均值，ATD表示車輛最小總行程的平均值。

圖5 本文算法對比其它算法在6類數(shù)據(jù)中ANV的結果

圖6 本文算法對比其它算法在6類數(shù)據(jù)中ADT的結果

分析圖5，圖6可以得出，6類數(shù)據(jù)中，本算法有5類的結果的平均車輛數(shù)目比其它算法要少。而對于C1 類結果，本算法跟其它算法都是平均需要10輛車，但本算法的平均車輛總行程比其它算法要少290個單位以上。

從以上結果可以得出，對于GLRCH 算法、IMPACT算法、I1算法的所有結果，本文算法運算結果都要比其要好，這表明本文算法的運算結果是非常優(yōu)秀的。

本算法是解決m－OVRPTW 問題的算法，通過反復選取車輛數(shù)量m，也能解決OVRPTW 問題。而且通過實驗結果對比可以發(fā)現(xiàn)，這種方法得出來的結果比GLRCH 算法、IMPACT 算法、I1算法中直接求解OVRPTW 問題的算法還要優(yōu)秀。

4 結束語

m－OVRPTW 問題是一個新的OVRP 問題分支，本文為這個新問題提出了多禁忌長度，針對m－OVRPTW 問題的4種鄰域變換規(guī)則的禁忌搜索算法。在Solomon基準測試數(shù)據(jù)中，本文算法運算結果達到了全部56組數(shù)據(jù)的最優(yōu)解下界。本文算法雖然是針對m－OVRPTW 問題，但通過反復選取車輛數(shù)量，多次求解m－OVRPTW 問題，也能解決OVRPTW 問題。而且通過實驗發(fā)現(xiàn)，利用本文算法求解出來的結果的質量較大幅度優(yōu)于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）.［陳憶群，牟來彥，陳國明，等.有數(shù)量限制的開放式車輛路徑加速算法［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，F(xiàn)u 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］.系統(tǒng)工程理論與實踐，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，F(xiàn)U 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）.［孫博，魏明，姚娟.基于車輛任務可靠性的協(xié)同車輛路徑問題 ［J］.計算機應用研究，2013，41 （8）：109－112.］

［14］YE Dongfen，F(xiàn)AN Wei，YANG Caiyun.The solution for vehicle path problem with constraints ［J］.Digital Technology and Application，2013，32 （11）：76－79 （in Chinese）.［葉冬芬，范偉，楊彩云.有能力約束車輛路徑問題的求解算法研究 ［J］.數(shù)字技術與應用，2013，32 （11）：76－79.］