最小-最大車輛路徑問題的禁忌搜索算法

1、最小-最大車輛路徑問題的禁忌搜索算法第25卷第1期(總第157期)2007年1月系統(tǒng)工程SystemsEngineeringV01.25.No.】Jan.2007文章編號:10014098(2007)Ol一004904最小一最大車輛路徑問題的禁忌搜索算法劉霞,齊歡(1.華中科技大學(xué)系統(tǒng)工程研究所,湖北武漢430074;2.江漢大學(xué)物理與信息工程學(xué)院,湖北武漢430056)摘要:在對最小一最大車輛路徑問題進(jìn)行描述的基礎(chǔ)上.建立了該問題的基本數(shù)學(xué)模型.針對最小一最大車輛路徑問題的目標(biāo)是最小化整個線路的最長子線路,本文提出了改進(jìn)的禁忌搜索算法.并用一些典型算例進(jìn)行了驗證.計算結(jié)果表明.用該算法求解最

2、小一最大車輛路徑問題,不僅可以取得較好的計算結(jié)果.而且算法的計算效率較高.收斂速度較快.關(guān)鍵詞:最小一最大車輛路徑問題;禁忌搜索;啟發(fā)式中圖分類號:o2l1文獻(xiàn)標(biāo)識碼:A引言車輛路徑問題(VehicleRoutingProblem,VRP)是指對一系列發(fā)貨點(或收貨點)組成適當(dāng)?shù)男熊嚶肪€,使車輛有序地通過它們,并能在滿足一定的約束條件下.達(dá)到諸如路程最短,費用最小或耗費時間盡量少等目的.該類問題具有很強的實際應(yīng)用背景.而且屬于NPhard.因此自它在1959年由Dantzig和Ramser首次提出以來就得到了專家學(xué)者的極大重視并進(jìn)行了大量的研究J.車輛路徑問題的求解方法可以分為三類:精確算法,

3、經(jīng)典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法.精確算法如樹搜索法,分枝定界法,整數(shù)線性規(guī)劃等.由于大部分實際問題都難以找到最優(yōu)解,因此這類算法往往只能用于求解小規(guī)模問題;經(jīng)典啟發(fā)式算法有節(jié)約法,構(gòu)造法,兩階段法和不完全優(yōu)化算法等;現(xiàn)代啟發(fā)式算法是近2O年發(fā)展起來的智能算法,如模擬退火算法,遺傳算法,禁忌搜索算法和蟻群優(yōu)化等.在實際情況中,存在這樣的一類車輛路徑問題.它們的基本定義和約束條件與經(jīng)典VRP一致,但目標(biāo)不是要求整個行車路線的路程最短或費用最少,而是要求整個線路中行程最長的子線路距離最短或時間最短.如出于社會因素考慮的校車行車線路制定4,郵遞員投送報紙,巡邏車隊的巡邏線路制定,緊急情況下空投物資的運

4、送等.這類問題稱為最小一最大車輛路徑問題(MinMaxVehicleRoutingProblem.MMVRP).本文將改進(jìn)的禁忌搜索算法應(yīng)用于最小.最大車輛路徑問題.并用實例進(jìn)行測試.取得了很好的效果.2最小一最大車輛路徑問題最小一最大車輛路徑問題可以描述為:有一個中心倉庫.用0表示.擁有輛相同型號的車.容量都為Q,現(xiàn)有個客戶點的運輸任務(wù)需要完成,以1.2,表示.第個客戶點的貨運量為q(=1.2,.),且maxqQ.每輛車從倉庫出發(fā).經(jīng)過一系列客戶點并裝載貨物,最終回到倉庫.規(guī)定每個客戶點的任務(wù)必須且只能由一輛車來完成.要求整個線路中行程最長的子線路長度盡可能短具體的數(shù)學(xué)模型可表示如下:目標(biāo)函

5、數(shù):2=minmax(d)+),k=l,2,re(1)=D;D約束:=0=0.1,2,=0.1.2.,(2)(3)一=0,k=o.1.2.,州;戶一1,2,.J=0i0(4)*收稿日期:2006一1029基金項目:國家自然科學(xué)基金資助項目(60574088)作者簡介:劉霞(1977一),女.華中科技大學(xué)博士研究生,江漢大學(xué)講師,研究方向:系統(tǒng)集成與優(yōu)化;齊歡,男.華中科技大學(xué)教授,博士生導(dǎo)師,研究方向:復(fù)雜系統(tǒng)建模與仿真,系統(tǒng)分析與集成.,l1=:50系統(tǒng)工程2007焦q,kQ.k一1,2,(5)f一0J一0其中,表示車輛數(shù);表示客戶數(shù);d,表示客戶到客戶的距離,若已知客戶節(jié)點的坐標(biāo),往往采用

6、Euclidean方法計算距離;q.表示客戶i的貨運量;Q表示每輛車的裝載容量;如果車輛k從客戶離開到達(dá)客戶J.為1,否則為0;表示罰值,可設(shè)為一個較大的正數(shù).約束(2)和(3)保證每個客戶點有且僅有一輛車經(jīng)過一次;約束(4)保證了子線路的連續(xù)性,即車輛到達(dá)了一個貨物點,也必須從該點離開;約束(5)為容量約束,規(guī)定了每條子線路裝載的貨物量不能超出車輛的容量.為滿足條件(5),在目標(biāo)函數(shù)中加入了罰值,即如果某條子線路裝載的貨物量超出車輛的裝載容量,目標(biāo)函數(shù)為max(d,)+M.此時M為一個很大的正數(shù),否則0=0目標(biāo)函數(shù)為max(d,),即M為0.一0J一03禁忌搜索禁忌搜索(TabuSearch

7、,TS)的思想最早由Glover(1986)提出,它是對局部搜索的一種擴展,是一種全局逐步尋優(yōu)算法,是對人類智力過程的一種模擬.TS算法通過引入一個靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索,并通過特赦準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài),進(jìn)而保證多樣化的有效探索以最終實現(xiàn)全局優(yōu)化.禁忌搜索的基本流程可描述如下:(1)給定算法參數(shù),產(chǎn)生初始解z,置禁忌表為空.(2)判斷算法終止條件是否滿足?若是.則結(jié)束算法并輸出優(yōu)化結(jié)果;否則.繼續(xù)以下步驟.(3)利用當(dāng)前解z的鄰域結(jié)構(gòu)產(chǎn)生其所有(或若干)鄰域解,并從中確定若干候選解.(4)對候選解判斷特赦準(zhǔn)則是否滿足?若成立,則用滿足特赦準(zhǔn)則的最佳狀態(tài)y替代z成

8、為新的當(dāng)前解,即,并用與Y對應(yīng)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象,同時用Y替換當(dāng)前全局最優(yōu)解,然后轉(zhuǎn)步驟(6);否則,繼續(xù)以下步驟.(5)判斷候選解對應(yīng)的各對象的禁忌屬性,選擇候選解集中非禁忌對象對應(yīng)的最佳狀態(tài)為新的當(dāng)前解,同時用與之對應(yīng)的禁忌對象替換最早進(jìn)入禁忌表的禁忌對象元素.(6)轉(zhuǎn)步驟(2).3.1初始解解采用自然數(shù)編碼,0表示車庫,其他自然數(shù)表示客戶.若有3輛車,8個客戶,則623II584II17表示三輛車的線路分別為0-6230,0-5840,0-170.禁忌搜索的初始解對結(jié)果的影響較大,本文將隨機法和節(jié)約法相結(jié)合,生成初始解.步驟如下:(1)從客戶列表中隨機選擇一個節(jié)點.作

9、為一條子線路經(jīng)過的第一個客戶節(jié)點,同時將該節(jié)點從客戶列表中刪除,并設(shè)該客戶節(jié)點為當(dāng)前節(jié)點current,此時該子線路裝載的貨物量demand一口(current),長度distance=d(depot,current)+d(current,depot).(2)若客戶列表為空,表明所有客戶節(jié)點都已被分配.初始解產(chǎn)生,結(jié)束;否則轉(zhuǎn)步驟(3).(3)以當(dāng)前節(jié)點current為基礎(chǔ),采用節(jié)約法計算子線路的下一節(jié)點.即設(shè)客戶列表中的每一個節(jié)點為下一節(jié)點next,計算將它們加入子線路后路程的增加量,一d(current,next)+d(next,depot)一d(current,depot),取出其中最小

10、者對應(yīng)的客戶節(jié)點.若增加該客戶節(jié)點后,子線路滿足容量約束,則將該節(jié)點加入子線路,同時將該節(jié)點從客戶列表中刪除,此時子線路的客戶節(jié)點數(shù)加1,裝載的貨物量demanddemand+q(current),長度distance=distance+s(current.next),用next作為新的當(dāng)前節(jié)點current,轉(zhuǎn)步驟(2);否則該子線路結(jié)束,轉(zhuǎn)步驟(4).(4)若子線路條數(shù)已達(dá)到給定的車輛數(shù)量,則將客戶列表中剩余的節(jié)點加入最后一條子線路,計算該子線路包含的客戶節(jié)點,裝載的貨物量和線路長度;否則構(gòu)造新的子線路,子線路條數(shù)加1,轉(zhuǎn)步驟(1).3.2鄰域結(jié)構(gòu)禁忌搜索算法是一種基于鄰域搜索技術(shù)的算法,

11、確定鄰域操作方法是構(gòu)造該算法的一個重要步驟.最小一最大車輛路徑問題的目標(biāo)是盡量縮短線路中最長的子線路,本文采用互換法和插入法實施鄰域操作.具體步驟如下:(1)選擇最長的子線路,稱為R1,隨機選擇其中的一個節(jié)點,稱為c1.(2)隨機選擇互換法或插入法.若為交換法,轉(zhuǎn)步驟(3);否則轉(zhuǎn)步驟(4).(3)互換法:隨機選擇另一條子線路和其中的一個節(jié)點.分別稱為R2和c2.將節(jié)點c1插入子線路R2;將c2插入子線路R1.(4)插入法:隨機選擇另一條子線路.稱為R2.將節(jié)點C1插入子線路R2.將節(jié)點插入子線路遵循的原則是:節(jié)點插入子線路的位置,應(yīng)使得子線路長度的增加值最小.3.3候選集當(dāng)問題的規(guī)模較大,當(dāng)

12、前解的鄰域數(shù)量將增大,考慮到鄰域搜索的效率,通常選取當(dāng)前解的鄰域集的一個子集作為候選集.本文設(shè)定候選集為一固定大小.3.4禁忌表禁忌的目的是為了盡量避免迂回搜索而多探索一些有效的搜索途徑,禁忌表是針對禁忌對象所設(shè)計的一種結(jié)構(gòu).本文在每次獲得新的當(dāng)前解后,取客戶節(jié)點從一條線第1期劉霞,齊歡:最小一最大車輛路徑問題的禁忌搜索算法51路到另一條線路的移動作為禁忌對象,禁忌表的長度設(shè)為一固定值.3.5特赦準(zhǔn)則在禁忌搜索算法中,可能會出現(xiàn)候選解全部被禁忌,或者存在一個優(yōu)于當(dāng)前全局最優(yōu)解的禁忌候選解,此時特赦準(zhǔn)則將使某些解解禁,以實現(xiàn)更高效的優(yōu)化性能.為了防止優(yōu)良解的遺失,本文采用最簡單且最常用的特赦準(zhǔn)則

13、,即當(dāng)某個禁忌候選解的適配值優(yōu)于當(dāng)前全局最優(yōu)值,則解禁此候選解為當(dāng)前解和當(dāng)前全局最優(yōu)解3.6終止條件由于問題的規(guī)模較大,且沒有相關(guān)的實例結(jié)果參照,本文給定最大計算時間作為終止條件,其具體大小根據(jù)問題的規(guī)模和難度而不同.3.7局部優(yōu)化每次產(chǎn)生新的當(dāng)前解,采用2-opt法對各子線路進(jìn)行局部優(yōu)化.4計算結(jié)果將本文的禁忌搜索算法應(yīng)用于Christofides,Mingozzi和Toth(CMT)E提出的算例.取其中的7個問題(問題1,2,3,4,5,11,12),如表l所示.其中表示客戶節(jié)點數(shù),表示車輛數(shù),Q表示車輛的裝載容量,Best表示在經(jīng)典的CVRP問題求解中,到目前為止得到的最佳目標(biāo)值,即整個

14、線路長度的最小值.表1算例問題QBest(CVRP)CMT一150516O524.61CMT一2751014O835.26CMT一31OO8200826.14CMT一4150l22001O28.42CMT一5l99l62001291.44CMTl1l207200i042.iiCMT一121O01O200819.56設(shè)鄰域列表大小為5O,禁忌表大小為1O.候選集大小為1O,得到結(jié)果如表2所示.其中Average(MMVRP)和Best(MMVRP)分別表示在最小一最大車輛路徑問題中,5次計算得到的目標(biāo)值(最長子線路長度)平均值和最優(yōu)值.5結(jié)論表2計算結(jié)果問題lQAverage(MMVRP)Bes

15、t(MMVRP)CMT一150516O118.769115.802CMT一275i0I401O8.3i91O6.723CMT一31OO8200116.924116.92OCMT一415O12200i07.5971O6.7l9CMT一5199162002O2.O67196.989CMTll12O7200209.397207.395CMT一121001020012O.53212O.532本文建立了最小一最大車輛路徑問題的數(shù)學(xué)模型,并提出用改進(jìn)的禁忌搜索算法對問題進(jìn)行求解,如采用隨機法和節(jié)約法相結(jié)合的方式生成初始解,既保持初始解一定的隨機性,又使其盡量合理,在鄰域結(jié)構(gòu)上,依據(jù)MMVRP的目標(biāo)對最長子

16、線路采用互換法和插入法進(jìn)行節(jié)點變換,產(chǎn)生合理的鄰域解,加快算法的收斂速度.將禁忌搜索算法應(yīng)用于經(jīng)52系統(tǒng)工程2007矩典算例,得到了較好的結(jié)果.參考文獻(xiàn):1E23334353673893李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法M.北京:中國物資出版社,2001.LaporteG,GendreauM,PotvinJY,SemetF.ClassicalandmodernheuristicsforthevehicleroutingproblemJ.InternationalTranctioninOperationalResearch,2000,(7):285300.CordeauJ-F,Lapo

17、rteG.Tabusearchheuristicsforthevehicleroutingproblem(TechnicalReportG一200215)zGroupforResearchinDecisionAnalysis(GERAD),Montreal,2002.SernaCRD,BonrostroJP.Minmaxvehicleroutingproblems:applicationtO,schooltransportintheprovinceofBurgos(Spain)A.InternationalConferenceonComputeraidedSchedulingofPublicT

18、ransportC.2000,(505):297317.王凌.智能優(yōu)化算法及應(yīng)用M.北京:清華大學(xué)出版社,2001.GoldenBL,LaporteG,TaillardE.AnadaptivememoryheuristicforaclassofvehicleroutingproblemswithminmaxobjectiveJ.Computers&OperationsResearch,1997.24(5):445452.WassanNA.Areactivetabu,searchforthevehicleroutingproblemJ.OperationalResearchSociety,2006,57(1):l11l16.ChichestofidesN,MingozziA,TothP.CombinatorialoptimizationM.Chichester:Wiley,1979.BarbarosogluG,OzgurD.Atabu.searchalgorithmforthevehicleroutingproblemJ.Computers&OperationsResearch,1999,26:25527O.TabuSearchAlgorithmofMinmaxVehicleRo