最小-最大車(chē)輛路徑問(wèn)題的禁忌搜索算法

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

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

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

4、送等.這類(lèi)問(wèn)題稱(chēng)為最小一最大車(chē)輛路徑問(wèn)題(MinMaxVehicleRoutingProblem.MMVRP).本文將改進(jìn)的禁忌搜索算法應(yīng)用于最小.最大車(chē)輛路徑問(wèn)題.并用實(shí)例進(jìn)行測(cè)試.取得了很好的效果.2最小一最大車(chē)輛路徑問(wèn)題最小一最大車(chē)輛路徑問(wèn)題可以描述為:有一個(gè)中心倉(cāng)庫(kù).用0表示.擁有輛相同型號(hào)的車(chē).容量都為Q,現(xiàn)有個(gè)客戶點(diǎn)的運(yùn)輸任務(wù)需要完成,以1.2,表示.第個(gè)客戶點(diǎn)的貨運(yùn)量為q(=1.2,.),且maxqQ.每輛車(chē)從倉(cāng)庫(kù)出發(fā).經(jīng)過(guò)一系列客戶點(diǎn)并裝載貨物,最終回到倉(cāng)庫(kù).規(guī)定每個(gè)客戶點(diǎn)的任務(wù)必須且只能由一輛車(chē)來(lái)完成.要求整個(gè)線路中行程最長(zhǎng)的子線路長(zhǎng)度盡可能短具體的數(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基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60574088)作者簡(jiǎn)介:劉霞(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其中,表示車(chē)輛數(shù);表示客戶數(shù);d,表示客戶到客戶的距離,若已知客戶節(jié)點(diǎn)的坐標(biāo),往往采用

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

7、,TS)的思想最早由Glover(1986)提出,它是對(duì)局部搜索的一種擴(kuò)展,是一種全局逐步尋優(yōu)算法,是對(duì)人類(lèi)智力過(guò)程的一種模擬.TS算法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索,并通過(guò)特赦準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài),進(jìn)而保證多樣化的有效探索以最終實(shí)現(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)對(duì)候選解判斷特赦準(zhǔn)則是否滿足?若成立,則用滿足特赦準(zhǔn)則的最佳狀態(tài)y替代z成

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

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

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

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

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

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

14、線路長(zhǎng)度的最小值.表1算例問(wèn)題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)分別表示在最小一最大車(chē)輛路徑問(wèn)題中,5次計(jì)算得到的目標(biāo)值(最長(zhǎng)子線路長(zhǎng)度)平均值和最優(yōu)值.5結(jié)論表2計(jì)算結(jié)果問(wèn)題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本文建立了最小一最大車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型,并提出用改進(jìn)的禁忌搜索算法對(duì)問(wèn)題進(jìn)行求解,如采用隨機(jī)法和節(jié)約法相結(jié)合的方式生成初始解,既保持初始解一定的隨機(jī)性,又使其盡量合理,在鄰域結(jié)構(gòu)上,依據(jù)MMVRP的目標(biāo)對(duì)最長(zhǎng)子

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