裴宏波，鄧 燁，盧厚清

(陸軍工程大學(xué) 野戰(zhàn)工程學(xué)院， 南京 210007)

在應(yīng)急車輛路徑問題研究中，時效性和公平性是區(qū)別于一般車輛路徑問題的顯著特點。但這兩者必須兼顧，如果單獨強(qiáng)調(diào)時效性則造成物資的失衡或浪費(fèi)，而一味強(qiáng)調(diào)公平性又會造成搶救時機(jī)的錯失。因此，應(yīng)急車輛路徑規(guī)劃的目標(biāo)就是盡量提高資源利用率，即系統(tǒng)總成本盡量低的基礎(chǔ)上，使時效性和公平性最優(yōu)。本文將應(yīng)急車輛路徑問題的時效性和公平性解釋如下：時效性，應(yīng)急事件發(fā)生后為了及時有效控制事件發(fā)展，必須優(yōu)先解決主要矛盾，具體來說，就是優(yōu)先服務(wù)需求量大的點或急迫程度高的點；公平性，應(yīng)急事件發(fā)生后，為避免供應(yīng)時間差異過大引起社會動蕩，不論需求量差異多大，每個點都應(yīng)公正平等的對待，具體來說，就是不能因為優(yōu)先服務(wù)“大客戶”而使“小客戶”等待時間太長。因此，傳統(tǒng)成本最小化目標(biāo)已不能恰當(dāng)反映受災(zāi)點的真實需求[1]，考慮時效性和公平性必須重點考慮救援物資到達(dá)每個受災(zāi)點的時間[1]。學(xué)者們對此提出不同的思路：Nikolakopoulou ]等[2研究了關(guān)于以平衡車輛使用時間為目標(biāo)的車輛路徑問題 (BUTVRP)，該類問題的目標(biāo)是在現(xiàn)有車輛能力下，以車輛使用時間的差最小，但當(dāng)車輛使用時間的差達(dá)到最小時，各個車輛的使用時間也可能都很大。Zhang等[3]針對時間要求提出了最快完成車輛路徑問題(FTVRP)，以最后一個車輛完成任務(wù)的時間最小為目標(biāo)。劉霞等[4]考慮了最小最大車輛路徑問題，該問題也考慮最長子線路最短，但其路徑包含返回車場的路程。Ngueveu等[5]于2009年研究了累計時間式帶容量約束的車輛路徑問題(Cumulative Capacitated Vehicle Routing Problem，CCVRP)，提出了“累計等待時間”[5-7]這一新目標(biāo)，累計等待時間等價于平均等待時間，同屬于公平性的一種度量指標(biāo)[8]，適合作為應(yīng)急車輛路徑規(guī)劃的優(yōu)化目標(biāo)。本文在CCVRP模型的基礎(chǔ)上進(jìn)行改進(jìn)，提出以“需求量加權(quán)的累計等待時間”作為優(yōu)化目標(biāo)，將每個應(yīng)急點物資需求量差異加入模型，不僅加快運(yùn)輸，而且同時達(dá)到最急迫的點優(yōu)先運(yùn)輸和整體快速運(yùn)輸相結(jié)合的優(yōu)化效果。需求量加權(quán)的累計等待時間最短，即代表所有貨物在應(yīng)急運(yùn)輸中走的“彎路”最少，從而達(dá)到時效性最強(qiáng)同時兼顧公平性的目標(biāo)。

在現(xiàn)實應(yīng)急事件中，車輛類型往往不止一種，需要根據(jù)車輛的裝備、容量、車齡或成本等方面不同，按客戶需要或配送成本合理分配車輛路線，因此需要結(jié)合多車型車輛路徑問題(Heterogeneous Fleet Vehicle Routing Problem，HVRP)進(jìn)行研究。國外學(xué)者Golden等[9]最先提出多車型車輛路徑問題的研究；國內(nèi)學(xué)者李軍、郭耀煌[10]最先研究了多車型滿載車輛調(diào)度優(yōu)化問題。求解算法主要是動態(tài)規(guī)劃、列生成等啟發(fā)式算法和禁忌搜索、遺傳算法、粒子群算法、蟻群算法、量子算法等智能優(yōu)化方法[11-14]。但目前多車型問題主要以降低成本、油耗、減少排量等作為優(yōu)化目標(biāo)，很少有將累計等待時間作為優(yōu)化目標(biāo)的研究，本文試圖將兩者進(jìn)行結(jié)合，研究更加貼近實際需求量加權(quán)的累計等待時間式多車型應(yīng)急車輛路徑問題(Cumulative Heterogeneous Fleet Vehicle Routing Problem with demands weighting，CHVRPdw)。在現(xiàn)實突發(fā)事件中，由于第一時間無法得到準(zhǔn)確的需求信息，決策者只能依據(jù)經(jīng)驗和歷史數(shù)據(jù)進(jìn)行初步預(yù)測，并根據(jù)后續(xù)信息進(jìn)行動態(tài)調(diào)整。其他研究主要在于優(yōu)化動態(tài)過程，本文的重點是合理規(guī)劃開始階段的車輛和路徑安排，以使得未來動態(tài)調(diào)整階段改動最少，因為需求越大的地點，發(fā)生動態(tài)變化的可能性越大，其實質(zhì)是優(yōu)化靜態(tài)過程。其中需求量加權(quán)的累計等待時間是實現(xiàn)最少改動的關(guān)鍵指標(biāo)，因為它既考慮了應(yīng)急點的需求急迫程度，又考慮了優(yōu)化路徑的總長度。

CCVRP問題已被證明是NP-hard問題[5]，CHVRPdw是較CCVRP更為復(fù)雜的衍生模型，因此也是NP-hard問題，而對于較大規(guī)模的NP-hard問題，需要采用啟發(fā)算法(heuristic algorithm)或元啟發(fā)算法(meta-heuristic algorithms)解決。從現(xiàn)有文獻(xiàn)資料來看，針對CHVRPdw的研究非常匱乏，對CCVRP也只有Ngueveu等人采用Memetic算法求解，而應(yīng)用蟻群算法解決CHVRPdw的研究尚未見相關(guān)報道。本文采用的蟻群算法ACA(Ant Colony Algorithm)對解決路徑尋優(yōu)問題具有天然的優(yōu)勢，它是由意大利學(xué)者Dorigo M等人于1991年首先提出[15-17]。在此基礎(chǔ)上，多種改進(jìn)的蟻群算法被提出，具有代表性的有：帶精英策略的螞蟻系統(tǒng)[18](Ant System with elitist strategy,ASelite)；Dorigo和Gambardella(1996)提出的蟻群系統(tǒng)[19](Ant Colony System,ACS)；Dorigo等人在ACS基礎(chǔ)上提出了更一般的蟻群算法Ant-Q System[16]等。其中，德國學(xué)者Stützle等[20]在1997年基于螞蟻系統(tǒng)提出的改進(jìn)算法——最大最小螞蟻系統(tǒng)(Max-Min Ant System,MMAS)是目前蟻群優(yōu)化中性能最好的算法，已成功地應(yīng)用于各類組合優(yōu)化問題中[21-22]，尤其是在TSP、VRP及其衍生模型上得到廣泛應(yīng)用。本文則是基于MMAS進(jìn)行改進(jìn)，通過基本CVRP算例，證明改進(jìn)算法的有效性和優(yōu)越性，同時結(jié)合CHVRPdw模型進(jìn)行實例計算，為解決實際應(yīng)急車輛路徑規(guī)劃問題提供新的思路。

1 CHVRPdw的數(shù)學(xué)模型

1.1 問題描述及符號說明

首先作如下假設(shè)：

1) 每個應(yīng)急節(jié)點可由任何一輛車且只能由一輛車服務(wù)，每輛車完成任務(wù)后需返回車場，且車輛不得重復(fù)使用；

2) 任意兩應(yīng)急節(jié)點間均有路徑直接到達(dá)，且整個應(yīng)急運(yùn)輸網(wǎng)絡(luò)為對稱型網(wǎng)絡(luò)；

3) 車輛勻速行駛，不考慮實際路況因素、裝卸物資時間和返程時間；

4) 運(yùn)輸對象均為通用類應(yīng)急保障物資，各類物資實行標(biāo)準(zhǔn)化單元運(yùn)輸，同時決策變量也均為整數(shù)。

問題的目標(biāo)：尋找一個合適的車輛路徑調(diào)度方案，在滿足車輛的各類約束條件下： 1)滿足各應(yīng)急點的需求量； 2)所有應(yīng)急節(jié)點的需求量加權(quán)累計等待時間盡量短，該目標(biāo)等價于單位重量應(yīng)急物資的行程時間盡量短。

1.2 數(shù)學(xué)模型

目標(biāo)函數(shù)：

(1)

約束條件：

?j∈N{0}，

?l∈[1,2,…,Lm]， ?m∈[1,2,…,M]

(2)

(3)

?l∈[1,2,…,Lm]， ?m∈[1,2,…,M]

(4)

(5)

(6)

?m∈[1,2,…,M]

(7)

?i∈N， ?j∈N， ?l∈[1,2,…,Lm]，

?m∈[1,2,…,M]

(8)

?m∈[1,2,…,M]

(9)

?l∈[1,2,…,Lm]，?m∈[1,2,…,,M]

(10)

(11)

2 CHVRPdw的求解算法

2.1 求解思路

對上文建立的CHVRPdw模型進(jìn)行分析，可以發(fā)現(xiàn)，其優(yōu)化目標(biāo)同傳統(tǒng)VRP的優(yōu)化目標(biāo)是最短路徑或最低成本有明顯區(qū)別，但同開放VRP有一定相似之處，兩者都忽略或不計回程時間。在用蟻群算法ACA(Ant Colony Algorithm)求解該問題時，每個螞蟻相當(dāng)于某一應(yīng)急車輛，螞蟻選擇某一車型從中心車場出發(fā)，以一定的轉(zhuǎn)移規(guī)則選擇待訪問的應(yīng)急節(jié)點，當(dāng)容量超過車型約束時返回中心車場，重新選擇車型訪問剩余節(jié)點，直到全部節(jié)點訪問完畢，其中每只螞蟻使用的車輛數(shù)必須滿足車型的數(shù)量約束。然后計算每只螞蟻所走路線的容量加權(quán)累計等待時間，值越小說明該路線越優(yōu)，其留下的信息素得到增強(qiáng)的概率越大，反之，路徑較差的子路段信息素含量隨著算法迭代會逐漸降低到很小的值，而每次迭代后的螞蟻都會傾向于選擇信息素含量較大的子路段，最終會找到一條最優(yōu)的車輛路徑方案。蟻群算法核心是轉(zhuǎn)移規(guī)則的設(shè)計和參數(shù)的優(yōu)化選取，但存在很大隨機(jī)性，故本文加入2-opt局部優(yōu)化策略，以加快收斂速度。

2.2 算法介紹

鑒于最大最小螞蟻系統(tǒng)MMAS在求解TSP、VRP等路徑優(yōu)化問題中的良好表現(xiàn)，本文擬采用MMAS算法結(jié)構(gòu)來求解提出的模型。MMAS算法結(jié)構(gòu)主要包括以下4個部分[23]：

1) 信息素軌跡更新

為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)解，每次循環(huán)后，只有一只螞蟻進(jìn)行信息素更新，這只螞蟻可以是當(dāng)前循環(huán)中的迭代最優(yōu)螞蟻，也可以是循環(huán)開始以來的全局最優(yōu)螞蟻，MMAS中主要使用迭代最優(yōu)螞蟻進(jìn)行更新：

(12)

2) 信息素軌跡限制和平滑

3) 信息素軌跡初始化

在第一次循環(huán)后，所有的信息素與τmax(1)相一致，如果將信息素初始化為τmin，選擇概率就會增加得異常緩慢，因此，將信息素初始化為最大值τmax可以明顯改善算法性能。

4) 算法收斂判析準(zhǔn)則

有兩種判斷方式，達(dá)到其中之一的條件可看作收斂。① 達(dá)到一定收斂精度，Viter-Viter-1≤ΔV；② 當(dāng)Maxiter=M。當(dāng)然，在實驗中，一般只設(shè)定迭代次數(shù)作為統(tǒng)一的判斷準(zhǔn)則，這樣可以方便比較算法性能。

2.3 改進(jìn)策略

傳統(tǒng)的蟻群算法及其改進(jìn)一般適用于求解成本最優(yōu)的車輛路徑問題，不完全適用于CHVRPdw的求解，必須進(jìn)一步改進(jìn)。

2.3.1 改進(jìn)轉(zhuǎn)移規(guī)則

為了擴(kuò)大解的搜索空間，增加隨機(jī)搜索的權(quán)重，本文以Dorigo M等提出的Ant-Q算法中的自適應(yīng)偽隨機(jī)比率選擇規(guī)則[16]作為基礎(chǔ)進(jìn)行改進(jìn),規(guī)則如下：對于每只螞蟻k，路徑記憶向量Rk按照訪問順序記錄了所有k已經(jīng)經(jīng)過的城市序號。設(shè)螞蟻k當(dāng)前所在城市為i，則其選擇城市j作為下一個訪問對象的概率如下:

其中

式中，τij表示信息素濃度函數(shù)；ηij表示期望啟發(fā)函數(shù)，ηij=1/dij；α、β、γ為相應(yīng)的啟發(fā)因子，是影響算法性能的關(guān)鍵參數(shù)，須經(jīng)試驗確定；R是在[0,1]上服從均勻分布的隨機(jī)變量，R0(0≤R0≤1)是確定性選擇初始概率參數(shù)；allowedk表示螞蟻k下一步允許選擇的需求節(jié)點集合。

2.3.2 改進(jìn)信息素更新規(guī)則

2.3.3 局部優(yōu)化策略

通過局部優(yōu)化策略可以明顯改善解的質(zhì)量，很多學(xué)者采用不同的局部優(yōu)化策略，如采用鄰域搜索λ-Opt、swap和move算子、結(jié)合遺傳算法等[24-26]，其中2-Opt算子[27]因其簡單有效而得到廣泛使用，本文也使用該算子對每輛車所走過的路線進(jìn)行局部優(yōu)化。

2.4 算法流程

求解CHVRPdw模型的算法框架可由圖1所示。

3 仿真分析

3.1 模型對比分析

為了驗證模型的有效性，這里暫不考慮車輛類型和數(shù)量約束，本文僅以路徑最短為目標(biāo)的CVRP模型、累計等待時間最短為目標(biāo)的CCVRP模型和本文提出的以需求量加權(quán)累計等待時間最短為目標(biāo)的單車型CHVRPdw模型(即CCVRPdw模型)進(jìn)行對比，采用本文改進(jìn)的MMAS算法求解，算法的有效性將在3.2節(jié)中通過實驗予以說明。

數(shù)據(jù)采用http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/網(wǎng)站上下載的CVRP算例中的A-n32-k5進(jìn)行實驗，共32個坐標(biāo)的隨機(jī)節(jié)點，其中第1個節(jié)點為中心車場，其余31個節(jié)點具有隨機(jī)的需求量，車輛容量為100，可用車輛數(shù)為6(如果不限定車輛數(shù)，則所有節(jié)點與中心節(jié)點相連所構(gòu)成的路徑為CCVRP最優(yōu)解，問題失去研究意義)，速度為1。

本文以CVRP模型為基礎(chǔ)，通過控制變量實驗，確定各參數(shù)的最優(yōu)值為：確定性選擇概率參數(shù)R0=0.7，初始信息素濃度τ0=10，信息素?fù)]發(fā)因子ρ=0.3，信息素啟發(fā)因子α=1，期望啟發(fā)因子β=2，可載率啟發(fā)因子γ=1，螞蟻數(shù)量M=33，迭代次數(shù)T=150；確定算法中參數(shù)最優(yōu)值為：正確決策概率Pbest=0.05，信息素閾值最小個數(shù)k=2，當(dāng)k取值較大時容易導(dǎo)致收斂過慢甚至不收斂，取1時候這種情況又過于苛刻，容易導(dǎo)致平滑操作的失效，從算法實驗的經(jīng)驗來看，取k=2比較合適。同理，平滑系數(shù)δ=0.6。

本測試通過硬件平臺：Intel(R) Core(TM)2 Duo CPU T6500 @2.10GHz，RAM 5G和軟件平臺：Matlab R2014b共同實現(xiàn)。每個模型分別進(jìn)行20次獨立的運(yùn)算，Best代表20次中的最優(yōu)結(jié)果，Average代表20次平均優(yōu)化結(jié)果。運(yùn)算結(jié)果見表1，三類模型的收斂曲線分別如圖2～圖4所示。

通過模型對比實驗可以發(fā)現(xiàn)，對應(yīng)CVRP模型真實路徑長度最短得到的路徑安排方案在累計等待時間上并不存在優(yōu)勢，也就是說，雖然整體運(yùn)輸成本最低，但對于應(yīng)急情況來說，真實路徑長度最優(yōu)的方案并沒有實際意義；對應(yīng)CCVRP模型累計等待時間最短得到的路徑安排方案雖然調(diào)用車輛數(shù)和真實路徑長度都不是最優(yōu)，但是充分體現(xiàn)了公平性，使整體節(jié)點的應(yīng)急時間縮短到最優(yōu)。相較前兩者，對應(yīng)CCVRPdw模型得到的需求量加權(quán)累計等待時間最短的路徑兼顧時效性與公平性，使整體物資的運(yùn)輸時間達(dá)到最短，體現(xiàn)了系統(tǒng)優(yōu)化的思想。其實質(zhì)就是以真實路徑長度和車輛數(shù)的很小損失來換取應(yīng)急時間的最優(yōu)，在應(yīng)急情況下是完全可以接受的。

3.2 算法對比分析

為了驗證算法的有效性和優(yōu)越性，本文將基本MMAS算法和改進(jìn)MMAS算法求解CHVRPdw模型進(jìn)行對比。對于CHVRPdw模型，目前沒有公開算例可以使用。為說明改進(jìn)策略，分別采用A-n32-k5、A-n55-k9、B-n38-k6、B-n57-k7作為測試算例進(jìn)行替代，其中車型參數(shù)人為設(shè)定。

車型參數(shù)R=(M,L,Q,V)，其中，車型編號M={1,2,3}，車型數(shù)量L1={2,3,4}，L2={4,5,6}車型容量Q={120,100,80}，車型速度V={0.8,1,1.2}。

將螞蟻數(shù)量M設(shè)為節(jié)點數(shù)n+1，基本MMAS算法中可載率啟發(fā)因子γ=0，其他算法參數(shù)設(shè)置參考3.1節(jié)。實驗共進(jìn)行10次，選擇最優(yōu)的結(jié)果記為Best，平均最優(yōu)值記錄為Average，最優(yōu)加權(quán)累計等待時間對應(yīng)的真實路徑長度記錄為RealLength，默認(rèn)使用全部車輛，這樣才能使得結(jié)果最優(yōu)。運(yùn)算結(jié)果見表2。

從實驗中任選一組來直觀比較兩種算法的收斂情況，其收斂曲線見圖5。

表1 模型對比分析結(jié)果

注：*表示該模型是以此項為目標(biāo)函數(shù)，其余各項數(shù)值是根據(jù)該項優(yōu)化值對應(yīng)的最優(yōu)路徑計算得到。

表2 算法對比分析結(jié)果

通過算法對比可以發(fā)現(xiàn)，本文提出的MMAS算法改進(jìn)策略對解決CHVRPdw問題具有很好效果，尤其是規(guī)模越大、效果越明顯，驗證了改進(jìn)算法的有效性和優(yōu)越性。對比3.1節(jié)與3.2節(jié)中A-n32-k5算例也會發(fā)現(xiàn)，雖然在增加車型和車數(shù)的基礎(chǔ)上加權(quán)累計等待時間有了較大縮短，但是相應(yīng)真實的總路程長度也增加很明顯，因此需要在未來研究中對此加以討論，即如何科學(xué)平衡應(yīng)急點的需求和應(yīng)急系統(tǒng)的整體成本。

4 結(jié)論

本文通過重新定義應(yīng)急車輛路徑優(yōu)化問題的時效性和公平性概念，提出應(yīng)急情況下優(yōu)化目標(biāo)必須同時兼顧時效性和公平性的原則，進(jìn)而在CCVRP模型基礎(chǔ)上首次提出考慮需求量加權(quán)的累計等待時間和多種車型同時存在情況下的CHVRPdw數(shù)學(xué)模型。同時，首次使用最大最小蟻群算法MMAS 來解決CHVRPdw模型問題，并有針對性的進(jìn)行了算法改進(jìn)，取得了較為明顯的效果。本文工作對應(yīng)急車輛路徑問題研究具有啟發(fā)意義，對蟻群算法在多車型車輛路徑問題中的應(yīng)用研究也有一定借鑒作用。由于篇幅所限，本文并未對大量算例進(jìn)行仿真實驗，算法的收斂性有待進(jìn)一步驗證，解的質(zhì)量有待進(jìn)一步提高。對于實際應(yīng)急情況下的多車型車輛路徑問題，還需考慮不同車輛類型的運(yùn)輸網(wǎng)絡(luò)不同、通道可靠程度不同以及動態(tài)環(huán)境等問題，有待未來進(jìn)行深入研究。

：

[1] CAMPBELL A M,VANDENBUSSCHE D,HERMANN W.Routing for relief efforts[J].Transportation Science,2008,42(2):127-145.

[2] NIKOLAKOPOULOU G,KORTESIS S,SNEFAKI A,et al.Solving a vehicle routing problem by balancing the vehicles time utilization[J].European Journal of Operational Research,2004,152:520-527.

[3] ZHANG X,MA H H,LIU W L,et al.Ant colony algorithm for vehicle routing problem with shortest completion time[C].The Proceedings of the 13th International Conference on Industrial Engineering and Engineering Management,2006:2928-2933.

[4] 劉霞，齊歡.最小-最大車輛路徑問題的禁忌搜索算法[J].系統(tǒng)工程,2007,25(1):46-52.

[5] NGUEVEU S U,PRINS C,CALVO R W.An effective memetic algorithm for the cumulative capacitated vehicle routing problem[J].Computers & Operations Research,2010,37(11):1877-1885.

[6] RIBEIRO G M,LAPORTE G.An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem[J].Computers & Operations Research,2012,39(3):728-735.

[7] KE L J,FENG Z R.A two-phase metaheuristic for the cumulative capacitated vehicle routing problem[J].Computers & Operations Research,2013,40(2):633-638.

[8] OGRYCZAK W.Inequality measures and equitable locations[J].Annals of Operations Research,2009,167(1):61-86.

[9] GOLDEN B L,ASSAD A,LEVY L,GHEYSENS R.The fleet size and mix vehicle routing problem[J].Computers & Operations Research.1984,11(1):49-66.

[10]李軍,郭耀煌.物流配送牢輛優(yōu)化調(diào)度理論與方法[M].北京:中國物資出版社,2001:1-90.

[11]FU L P.Scheduling Dial-a-ride Para-transit Under Time-varying,Stochastic Congestion[J].Transportation Research Part B,2002,36(6):485-506.

[12]BERNHARD F,MARTIN G.Time-Varying Travel Times in Vehicle Routing[J].Transportation Science,2004,38(2):160-173.

[13]王曉博,李一軍.電子商務(wù)環(huán)境下物流配送中心選址模型與評價方法[J].系統(tǒng)工程理論方法，2006,15(3):199-204.

[14]葛顯龍,許茂增,王偉義.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學(xué).2013,21(1):125-133.

[15]COLORNI A,DORIGO M,MANIEZZO V,et al.Distributed optimization by ant colonies[C].Proceedings of the 1st European Conference on Artificial Life,1991:134-142.

[16]GAMBARDELLA L M,DORIGO M.Ant-Q:A reinforcement learning approach to the traveling salesman problem[C].Proceedings of the 12th International Conference on Machine Learning,1995:252-260.

[17]DORIGO M,MANIEZZO V,COLORNI A.Ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.

[18]GAMBARDELLA L M,DORIGO M.Solving symmetric and asymmetric TSPs by ant colonic[C]//Proc of the IEEE Conference on Evolutionary Computation.1996,622-627.

[19]DORIGO M,GAMBARDELLA L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactionson Evolutionary Compution,1997,1(1):53-66.

[20]STUTZLE T,HOOS H.The MAX-MIN ant system and local search for the traveling salesman problem[A].IEEE International Conference on Evolutionary Computation and Evolutionary Program-ming Conference[C].Proceedings of IEEE-ICEC-EPS’97,1997:309-314.

[21]DORIGO M,BIRATARI M,STUTZLE T.Ant colony optimization:Artificial ants as a computational intelligence technique[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.

[22]FAVARETO D,MORETTI E,PELLEGRINI P.On the explorative behavior of max-min ant system[M].International Workshop on Engineering Stochastic Local Search Algorithms.Designing,Implementing and Analyzing Effective Heuristics,Springer Berlin Heidelberg,2009:115-119.

[23]STUTZLE T,HOOS H H.MAX-MIN Ant System[J].Future Generation Computer System,2000,16:889-914.

[24]BRAYSY O,GENDREAU M.Vehicle routing problem with time windows,Part I:Route construction and local searchalgorithms[J].Transportation Science,2005,39(1):104-118.

[25]SUBRAMANIAN A,DRUMMOND L M A,BENTES C,et al.A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery[J].Computers &Operations Research,2011,37(11):1899-1911.

[26]SUBRAMANIAN A,UCHOA E,OCHI L S.A hybrid algorithm for a class of vehicle routing problems[J].Computers &Operations Research,2013,40(10):2519-2531.

[27]HASEGAWA M,IKEGUCHI T,AIHARA K.Combination of chaotic neurodynamic with the 2-opt algorithem to solve traveling salesman problems[J].Physical Review Letters,1997,79(12):2344-2347.