車站車輛路徑問題是直接關(guān)系到客運(yùn)汽車公司的效率與效益、服務(wù)質(zhì)量和企業(yè)形象的關(guān)鍵問題，一直是運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域的研究熱點(diǎn)問題，在生活中有著廣泛的應(yīng)用價(jià)值，對(duì)該類問題的研究主要集中在能否找到在較短的時(shí)間內(nèi)給出較優(yōu)解的算法。Dethloff提出了帶有參數(shù)的插入法，Crispim提出了基于禁忌的混合啟發(fā)算法，但求解質(zhì)量還有較大的改進(jìn)空間。

　　蟻群算法蟻群算法（ant colony optimization, ACO），又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對(duì)PID控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。

　　1 車輛路徑的描述

　　本研究利用有向帶權(quán)圖G描述車輛調(diào)度路徑問題。假設(shè)G=（V，A，C），其中，V={i|i=0,1,…，n}是頂點(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。滿足以下條件并使得總行程長(zhǎng)度短：

　　（1）每輛車都從倉(cāng)庫(kù)出發(fā)，并終返回倉(cāng)庫(kù)。

　　（2）每個(gè)客戶都只被1輛車服務(wù)，且僅被服務(wù)1次。

　　（3）任1車輛在行程過程中，載重始終不能超過Q。

　　設(shè)s={ri|i={1,2,…，k}}是問題的一個(gè)解，其中，ri對(duì)應(yīng)1條車輛路徑。由上面問題描述要求可以知道，s作為問題的1個(gè)可行解的重要條件是：對(duì)任意ri都滿足以下條件：

　?。?）ri上所有站點(diǎn)的總上車需求D（x）不超過Q。

　?。?）ri上所有站點(diǎn)的總下車需求P（x）不超過Q。

　?。?）車輛承載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)化成可行路徑。

　　2 混合啟發(fā)式算法ACS_VND

　　2.1 初始化信息素

　　首先使用近鄰啟發(fā)式構(gòu)造一個(gè)強(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個(gè)站點(diǎn)近的站點(diǎn)，作為下一個(gè)訪問的節(jié)點(diǎn)；否則，轉(zhuǎn)步驟（1），直到所有站點(diǎn)都已經(jīng)被訪問。這里，將V0定義為尚未被訪問，且加入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)，直到V1為空，結(jié)束當(dāng)前路徑r的構(gòu)造。若所有站點(diǎn)都已在當(dāng)前解中，算法結(jié)束；否則，重新開始1條新的r并重復(fù)上述構(gòu)造過程。為取得利用歷史信息和隨機(jī)選擇之間的平衡，算法ACS_VND中動(dòng)態(tài)調(diào)整q0的大小，使其取值為qmax或qmin。

　　ACS_VND算法將弱可行解轉(zhuǎn)化為強(qiáng)可行解的過程如下：從頭到尾逐個(gè)掃描每1條路徑r上的站點(diǎn)，若訪問當(dāng)前站點(diǎn)后r不能滿足強(qiáng)可行性條件，則跳過當(dāng)前站點(diǎn)掃描下一個(gè)；否則，繼續(xù)掃描下一個(gè)；，按照逆序?qū)⒃诘?次掃描中被跳過的站點(diǎn)逐個(gè)重新加入r。

　　在求解過程中，根據(jù)，利用構(gòu)造的每一個(gè)解s進(jìn)行局部信息素更新，其中，0＜ρ1＜1是信息素的揮發(fā)系數(shù)，τ0是信息素的初值。

　　2.3 變鄰域下降搜索

　　變鄰域下降搜索的基本步驟是：從初始解出發(fā)，選擇一種鄰域結(jié)構(gòu)進(jìn)行局部搜索，直到找到局部解。以當(dāng)前局部解為初始解，使用另一種鄰域結(jié)構(gòu)繼續(xù)進(jìn)行局部搜索。當(dāng)使用任何一種鄰域結(jié)構(gòu)都不能繼續(xù)改進(jìn)當(dāng)前解時(shí)，結(jié)束VND過程。

　　在使用變鄰域下降搜索之前，需要定義一組鄰域結(jié)構(gòu)。算法ACS_VND中分別使用3種求解VRP問題時(shí)常用的鄰域結(jié)構(gòu)：插入（insert）、交換（swap）和2-opt。

　　（1）插入（insert）

　?。?）交換（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。

　?。?）2-opt

　　解s同一路徑上的2個(gè)站點(diǎn)i和j，在解s中的位置分別為pi與pj（pij）。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，對(duì)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é)果與分析比較

　　以某長(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)結(jié)果如表1所示。其中，L表示解得到的車輛路徑總長(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ì)量，加速了算法的收斂。