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

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

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

　　(2)交換(swap)
將解s中的站點i和j的位置互換(i和j可屬于同一路徑，也可屬于不同路徑)，產生新解。例如，解s=0-3-5-7-0-1-2-4-6-0，交換同一路徑上的站點3與7，產生新解s′=0-7-5-3-0-1-2-4-6-0；解s=0-3-5-7-0-1-2-4-6-0，交換不同路徑上的站點3與2，產生新解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）之間的節點按逆序訪問。例如：解s=0-1-9-5-7-4-0-2-6-3-8-10-11-0，對2條路徑分別通過2-opt優化后，得到新解s′=0-1-4-7-5-9-0-2-10-8-3-6-11-0。
2.4 搜索策略

3 實驗結果與分析比較
以某長途汽車客運公司為實驗對象，該運輸公司有17個站點(包括14個途經站點和3個終點站)，車輛都是德國產歐洲之星，已知各站點上下車客戶需求服務總量為k。為了驗證混合啟發式算法ACS_VND的性能，將它與單獨使用ACS或 VND算法進行了比較。除了算法不同之外，其他實驗樣本和設置均相同，以保證實驗不失一般性。實驗結果如表1所示。其中，L表示最優解得到的車輛路徑總長度；n表示所需車輛的臺數。

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

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