摘  要： 將蟻群優(yōu)化和變鄰域下降搜索VND相結(jié)合，形成一種混合啟發(fā)式算法ACS_VND，應(yīng)用于客運公司的汽車調(diào)度，求解車輛需求數(shù)和最佳路徑。該算法充分利用了2種不同算法的優(yōu)點。實驗結(jié)果表明，算法ACS_VND能在較短時間內(nèi)獲得比單個算法更好的車輛調(diào)度路徑。
關(guān)鍵詞： 蟻群系統(tǒng)； 變鄰域下降搜索； 車輛路徑； 混合啟發(fā)式算法

　　車站車輛路徑問題是直接關(guān)系到客運汽車公司的效率與效益、服務(wù)質(zhì)量和企業(yè)形象的關(guān)鍵問題，一直是運籌學(xué)、管理學(xué)、計算機科學(xué)等領(lǐng)域的研究熱點問題，在生活中有著廣泛的應(yīng)用價值,如物流陪送、郵政投遞、汽車、火車和飛機的調(diào)度等。對該類問題的研究主要集中在能否找到在較短的時間內(nèi)給出較優(yōu)解的算法。自1959年Dantzig^[1]提出這一問題以后，幾十年來已取得了大量的成果。Dethloff[2]提出了帶有參數(shù)的插入法，Crispim^[3]提出了基于禁忌的混合啟發(fā)算法，但求解質(zhì)量還有較大的改進空間。
蟻群優(yōu)化ACO(Ant Colony Optimization)是一種基于群體的元啟發(fā)算法，最初的靈感來源于真實的螞蟻搜尋食物的行為^[4]，以信息素作為媒介，間接進行信息交換。變領(lǐng)域搜索VNS(Variable Neighborhood Search)最早由Hansen和Mladenovie^[5]提出，其核心思想是：領(lǐng)域?qū)?yīng)搜索空間的拓撲特性，不同的領(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)域下降搜索則是屬于軌跡法。基于群體的元啟發(fā)式算法的優(yōu)勢是善于發(fā)現(xiàn)搜索空間中可能存在最優(yōu)解的區(qū)域，而軌跡法的優(yōu)勢在于善于探索搜索空間中較好的區(qū)域^[6]。因此，將二者結(jié)合可以充分利用各自的優(yōu)勢，提高算法的搜索性能和效率。本研究就是將二者進行結(jié)合，應(yīng)用于客運公司汽車的調(diào)度。
1 車輛路徑的描述
　　本研究利用有向帶權(quán)圖G描述車輛調(diào)度路徑問題。假設(shè)G=(V，A，C)，其中，V={i|i=0,1,…,n}是頂點集(其中0表示車站調(diào)度中心，其他表示站點)；A={(i,j)|i, j∈V}是連接各頂點的弧集；C={c_ij|(i,j)∈A}是權(quán)重矩陣，c_ij表示從站點i到站點j的距離。任意站點i(i=1,2,…,n)都有一定的上車d_i與下車需求p_i。安排車輛為所有客戶服務(wù)，要求滿足以下條件并使得總行程長度最短：
(1)每輛車都從倉庫出發(fā)，并最終返回倉庫。
(2)每個客戶都只被1輛車服務(wù)，且僅被服務(wù)1次。
(3)任1車輛在行程過程中，載重始終不能超過Q。
設(shè)s={r_i|i={1,2,…,k}}是問題的一個解，其中,r_i對應(yīng)1條車輛路徑。由上面問題描述要求可以知道，s作為問題的1個可行解的重要條件是：對任意r_i都滿足以下條件：
(1)r_i上所有站點的總上車需求D(x)不超過Q。
(2)r_i上所有站點的總下車需求P(x)不超過Q。
(3)車輛承載ri上的任何客戶之后人員都不超過Q。
若都滿足條件(1)、(2)、(3)，則稱s滿足強可行條件，是強可行解；若都滿足條件(1)、(2)，但不滿足條件(3)，則稱s滿足弱可行性條件，是弱可行解。由Mosheiov^[7]已經(jīng)證明，如果D(x)和P(x)都不超過車輛容量限制，則ri一定可以通過某種方式轉(zhuǎn)化成可行路徑。因此，若s是弱可行解，則一定可以通過某種方式轉(zhuǎn)化為強可行解。
2 混合啟發(fā)式算法ACS_VND
2.1 初始化信息素
　　首先使用最近鄰啟發(fā)式構(gòu)造一個強可行解s0，并且根據(jù)τ₀=1/n·f(s0)設(shè)定信息素的初值,其中n是站點數(shù)量。則最近鄰啟發(fā)式算法構(gòu)造解的步驟如下：
(1)從尚未訪問的節(jié)點中選擇距離調(diào)度中心最小的站點，開始一條新的車輛路徑r。
(2)若V₀不為空，則從中選擇距離r上最后1個站點最近的站點，作為下一個訪問的節(jié)點；否則，轉(zhuǎn)步驟(1)，直到所有站點都已經(jīng)被訪問。這里，將V₀定義為尚未被訪問，且加入r后，使得r仍能約束強可行性條件的所有站點節(jié)點的集合。
2.2 構(gòu)建可行解
由于弱可行性條件檢查比較簡單，因此在算法ACS_VND的構(gòu)建階段，首先產(chǎn)生一組弱可行解，然后轉(zhuǎn)化成強可行解。在ACS_VND中應(yīng)使用一種基于插入的啟發(fā)式方法構(gòu)造弱可行解。首先，從調(diào)度中心0出發(fā)，隨機選擇1個站點，開始1條新的路徑r；然后，根據(jù)如下偽隨機比例規(guī)則：

　　不斷地從V1中選擇站點，直到V₁為空，結(jié)束當前路徑r的構(gòu)造。若所有站點都已在當前解中，算法結(jié)束；否則，重新開始1條新的r并重復(fù)上述構(gòu)造過程。為取得利用歷史信息和隨機選擇之間的平衡，算法ACS_VND中動態(tài)調(diào)整q₀的大小，使其取值為q_max或q_min。
ACS_VND算法將弱可行解轉(zhuǎn)化為強可行解的過程如下：從頭到尾逐個掃描每1條路徑r上的站點，若訪問當前站點后r不能滿足強可行性條件，則跳過當前站點掃描下一個；否則，繼續(xù)掃描下一個；最后，按照逆序?qū)⒃诘?次掃描中被跳過的站點逐個重新加入r，即可得到1個強可行解。
在求解過程中，根據(jù)，利用構(gòu)造的每一個解s進行局部信息素更新，其中，0＜ρ₁＜1是信息素的揮發(fā)系數(shù)，τ₀是信息素的初值。
2.3 變鄰域下降搜索
變鄰域下降搜索的基本步驟是：從初始解出發(fā)，選擇一種鄰域結(jié)構(gòu)進行局部搜索，直到找到局部最優(yōu)解。以當前局部最優(yōu)解為初始解，使用另一種鄰域結(jié)構(gòu)繼續(xù)進行局部搜索。當使用任何一種鄰域結(jié)構(gòu)都不能繼續(xù)改進當前解時，結(jié)束VND過程。
在使用變鄰域下降搜索之前，需要定義一組鄰域結(jié)構(gòu)。算法ACS_VND中分別使用3種求解VRP問題時常用的鄰域結(jié)構(gòu)：插入(insert)、交換(swap)和2-opt。
(1)插入(insert)
　

　　(2)交換(swap)
將解s中的站點i和j的位置互換(i和j可屬于同一路徑，也可屬于不同路徑)，產(chǎn)生新解。例如，解s=0-3-5-7-0-1-2-4-6-0，交換同一路徑上的站點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，交換不同路徑上的站點3與2，產(chǎn)生新解s′′=0-2-5-7-0-1-3-4-6-0。
(3)2-opt
解s同一路徑上的2個站點i和j，在解s中的位置分別為p_i與p_j(p_i

_j）。2-opt是指將pi+1位置上的站點與j交換，并將p_i+1和站點j(不包括p_i+1位置上的站點和站點j）之間的節(jié)點按逆序訪問。例如：解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 實驗結(jié)果與分析比較
以某長途汽車客運公司為實驗對象，該運輸公司有17個站點(包括14個途經(jīng)站點和3個終點站)，車輛都是德國產(chǎn)歐洲之星，已知各站點上下車客戶需求服務(wù)總量為k。為了驗證混合啟發(fā)式算法ACS_VND的性能，將它與單獨使用ACS或 VND算法進行了比較。除了算法不同之外，其他實驗樣本和設(shè)置均相同，以保證實驗不失一般性。實驗結(jié)果如表1所示。其中，L表示最優(yōu)解得到的車輛路徑總長度；n表示所需車輛的臺數(shù)。

　　本實驗結(jié)合多種元啟發(fā)方法的優(yōu)點和策略，設(shè)計了更有效的混合啟發(fā)式算法。結(jié)合蟻群系統(tǒng)ACS和變鄰域下降搜索VDN，提出一種混合啟發(fā)式算法ACS_VND。該混合算法充分利用了螞群搜索的多樣性和變鄰域下降搜索有較強的局部尋優(yōu)能力，提高了解的質(zhì)量，加速了算法的收斂。

參考文獻
[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.