摘 要: 將蟻群優(yōu)化和變鄰域下降搜索VND相結(jié)合,形成一種混合啟發(fā)式算法ACS_VND,應(yīng)用于客運(yùn)公司的汽車調(diào)度,求解車輛需求數(shù)和最佳路徑。該算法充分利用了2種不同算法的優(yōu)點(diǎn)。實(shí)驗(yàn)結(jié)果表明,算法ACS_VND能在較短時間內(nèi)獲得比單個算法更好的車輛調(diào)度路徑。
關(guān)鍵詞: 蟻群系統(tǒng); 變鄰域下降搜索; 車輛路徑; 混合啟發(fā)式算法
車站車輛路徑問題是直接關(guān)系到客運(yùn)汽車公司的效率與效益、服務(wù)質(zhì)量和企業(yè)形象的關(guān)鍵問題,一直是運(yùn)籌學(xué)、管理學(xué)、計算機(jī)科學(xué)等領(lǐng)域的研究熱點(diǎn)問題,在生活中有著廣泛的應(yīng)用價值,如物流陪送、郵政投遞、汽車、火車和飛機(jī)的調(diào)度等。對該類問題的研究主要集中在能否找到在較短的時間內(nèi)給出較優(yōu)解的算法。自1959年Dantzig[1]提出這一問題以后,幾十年來已取得了大量的成果。Dethloff[2]提出了帶有參數(shù)的插入法,Crispim[3]提出了基于禁忌的混合啟發(fā)算法,但求解質(zhì)量還有較大的改進(jìn)空間。
蟻群優(yōu)化ACO(Ant Colony Optimization)是一種基于群體的元啟發(fā)算法,最初的靈感來源于真實(shí)的螞蟻搜尋食物的行為[4],以信息素作為媒介,間接進(jìn)行信息交換。變領(lǐng)域搜索VNS(Variable Neighborhood Search)最早由Hansen和Mladenovie[5]提出,其核心思想是:領(lǐng)域?qū)?yīng)搜索空間的拓?fù)涮匦?,不同的領(lǐng)域結(jié)構(gòu)對應(yīng)搜索空間的不同區(qū)域。一般地,問題解空間中某個區(qū)域的特性不同于其他區(qū)域,因此,動態(tài)使用不同的領(lǐng)域結(jié)構(gòu)能夠增加解的多樣性。變領(lǐng)域下降VND(Variable Neighborhood Descent)是VNS的一種變形,它通過一種確定的方式來改變領(lǐng)域結(jié)構(gòu)的使用。蟻群優(yōu)化屬于群體基于群體的算法,而變領(lǐng)域下降搜索則是屬于軌跡法?;谌后w的元啟發(fā)式算法的優(yōu)勢是善于發(fā)現(xiàn)搜索空間中可能存在最優(yōu)解的區(qū)域,而軌跡法的優(yōu)勢在于善于探索搜索空間中較好的區(qū)域[6]。因此,將二者結(jié)合可以充分利用各自的優(yōu)勢,提高算法的搜索性能和效率。本研究就是將二者進(jìn)行結(jié)合,應(yīng)用于客運(yùn)公司汽車的調(diào)度。
1 車輛路徑的描述
本研究利用有向帶權(quán)圖G描述車輛調(diào)度路徑問題。假設(shè)G=(V,A,C),其中,V={i|i=0,1,…,n}是頂點(diǎn)集(其中0表示車站調(diào)度中心,其他表示站點(diǎn));A={(i,j)|i, j∈V}是連接各頂點(diǎn)的弧集;C={cij|(i,j)∈A}是權(quán)重矩陣,cij表示從站點(diǎn)i到站點(diǎn)j的距離。任意站點(diǎn)i(i=1,2,…,n)都有一定的上車di與下車需求pi。安排車輛為所有客戶服務(wù),要求滿足以下條件并使得總行程長度最短:
(1)每輛車都從倉庫出發(fā),并最終返回倉庫。
(2)每個客戶都只被1輛車服務(wù),且僅被服務(wù)1次。
(3)任1車輛在行程過程中,載重始終不能超過Q。
設(shè)s={ri|i={1,2,…,k}}是問題的一個解,其中,ri對應(yīng)1條車輛路徑。由上面問題描述要求可以知道,s作為問題的1個可行解的重要條件是:對任意ri都滿足以下條件:
(1)ri上所有站點(diǎn)的總上車需求D(x)不超過Q。
(2)ri上所有站點(diǎn)的總下車需求P(x)不超過Q。
(3)車輛承載ri上的任何客戶之后人員都不超過Q。
若都滿足條件(1)、(2)、(3),則稱s滿足強(qiáng)可行條件,是強(qiáng)可行解;若都滿足條件(1)、(2),但不滿足條件(3),則稱s滿足弱可行性條件,是弱可行解。由Mosheiov[7]已經(jīng)證明,如果D(x)和P(x)都不超過車輛容量限制,則ri一定可以通過某種方式轉(zhuǎn)化成可行路徑。因此,若s是弱可行解,則一定可以通過某種方式轉(zhuǎn)化為強(qiáng)可行解。
2 混合啟發(fā)式算法ACS_VND
2.1 初始化信息素
首先使用最近鄰啟發(fā)式構(gòu)造一個強(qiáng)可行解s0,并且根據(jù)τ0=1/n·f(s0)設(shè)定信息素的初值,其中n是站點(diǎn)數(shù)量。則最近鄰啟發(fā)式算法構(gòu)造解的步驟如下:
(1)從尚未訪問的節(jié)點(diǎn)中選擇距離調(diào)度中心最小的站點(diǎn),開始一條新的車輛路徑r。
(2)若V0不為空,則從中選擇距離r上最后1個站點(diǎn)最近的站點(diǎn),作為下一個訪問的節(jié)點(diǎn);否則,轉(zhuǎn)步驟(1),直到所有站點(diǎn)都已經(jīng)被訪問。這里,將V0定義為尚未被訪問,且加入r后,使得r仍能約束強(qiáng)可行性條件的所有站點(diǎn)節(jié)點(diǎn)的集合。
2.2 構(gòu)建可行解
由于弱可行性條件檢查比較簡單,因此在算法ACS_VND的構(gòu)建階段,首先產(chǎn)生一組弱可行解,然后轉(zhuǎn)化成強(qiáng)可行解。在ACS_VND中應(yīng)使用一種基于插入的啟發(fā)式方法構(gòu)造弱可行解。首先,從調(diào)度中心0出發(fā),隨機(jī)選擇1個站點(diǎn),開始1條新的路徑r;然后,根據(jù)如下偽隨機(jī)比例規(guī)則:
不斷地從V1中選擇站點(diǎn),直到V1為空,結(jié)束當(dāng)前路徑r的構(gòu)造。若所有站點(diǎn)都已在當(dāng)前解中,算法結(jié)束;否則,重新開始1條新的r并重復(fù)上述構(gòu)造過程。為取得利用歷史信息和隨機(jī)選擇之間的平衡,算法ACS_VND中動態(tài)調(diào)整q0的大小,使其取值為qmax或qmin。
ACS_VND算法將弱可行解轉(zhuǎn)化為強(qiáng)可行解的過程如下:從頭到尾逐個掃描每1條路徑r上的站點(diǎn),若訪問當(dāng)前站點(diǎn)后r不能滿足強(qiáng)可行性條件,則跳過當(dāng)前站點(diǎn)掃描下一個;否則,繼續(xù)掃描下一個;最后,按照逆序?qū)⒃诘?次掃描中被跳過的站點(diǎn)逐個重新加入r,即可得到1個強(qiáng)可行解。
在求解過程中,根據(jù),利用構(gòu)造的每一個解s進(jìn)行局部信息素更新,其中,0<ρ1<1是信息素的揮發(fā)系數(shù),τ0是信息素的初值。
2.3 變鄰域下降搜索
變鄰域下降搜索的基本步驟是:從初始解出發(fā),選擇一種鄰域結(jié)構(gòu)進(jìn)行局部搜索,直到找到局部最優(yōu)解。以當(dāng)前局部最優(yōu)解為初始解,使用另一種鄰域結(jié)構(gòu)繼續(xù)進(jìn)行局部搜索。當(dāng)使用任何一種鄰域結(jié)構(gòu)都不能繼續(xù)改進(jìn)當(dāng)前解時,結(jié)束VND過程。
在使用變鄰域下降搜索之前,需要定義一組鄰域結(jié)構(gòu)。算法ACS_VND中分別使用3種求解VRP問題時常用的鄰域結(jié)構(gòu):插入(insert)、交換(swap)和2-opt。
(1)插入(insert)
(2)交換(swap)
將解s中的站點(diǎn)i和j的位置互換(i和j可屬于同一路徑,也可屬于不同路徑),產(chǎn)生新解。例如,解s=0-3-5-7-0-1-2-4-6-0,交換同一路徑上的站點(diǎn)3與7,產(chǎn)生新解s′=0-7-5-3-0-1-2-4-6-0;解s=0-3-5-7-0-1-2-4-6-0,交換不同路徑上的站點(diǎn)3與2,產(chǎn)生新解s′′=0-2-5-7-0-1-3-4-6-0。
(3)2-opt
解s同一路徑上的2個站點(diǎn)i和j,在解s中的位置分別為pi與pj(pi
j)。2-opt是指將pi+1位置上的站點(diǎn)與j交換,并將pi+1和站點(diǎn)j(不包括pi+1位置上的站點(diǎn)和站點(diǎn)j)之間的節(jié)點(diǎn)按逆序訪問。例如:解s=0-1-9-5-7-4-0-2-6-3-8-10-11-0,對2條路徑分別通過2-opt優(yōu)化后,得到新解s′=0-1-4-7-5-9-0-2-10-8-3-6-11-0。
2.4 搜索策略
3 實(shí)驗(yàn)結(jié)果與分析比較
以某長途汽車客運(yùn)公司為實(shí)驗(yàn)對象,該運(yùn)輸公司有17個站點(diǎn)(包括14個途經(jīng)站點(diǎn)和3個終點(diǎn)站),車輛都是德國產(chǎn)歐洲之星,已知各站點(diǎn)上下車客戶需求服務(wù)總量為k。為了驗(yàn)證混合啟發(fā)式算法ACS_VND的性能,將它與單獨(dú)使用ACS或 VND算法進(jìn)行了比較。除了算法不同之外,其他實(shí)驗(yàn)樣本和設(shè)置均相同,以保證實(shí)驗(yàn)不失一般性。實(shí)驗(yàn)結(jié)果如表1所示。其中,L表示最優(yōu)解得到的車輛路徑總長度;n表示所需車輛的臺數(shù)。
本實(shí)驗(yàn)結(jié)合多種元啟發(fā)方法的優(yōu)點(diǎn)和策略,設(shè)計了更有效的混合啟發(fā)式算法。結(jié)合蟻群系統(tǒng)ACS和變鄰域下降搜索VDN,提出一種混合啟發(fā)式算法ACS_VND。該混合算法充分利用了螞群搜索的多樣性和變鄰域下降搜索有較強(qiáng)的局部尋優(yōu)能力,提高了解的質(zhì)量,加速了算法的收斂。
[7] MOSHEIOV G. The traveling salesman problem with pick-up and delivery. European Journal of Operational
參考文獻(xiàn)
[1] DANTZIG G B, RAMSER J H. The truck dispatching problem. Manegement secience, 1959,6(1):80-91.
[2] DETHLOFF J. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum,2001,23(1):79-96.
[3] CRISPIM J, BRANDAO J. Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. Journal of the Operational Research Society,2005,56(11):1296-1302.
[4] DORIGO M, STUTZLE T. Ant colony optimization. Cambridge, Massachusetts, London, England: The MIT
Press, 2004.
[5] HANSEN P, MLADENOVIE N. An introduction to variable neighborhood search. Metaheuristic: Advanced and Trends in Loal Search Paradigms for Optimization. Boston: Kluwer Academic Publishers, 1999: 433-458.
[6] HANSEN P, MLADENOVIE N. Variable neighborhood search: principles and applications. European Journal of
Operational Research, 2001,130(3):449-467.
Research, 1994,79(2):299-310.