王 建，李紅云，楊燕飛

Wang Jian，Li Hongyun，Yang Yanfei

（北京航空航天大學(xué) 交通科學(xué)與工程學(xué)院，北京 100191）

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem，VRP）是營(yíng)運(yùn)車(chē)輛研究領(lǐng)域中一個(gè)具有重要理論和現(xiàn)實(shí)意義的問(wèn)題[1]。由于該問(wèn)題屬于 NP-hard（Non-deterministic Polynomial Hard，非確定性多項(xiàng)式難題），所以尋找到一種高效而精確的算法的可能性微乎其微，而自然界中生物群體的合作與競(jìng)爭(zhēng)等復(fù)雜行為產(chǎn)生的群體智能往往對(duì)解決某些特定的隨機(jī)尋優(yōu)問(wèn)題提供了高效的解決方法，因此人們開(kāi)始嘗試?yán)梅律悄芩惴ㄇ蠼狻?/p>

蟻群算法模型來(lái)源于對(duì)自然界真實(shí)螞蟻行為的觀測(cè)，蟻群在解決優(yōu)化以及分布控制問(wèn)題上具有很高的智能性，因此蟻群算法對(duì)解決復(fù)雜尋優(yōu)問(wèn)題的新型算法的開(kāi)發(fā)與應(yīng)用具有重要的啟發(fā)價(jià)值。蟻群算法隨機(jī)尋優(yōu)機(jī)制的核心內(nèi)容是分布性和協(xié)作性，而營(yíng)運(yùn)車(chē)輛具有同蟻群相似的分布性與協(xié)作性。目前采用蟻群算法求解車(chē)輛路徑問(wèn)題已經(jīng)取得了很多的研究成果[2-4]。但是蟻群算法也存在著前期收斂速度慢，容易陷入局部最優(yōu)等缺點(diǎn)。國(guó)內(nèi)外學(xué)者針對(duì)蟻群算法存在的缺點(diǎn)進(jìn)行一系列的改進(jìn)，包括Max-Min螞蟻系統(tǒng)，精英螞蟻系統(tǒng)，基于排序的螞蟻系統(tǒng)，基于混沌理論的螞蟻系統(tǒng)等[5-6]，這些改進(jìn)有一個(gè)共同的目的，就是在合理時(shí)間復(fù)雜度的限制條件下，盡可能提高蟻群算法在一定空間復(fù)雜度下的尋優(yōu)能力，從而改善蟻群算法的全局收斂性，并拓寬蟻群算法的應(yīng)用領(lǐng)域。

文中對(duì)蟻群算法的分布和協(xié)作機(jī)制進(jìn)行了深入研究，在分析已有蟻群系統(tǒng)的優(yōu)缺點(diǎn)的基礎(chǔ)上提出了基于實(shí)時(shí)路況的 3層信息素更新策略，提出了考慮時(shí)間窗約束的基于多種蟻群系統(tǒng)的混合蟻群算法（Mixed Ant Colony Algorithm，MACO），在算法中充分考慮實(shí)時(shí)路況更新對(duì)道路通行能力的影響，以增強(qiáng)蟻群算法在求解動(dòng)態(tài)車(chē)輛路徑問(wèn)題的算法性能。

1 車(chē)輛路徑問(wèn)題描述

營(yíng)運(yùn)車(chē)輛的調(diào)度問(wèn)題屬于車(chē)輛路徑問(wèn)題，但在普通的車(chē)輛路徑問(wèn)題上增加了一些約束，主要體現(xiàn)在以下3個(gè)方面：

1）營(yíng)運(yùn)車(chē)輛的調(diào)度不只是單純地考慮最短路徑，同時(shí)考慮車(chē)輛運(yùn)行過(guò)程中所經(jīng)路徑等級(jí)、運(yùn)行時(shí)間等問(wèn)題，最終達(dá)到降低整體成本的目的；

2）營(yíng)運(yùn)車(chē)輛作為一種商業(yè)化的信息溝通形式，要充分考慮以人為本，要注重企業(yè)形象、提高顧客滿意度；

3）營(yíng)運(yùn)車(chē)輛數(shù)目有限，載貨量一定并且客戶的訂單具有時(shí)間要求。

營(yíng)運(yùn)車(chē)輛領(lǐng)域的車(chē)輛路徑問(wèn)題可以簡(jiǎn)單描述為：每個(gè)廠商都有一個(gè)倉(cāng)庫(kù)和一批客戶集合，倉(cāng)庫(kù)即是配送中心，擁有K輛可用于調(diào)度的運(yùn)輸車(chē)輛，車(chē)輛的最大載重量、最大行駛距離和車(chē)況已知，每個(gè)客戶的位置信息、需求信息已知，車(chē)輛都由倉(cāng)庫(kù)出發(fā)，經(jīng)過(guò)若干客戶點(diǎn)之后返回倉(cāng)庫(kù)，形成一個(gè)子回路，假如若干車(chē)輛構(gòu)成的子回路集合可以完成對(duì)客戶點(diǎn)的不重復(fù)遍歷，那么就構(gòu)成車(chē)輛路徑問(wèn)題的一個(gè)可行解。通過(guò)一定的算法以及約束條件尋找可行解，并從可行解的集合中發(fā)掘滿足總行程最短或者總體成本最低的可行解就是營(yíng)運(yùn)車(chē)輛領(lǐng)域的車(chē)輛路徑問(wèn)題。

鑒于營(yíng)運(yùn)車(chē)輛調(diào)度問(wèn)題與普通的車(chē)輛路徑問(wèn)題存在以上不同，同時(shí)我國(guó)“十二五”提出到2015年構(gòu)建完善的營(yíng)運(yùn)車(chē)輛車(chē)聯(lián)網(wǎng)系統(tǒng)，以完成對(duì)路況信息的實(shí)時(shí)更新，因此有必要對(duì)蟻群算法做出一定形式的改進(jìn)，以適應(yīng)企業(yè)對(duì)車(chē)輛的調(diào)度。

2 基本蟻群算法模型

蟻群在覓食過(guò)程中可以通過(guò)感知和釋放一種帶有氣味的化學(xué)物質(zhì)—信息素來(lái)實(shí)現(xiàn)相互之間的通訊交流[7]。生物學(xué)家已經(jīng)指出，只要存在一種通過(guò)媒介質(zhì)進(jìn)行的間接傳遞信息途徑，就可以解釋蟻群如何實(shí)現(xiàn)有序的組織行為。蟻群算法的提出正是以此為基礎(chǔ)，以一種人工媒介質(zhì)的形式來(lái)實(shí)現(xiàn)群體之間的協(xié)作溝通。

螞蟻在蟻巢與食物源之間往返，在前進(jìn)和返回時(shí)都會(huì)釋放信息素，并且自然界中蟻群的實(shí)際行為也證明這是尋找較短分支所必需的行為方式。

蟻群在蟻巢與食物源之間的隨機(jī)尋優(yōu)簡(jiǎn)化模型如圖1所示。

參考圖1，假設(shè)在t時(shí)刻分別有m只螞蟻同時(shí)從蟻巢和食物源之間出發(fā)，路徑AB的長(zhǎng)度等于路徑BC的長(zhǎng)度，并且均為路徑AD以及DC的2倍。此時(shí)路徑ABC與路徑ADC上的信息素濃度均為τ(t)，螞蟻選擇路徑的概率嚴(yán)格與信息素濃度成線性比例關(guān)系，因此分別有p/2只螞蟻選擇ABC與ADC。當(dāng)?shù)竭_(dá)t+n時(shí)刻時(shí)，ADC路徑上的螞蟻已經(jīng)從出發(fā)地到達(dá)目的地，然而由于路徑較長(zhǎng)，AB路徑和BC路徑上的螞蟻在B點(diǎn)相遇，此時(shí)路徑ADC的信息素濃度為

而此時(shí)路徑ABC上的信息素濃度為

式中，τ(ρ)表示揮發(fā)掉的信息素?cái)?shù)量，τ(*)表示每只螞蟻在路上經(jīng)過(guò)時(shí)對(duì)路徑信息素濃度的貢獻(xiàn)量。

由于螞蟻選擇路徑的概率與信息素濃度成線性比例關(guān)系，因此

因此當(dāng)以后的m-p只螞蟻繼續(xù)往返于蟻巢與食物源之間時(shí)，由于兩條路徑信息素濃度的不同而有越來(lái)越多的螞蟻選擇較短的路徑而達(dá)到群體尋優(yōu)的效果。

3 蟻群算法改進(jìn)策略

將蟻群算法的思想用于求解營(yíng)運(yùn)車(chē)輛路徑問(wèn)題，要充分考慮客戶訂單的時(shí)間要求、位置要求等方面，因此對(duì)普通蟻群算法主要改進(jìn)轉(zhuǎn)移概率，信息素濃度更新以及最終可行解的選擇3個(gè)方面。

3.1 相鄰城市轉(zhuǎn)移概率

在基本的蟻群算法中，螞蟻轉(zhuǎn)移概率只考慮道路長(zhǎng)度和信息素濃度的影響，而在帶有時(shí)間窗的車(chē)輛路徑問(wèn)題中，應(yīng)綜合考慮，做到緊急訂單優(yōu)先處理。因此其轉(zhuǎn)移概率為

式中，τij(t)為在t時(shí)刻路徑ij上的信息素濃度；ηij(t)為由節(jié)點(diǎn)i選擇j點(diǎn)的期望值，一般情況下取ηij(t)=1/dij，dij為客戶 ij之間的花費(fèi)；ωij(t)是在 t時(shí)刻由城市i轉(zhuǎn)到城市j的滿意度影響因子；α，β，λ分別為信息素啟發(fā)因子、路徑選擇期望值影響啟發(fā)因子和滿意度影響啟發(fā)因子。顧客滿意程度與送貨時(shí)間有關(guān)，假定[aj，bj]為顧客點(diǎn)j的時(shí)間要求，在此范圍內(nèi)送到顧客的滿意度為1，顧客能容忍的提前送到時(shí)間為，能容忍的最晚送到時(shí)間為。在提前和推遲送貨時(shí)間內(nèi)將貨物送到的顧客滿意度變化符合一定的三角函數(shù)規(guī)律，如圖 2所示。

因此ωij(t)隨送貨時(shí)間的變化取值如式（6）所示。

式中，tj表示到達(dá)城市j的時(shí)間，其值等于到達(dá)顧客點(diǎn)i的時(shí)間加上在顧客點(diǎn)i的服務(wù)時(shí)間和由顧客點(diǎn)i到達(dá)顧客點(diǎn)j的路程時(shí)間。

在該轉(zhuǎn)移概率算法中，充分考慮了時(shí)間窗對(duì)顧客滿意度的影響，同時(shí)在不需要考慮時(shí)間窗的VRP問(wèn)題中，通過(guò)將λ設(shè)置為0可以很方便地將顧客滿意度的影響忽略。

3.2 信息素更新策略

3.2.1 信息素?fù)]發(fā)自適應(yīng)策略

線路非直線系數(shù)是路網(wǎng)布局規(guī)劃中的一項(xiàng)重要指標(biāo)。網(wǎng)絡(luò)兩節(jié)點(diǎn)（小區(qū)）間的非直線系數(shù)定義為該兩節(jié)點(diǎn)（小區(qū)）間的路上實(shí)際距離與兩點(diǎn)間空間直線距離之比。

首先統(tǒng)計(jì)車(chē)輛行經(jīng)路徑信息，并按照所經(jīng)路徑的質(zhì)量，路徑質(zhì)量定義為實(shí)際距離與非直線系數(shù)的函數(shù)，即

式中，Rij為m×2維矩陣，1到m分別代表顧客點(diǎn)i到顧客點(diǎn)j的路段在路網(wǎng)中的功能等級(jí)，ψij代表顧客點(diǎn)i到顧客點(diǎn)j的路段的非直線系數(shù)。

定義信息素?fù)]發(fā)因子

式中，ρ(t)為自適應(yīng)信息素調(diào)整因子，R(i1)表示某段路徑的功能等級(jí)數(shù)，s為道路集合。

采用自適應(yīng)信息素調(diào)整后的全局信息素更新策略為

該調(diào)整因子的功能在于對(duì)道路進(jìn)行排序處理，路程短且非直線系數(shù)小的道路屬于精英道路，信息素?fù)]發(fā)較慢，有助于加快算法收斂速度，當(dāng)R(i1)過(guò)大的時(shí)候，則代表此段路徑長(zhǎng)度長(zhǎng)且非直線系數(shù)大，此時(shí)ρ(t)有可能為負(fù)值，主要是為了避免算法陷入局部最優(yōu)，使所有道路都有可能被選中。

3.2.2 考慮空間擴(kuò)散特性的局部信息素更新

信息素在空氣中的濃度與距離成反比，在以往的蟻群系統(tǒng)中，往往對(duì)信息素的擴(kuò)散更新只是局限于一條道路，文中認(rèn)為信息素在空間的擴(kuò)散過(guò)程是三維立體擴(kuò)散，信息素的擴(kuò)散對(duì)周?chē)缆芬喈a(chǎn)生影響，該信息素?cái)U(kuò)散策略更加忠實(shí)于自然界真實(shí)的螞蟻系統(tǒng)，擴(kuò)散過(guò)程如圖3所示。

在簡(jiǎn)化的信息素?cái)U(kuò)散模型中，圓心的信息素濃度為τmax時(shí)，信息素在空氣中的最大傳播距離為2rmax，根據(jù)信息素濃度與傳播距離成正比的原則可知，信源信息素濃度為τ時(shí)，信息素的最大傳播距離為。

由此可得，距離信源為ri處的信息素為

從式（10）可以看出：距離信源越遠(yuǎn)，螞蟻所接收到的信息素就越少。

該擴(kuò)散策略充分考慮了與信源的距離和中央信息素濃度的影響，同時(shí)在算法中，考慮信息素的空間擴(kuò)散，更加真實(shí)地模擬自然界中信息素的擴(kuò)散機(jī)制，能夠更加全面地反映路況，提高算法的收斂速度。

3.2.3 采用閾值判斷的全局信息素更新策略

蟻群算法中容易出現(xiàn)的停滯和擴(kuò)散問(wèn)題不容忽視，將各條路徑上可能的殘留信息素量限制在[τmin，τmax]之間，以避免算法陷入停滯狀態(tài)。這個(gè)信息素限制規(guī)則的作用是把位于城市 i的螞蟻選擇城市 j作為下一個(gè)訪問(wèn)城市的概率 pij限制在[pmin，pmax]內(nèi)，其中0

基于閾值判斷的信息素更新策略如下

假定在任何一次迭代結(jié)束之后，任意一條邊（i，j）上的信息素的最大增量為qf(s*)，因此可得在第 1次迭代中的信息素的最大值為(1-ρ)τ0+qf(s*)，在第 2次迭代之后最大值為(1-ρ)2τ0+(1-ρ)qf(s*)+qf(s*)，以此類(lèi)推，考慮信息素?fù)]發(fā)之后，第NC次迭代結(jié)束之后的信息素的值應(yīng)該小于等于下式

因?yàn)?<ρ≤1，因此式（12）漸進(jìn)和收斂于

每當(dāng)發(fā)現(xiàn)一條新的最優(yōu)路徑，就按照式（13）更新τmax的值，相應(yīng)地，信息素的下界被設(shè)定為τmin=τmax/a，其中a是一個(gè)參數(shù)。

3.3 可行解的構(gòu)造方法

由于在VRP中，每輛營(yíng)運(yùn)車(chē)輛所經(jīng)過(guò)的只是客戶集合中的一個(gè)子回路，所有螞蟻?zhàn)踊芈返募蠘?gòu)成的解有可能為可行解也有可能得不到可行解。若在有限的迭代次數(shù)內(nèi)經(jīng)常得不到可行解，則會(huì)造成算法的時(shí)間復(fù)雜度大幅度增加，影響車(chē)輛調(diào)度系統(tǒng)對(duì)車(chē)輛的有效調(diào)度，無(wú)法完成企業(yè)降低成本等方面的要求，因此文中提出當(dāng)算法到達(dá)一定的迭代次數(shù)并未找到可行解時(shí)，放棄尋找可行解并轉(zhuǎn)向?qū)⑺媒平膺M(jìn)行可行化的算法以降低計(jì)算量，防止算法陷入搜索停滯狀態(tài)。

按照文獻(xiàn)[8]中給出的定義，近似解有2種，分別為最大未滿非可行解和最小溢出非可行解[8]。對(duì)于未滿非可行解按照節(jié)約算法將未出現(xiàn)在路徑中的點(diǎn)插入到現(xiàn)有路徑中，同理對(duì)于最小溢出非可行解可以將多次出現(xiàn)的客戶點(diǎn)通過(guò)插入可行解任意一個(gè)子回路的方式抹去。

若到達(dá)一定迭代次數(shù)時(shí)沒(méi)有找到可行解，并且還存在沒(méi)有被調(diào)用過(guò)的車(chē)輛，則需要比較單獨(dú)使用未調(diào)用車(chē)輛去服務(wù)未出現(xiàn)的客戶點(diǎn)與直接將該客戶點(diǎn)插入至未達(dá)到最大載貨量與最大行駛距離的子回路的成本，成本較低的方案即為尋找的可行解。

若近似解已經(jīng)完成對(duì)全部車(chē)輛的調(diào)用，則算法需要遍歷將未出現(xiàn)客戶點(diǎn)插入至子回路產(chǎn)生的成本總和，最低成本者同樣為尋找的可行解。

4 MACO算法步驟

根據(jù)上述蟻群算法改進(jìn)策略，提出的 MACO算法求解步驟如下。

1）算法開(kāi)始進(jìn)行時(shí)，初始化MACO的參數(shù)：τmin, τmax, h, allowedk，[aj，bj]，s，R，α，β，設(shè)置迭代次數(shù)NC，初始化各條路徑上的信息素，將m只螞蟻均勻地放在 N個(gè)節(jié)點(diǎn)上，更新 allowedk，tabuk；

2）將 m只螞蟻放在初始節(jié)點(diǎn)，迭代次數(shù)NC=NC++；

3）螞蟻從allowedk中選擇下一步允許到達(dá)的城市，根據(jù)轉(zhuǎn)移概率公式進(jìn)行移動(dòng)；

4）判斷載重量是否已經(jīng)達(dá)到極限，若是，則轉(zhuǎn)到第5步，若否，則轉(zhuǎn)到第3步；

5）螞蟻k返回原點(diǎn)，構(gòu)成一個(gè)子回路；轉(zhuǎn)到第2步，若tabu[k]未滿，則從初始節(jié)點(diǎn)繼續(xù)出發(fā)；

6）根據(jù)動(dòng)態(tài)揮發(fā)原則，更新局部路徑信息素；記錄本次最優(yōu)路徑，更新全局信息素；

7）若Nc

8）判斷可行解是否找到，若找到，轉(zhuǎn)到第9步，若沒(méi)有找到，找到近似解，通過(guò)節(jié)約算法將近似解可行化，轉(zhuǎn)到第9步；

9）輸出結(jié)果。

5 仿真驗(yàn)證

為了便于檢驗(yàn)算法的性能，用改進(jìn)的MACO算法在C#中進(jìn)行了仿真計(jì)算。文中采用Marius M等在文獻(xiàn)[9]中所述的基準(zhǔn)VRPTW實(shí)例，這些實(shí)例共有56個(gè)，這56個(gè)實(shí)例中都含有100個(gè)客戶和1個(gè)中心倉(cāng)庫(kù)，并規(guī)定了車(chē)輛負(fù)載、客戶的時(shí)間窗和車(chē)輛運(yùn)行時(shí)間[9]。

實(shí)驗(yàn)開(kāi)始，在每個(gè)城市都放置一只螞蟻，螞蟻的個(gè)數(shù)與客戶的數(shù)目相同，設(shè)置α=1.0，β=5.0，信息素?fù)]發(fā)因子ρ=0.12，ω1=0.68，ω2=0.32，NC=40，τmax=1，τmin=0.024。

文中選取56個(gè)實(shí)例中的10個(gè)進(jìn)行仿真計(jì)算，實(shí)驗(yàn)結(jié)果見(jiàn)表1。

表1 實(shí)驗(yàn)結(jié)果

仿真結(jié)果表明，算法具有快速尋優(yōu)的能力，能夠在很短的時(shí)間內(nèi)找到可行解或者找到近似解進(jìn)行快速可行化，并且通過(guò)對(duì)實(shí)驗(yàn)結(jié)果求平均值可以知道算法的尋優(yōu)結(jié)果穩(wěn)定，有效地改進(jìn)了蟻群算法求解時(shí)間長(zhǎng)，容易陷入局部最優(yōu)的缺點(diǎn)。

6 結(jié) 論

文中提出的混合蟻群算法（MACO）在處理帶有時(shí)間窗的車(chē)輛路徑問(wèn)題中具有計(jì)算結(jié)果穩(wěn)定，跳出局部最優(yōu)，計(jì)算時(shí)間短的優(yōu)點(diǎn)。除此之外，算法還有以下優(yōu)點(diǎn)。

1）提出的信息素?fù)]發(fā)自適應(yīng)策略能夠根據(jù)實(shí)時(shí)道路狀況調(diào)整信息素的揮發(fā)快慢，可以擴(kuò)展算法完成動(dòng)態(tài)調(diào)度問(wèn)題；

2）將螞蟻轉(zhuǎn)移概率中的ωij設(shè)置為1可以很方便地求解不帶時(shí)間窗的車(chē)輛路徑問(wèn)題或者經(jīng)典旅行商問(wèn)題；

3）修改迭代次數(shù)可以在保證計(jì)算量的前提下保持較好的尋優(yōu)穩(wěn)定性。

[1]Jose Brandao.A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem.[J]Computers&Operations Research.2011，38（1）：140-151.

[2]Ren yingtao，Maged Dessouky，F(xiàn)ernando Ordonez.The Multi-shift Vehicle Routing Problem with Overtime[J].Computer&Operations Research.2010，37（11）：1987-1998.

[3]R.Tavakkoli Moghaddam，M.Gazanfari，M.Alinaghian.A New Mathematical Model for A Competitive Vehicle Routing Problem with Time Windows Solved by Simulated Annealing[J].Journal of Manufacturing Systems.2011，30（2）：83-92.

[4]Habibeh Nazif，Lai Soon lee.Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem[J].Applied Methematical Modeling.2012，36（5）：2110-2117.

[5]W.Y.Szeto，Yongzhong Wu，Sin c.Ho.Anartificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem[J].European Journal of Operational Research.2011，215（1）：126-135.

[6]Zhang xiaoxia，Tang lixin.A New Hybrid Ant Colony Optimization Algorithm for the Vehicle Routing Problem[J].Pattern Recognition Letters.2009，30（9）：848-855.

[7]桑國(guó)珍，王峰，楊瑞臣.改進(jìn)的蟻群算法求解VRP問(wèn)題[J].現(xiàn)代電子技術(shù)， 2010（12）：75-77.

[8]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社， 2005，238-249.

[9]Marius M，Solomon M.Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constrains[J].Operation Research.1987，35（2）：763-781.