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

廖大強(qiáng)，鄔依林，印 鑒

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

0 引 言

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

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

另外，通過枚舉m－OVRPTW 問題的車輛數(shù)并求解m－OVRPTW 問題，也能解決OVRPTW 問題，這也是研究m－OVRPTW 問題的重要意義之一。m－OVRPTW 問題可以轉(zhuǎn)化為廣義多約束的背包問題，由于背包問題已被驗(yàn)證為NP－Hard難題，所以m－OVRPTW 問題也是NP－Hard 難題，使用高效的近似算法來解決m－OVRPTW 問題是一個(gè)很好的研究方向。

1 問題的描述

1.1 符號(hào)說明

首先引入兩個(gè)0－1決策變量

模型使用到的記號(hào)：V 表示車輛的集合；L 表示客戶的集合并上車場(chǎng)的集合，其中編號(hào)為1的是車場(chǎng)，編號(hào)為2到｜L｜的是客戶。m 是問題給定的車輛數(shù)量；λ是一個(gè)大系數(shù)，用來保證第一個(gè)目標(biāo)先于第二個(gè)目標(biāo)被考慮；η是一個(gè)大系數(shù)，用來實(shí)現(xiàn)式 （10）、式 （11）的條件選擇。dij表示從點(diǎn)i到點(diǎn)j 的距離

1.2 數(shù)學(xué)模型

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

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

約束條件

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

1.3 禁忌搜索簡(jiǎn)介

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

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

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

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

2.1 鄰域變換規(guī)則

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

圖2 新結(jié)點(diǎn)插入規(guī)則

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

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

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

2.2 禁忌對(duì)象及禁忌表

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

本算法采用的禁忌表是一個(gè)先進(jìn)先出隊(duì)列 （FIFO），最早進(jìn)入禁忌表的禁忌對(duì)象在禁忌表長(zhǎng)度超過限制時(shí)就會(huì)被最先清除出禁忌表。

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

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

2.3 解的表示方法

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

2.4 終止準(zhǔn)則

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

3 實(shí)驗(yàn)與數(shù)據(jù)分析

3.1 Solomon基準(zhǔn)測(cè)試數(shù)據(jù)

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

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

表2 Solomon基準(zhǔn)測(cè)試數(shù)據(jù)的特點(diǎn)

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

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

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

3.3 運(yùn)算結(jié)果

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

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

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

表3 R1類數(shù)據(jù)運(yùn)算結(jié)果

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

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

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

表4 C1類數(shù)據(jù)運(yùn)算結(jié)果

表5 RC1類數(shù)據(jù)運(yùn)算結(jié)果

表6 R2類數(shù)據(jù)運(yùn)算結(jié)果

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

表7 C2類數(shù)據(jù)運(yùn)算結(jié)果

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

表8 RC2類數(shù)據(jù)運(yùn)算結(jié)果

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

3.4 結(jié)果對(duì)比

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

m－OVRPTW 問題是一個(gè)新的OVRP 問題分支，本文為這個(gè)新問題提出了多禁忌長(zhǎng)度，針對(duì)m－OVRPTW 問題的4種鄰域變換規(guī)則的禁忌搜索算法。在Solomon基準(zhǔn)測(cè)試數(shù)據(jù)中，本文算法運(yùn)算結(jié)果達(dá)到了全部56組數(shù)據(jù)的最優(yōu)解下界。本文算法雖然是針對(duì)m－OVRPTW 問題，但通過反復(fù)選取車輛數(shù)量，多次求解m－OVRPTW 問題，也能解決OVRPTW 問題。而且通過實(shí)驗(yàn)發(fā)現(xiàn)，利用本文算法求解出來的結(jié)果的質(zhì)量較大幅度優(yōu)于GLRCH、IMPACT、I1等3種針對(duì)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］.計(jì)算機(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）.［孫國華.帶時(shí)間窗的開放式滿載車輛路徑問題建模及其求解算法 ［J］.系統(tǒng)工程理論與實(shí)踐，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］.計(jì)算機(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］.計(jì)算機(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）. ［潘立軍，符卓，劉喜梅.帶工作時(shí)間與時(shí)間窗的開放式車輛路徑問題［J］.計(jì)算機(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）.［鐘石泉，杜綱，賀國光.有時(shí)間窗的開放式車輛路徑問題及其遺傳算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，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）.［孫博，魏明，姚娟.基于車輛任務(wù)可靠性的協(xié)同車輛路徑問題 ［J］.計(jì)算機(jī)應(yīng)用研究，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ù)字技術(shù)與應(yīng)用，2013，32 （11）：76－79.］