摘  要： 將蟻群優(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能在較短時(shí)間內(nèi)獲得比單個(gè)算法更好的車輛調(diào)度路徑。
關(guān)鍵詞： 蟻群系統(tǒng)； 變鄰域下降搜索； 車輛路徑； 混合啟發(fā)式算法

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

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

_j）。2-opt是指將pi+1位置上的站點(diǎn)與j交換，并將p_i+1和站點(diǎn)j(不包括p_i+1位置上的站點(diǎn)和站點(diǎn)j）之間的節(jié)點(diǎn)按逆序訪問(wèn)。例如：解s=0-1-9-5-7-4-0-2-6-3-8-10-11-0，對(duì)2條路徑分別通過(guò)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é)果與分析比較
以某長(zhǎng)途汽車客運(yùn)公司為實(shí)驗(yàn)對(duì)象，該運(yùn)輸公司有17個(gè)站點(diǎn)(包括14個(gè)途經(jīng)站點(diǎn)和3個(gè)終點(diǎn)站)，車輛都是德國(guó)產(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)解得到的車輛路徑總長(zhǎng)度；n表示所需車輛的臺(tái)數(shù)。

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

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