劉曉勝，張 芮，朱宏林，王 娟

（哈爾濱工業(yè)大學 電氣工程及自動化學院，黑龍江 哈爾濱 150001）

0 引言

電動汽車相對于傳統(tǒng)汽車具有明顯的節(jié)能減排的特點，成為21世紀最具有潛力的交通工具［1］。但續(xù)航里程是制約電動汽車發(fā)展的主要因素。動力電池作為電動汽車的動力來源，快速更換電池是解決這種問題的有效途徑之一［2］。對動力電池配送車輛進行路徑優(yōu)化，不僅可以提高經(jīng)濟效益，還可以及時滿足電動汽車的能量供給［3］。由此可見，合理選擇滿足約束條件的動力電池配送最優(yōu)路徑，進一步提升充換電站服務體系運行管理程度，具有非常重要的現(xiàn)實意義［4］。

物流配送中的路徑選擇優(yōu)化問題是一個典型的NP-hard問題，國內(nèi)外學者對其進行了深入的研究，并提出很多求解算法。這些算法可以分為精確求解算法和啟發(fā)式算法兩大類［5］。在精確求解算法中，計算量與問題的規(guī)模呈指數(shù)增加關系，求解耗費時間相當長，效率低［6］。啟發(fā)式算法以及一些組合算法成為研究路徑優(yōu)化問題的主要算法［7］，但是為了保證可行解，導致遺傳算法爬山能力差、禁忌搜索算法全局性差等問題?；镜膯l(fā)式算法在求解大規(guī)模的路徑優(yōu)化問題時存在各種缺陷［8］。

蟻群算法是一種新的種群啟發(fā)式算法，可以看作是一個分布式的多智能體系統(tǒng)。它可以在問題空間的多點同時獨立進行解搜索，具有很強的魯棒性［9］。本文根據(jù)路網(wǎng)的特點對蟻群算法進行改進，同時為了避免算法在搜索過程中陷入局部最優(yōu)，在算法中引入懲罰因子，在保證全局最優(yōu)的同時還可以提高算法的收斂速度。而且，對于城市的實際路網(wǎng)，當交通網(wǎng)絡規(guī)模龐大，各服務點的服務范圍內(nèi)交通情況實時變化時，蟻群算法在動態(tài)環(huán)境中具有良好的靈活性［10］，能夠適應不斷變化的道路狀況對路徑選擇的影響。同時，正反饋可以縮小搜索范圍，保證算法朝著最優(yōu)解的方向進化［11］，進一步體現(xiàn)了蟻群算法在求解路徑優(yōu)化問題時的優(yōu)越性。

1 電池配送的數(shù)學模型

本文以杭州市充換電服務網(wǎng)為背景，從電池配送的實際問題出發(fā)，主要解決以下2個問題。

a.電動汽車在行駛過程中可能會出現(xiàn)電力不足，而不能到達配送站進行電力補充。這時，電動汽車車主可以向電池調(diào)配中心“報警”，電池調(diào)度中心記錄有關的道路地理信息數(shù)據(jù)，然后調(diào)度載有動力電池的搶修車在最短的時間內(nèi)到報警現(xiàn)場搶修。

b.電動汽車換電主要依賴于智能充換電服務網(wǎng)絡，智能充換電服務網(wǎng)絡主要由電池集中充電站、電池充換電站及電池配送站三級網(wǎng)絡組成［12］。動力電池作為電能的載體，流動于三級服務網(wǎng)絡之間。由于充換電站的電池基本上可以自給，因此本文主要解決從集中充電站（物流據(jù)點）用多輛汽車向配送站（客戶點）送貨的問題，每個需求點的位置和需求量一定，每輛配送車的載重量一定，每日的最大行駛里程一定，合理安排配送車路線，使總運距最短，從而使配送成本最小。

1.1 搶修系統(tǒng)的數(shù)學模型

在對路徑進行選擇時，人們往往更傾向于選擇順暢、寬敞的大道，這樣搶修時間比較短；相反，有的路徑雖然較短，但可能存在道路狹窄等問題，甚至經(jīng)常發(fā)生交通擁堵，因而時間花費和燃油花費均不理想。因此，人們在選擇較為合理的路徑時主要考慮時間最短和距離最短。

1.1.1 路網(wǎng)的構(gòu)建

城市交通主要由眾多的道路相交、相連而構(gòu)成，并組成縱橫交錯、錯綜復雜的城市交通網(wǎng)絡圖。道路拓撲結(jié)構(gòu)是求解最優(yōu)路徑問題的基礎，它描述了道路網(wǎng)絡結(jié)點（道路交叉點）和主要道路的連通關系。提取和構(gòu)建道路網(wǎng)絡的網(wǎng)絡拓撲結(jié)構(gòu)是指：運用圖論中的相關知識，交通路網(wǎng)被抽象成帶權(quán)網(wǎng)絡無向圖G=（V，E，W）。 其中，V 為路網(wǎng)節(jié)點（即道路的交叉點）的有窮非空集合，V=｛V1，V2，…，Vn｝；E 為 V 中頂點之間邊的有窮集，每一條邊表示相鄰兩節(jié)點間的直達路徑，假定相鄰兩節(jié)點間最多僅有一條邊。SP? V 表示配送站（即源結(jié)點），EP?｛V-｛SP｝｝為事故地點（即目的結(jié)點），對 G 中的某一條邊（Vi，Vj），相應地有一個表示該路段特性的數(shù) di，j，若（Vi，Vj）之間連通則 di，j為實際路段長度；若（Vi，Vj）之間不連通，則 di，j=∞，在實際計算中以一個足夠大的值代替。把矩陣稱為權(quán)值矩陣，Dij表示路徑（Vi，Vj）是綜合考慮道路屬性和交通情況的等效道路長度。W為E上邊權(quán)值的有窮集，對于一定的城市交通網(wǎng)絡，W反映了某一時段的交通狀況和道路屬性。

利用從杭州市電子地圖上提取的道路網(wǎng)絡中各路段的屬性數(shù)據(jù)以及各結(jié)點的坐標信息，并利用鄰接矩陣存儲網(wǎng)絡拓撲信息，得到如圖1所示的道路網(wǎng)絡拓撲結(jié)構(gòu)，在不同的區(qū)域道路擁堵指數(shù)不同。

圖1 杭州市道路網(wǎng)絡拓撲圖Fig.1 Road network of Hangzhou

1.1.2 模型建立

在最優(yōu)路徑規(guī)劃中，增加2個啟發(fā)因素：道路等級指數(shù)rij和表示t時刻道路（Vi，Vj）交通擁堵情況的指數(shù)yij（t）。道路等級指數(shù)rij指道路的相對重要程度，其取值如式（1）所示：

rij值越小，說明道路（Vi，Vj）越重要，人工螞蟻在尋優(yōu)過程中更傾向于選擇等級較高的一級道路（快速路）。 yij（t）表示 t時刻道路（Vi，Vj）的交通擁堵情況，yij（t）越小，說明 t時刻道路（Vi，Vj）越通暢，這條路徑被選的概率越大。交通擁堵指數(shù)的范圍是1～10，10表示嚴重擁堵，1表示完全暢通。由于同一時間段不同區(qū)域的交通擁堵情況不同，不同時間段同一個區(qū)域的交通情況也不同，本文將一天的交通擁堵情況分成4個時間段和6個區(qū)域考慮，如表1［13］所示。某時間段某路段的交通擁堵指數(shù)在相應的指數(shù)范圍內(nèi)隨機變化。在仿真中，利用MATLAB中的rand函數(shù)在該范圍內(nèi)隨機產(chǎn)生交通擁堵指數(shù)的值來模擬實際道路交通情況的隨時變化。

表1 杭州市不同區(qū)域不同時間段交通擁堵指數(shù) yij（t）的范圍Table 1 Range of congestion index yij（t） of Hangzhou for different regions and different periods

引入3個權(quán)重系數(shù)來衡量影響最優(yōu)路徑選擇的各個因素相對重要程度：路徑距離的權(quán)重系數(shù)W1，道路等級的權(quán)重系數(shù)W2，交通堵塞的權(quán)重系數(shù)W3，滿足W1+W2+W3=1。利用層次分析法最終確定W1=0.6191、W2=0.1506、W3=0.3715。根據(jù)前面的分析，本文將時間約束、道路交通狀況等添加到目標函數(shù)中，提出以實際道路長度、道路等級以及交通擁堵情況線性組合成的等效道路長度為目標函數(shù)的最優(yōu)路徑規(guī)劃問題，來規(guī)劃省時省路的最優(yōu)路徑。最終確定的等效道路長度Dij如式（2）所示：

1.2 配送系統(tǒng)的數(shù)學模型

1.2.1 模型假設

在進行動力電池配送路徑選擇的數(shù)學模型構(gòu)造時首先作如下假設：

a.任何配送中心（集中充電站）所對應的需求點（配送站）和任何需求點的需求量均已知；

b.每個需求點（配送站）只由一輛車服務一次，每輛車只能服務一條路線；

c.需求點相互之間以及需求點與配送中心之間距離已知；

d.配送中心擁有多輛同種載重量的車，每輛車始點和終點均為各自所屬的配送中心；

e.配送成本與配送距離成正比；

f.要配送的動力電池有2種型號，質(zhì)量也不同，各型號的配送比例為1∶1，配送質(zhì)量取平均值；

g.配送網(wǎng)點有足夠的資源可以供應配送，并且擁有足夠的配送能力；

h.最終目標是尋找一個物流配送的路線，使配送成本最小。

1.2.2 變量定義

模型中要用到的變量定義為：K為集中充電站擁有的配送汽車數(shù)目；Qk（k=1，2，…，K）為每輛汽車的載重量；Dk（k=1，2，…，K）為每輛汽車一次配送的行駛距離；L 為配送站（需求點）數(shù)目；qi（i=1，2，…，L） 為每個配送站需要的動力電池的數(shù)目；di，j（i，j=1，2，…，L） 為配送站 i到配送站 j的距離；d0j（j=1，2，…，L） 為集中充電站到配送站的距離；nk（k=1，2，…，K）為第 k輛汽車配送的配送站數(shù)目（nk=0表示未使用第 k 輛汽車）；Rk（k=1，2，…，K）為第 k 輛汽車配送的配送站集合（當 nk≠0 時表示該配送站在第 k 輛汽車的配送線路中順序為i；ei為客戶點i對貨物需求的時間窗系數(shù)，值越大表示要貨的緊急程度越高，當 ei為-1時，表示沒有限制到貨時間；Pe為超時懲罰系數(shù)。

1.2.3 模型建立

配送車最優(yōu)路徑的選擇條件是，在滿足各個配送站需求的條件下，使整體的配送成本最小。而配送成本基本上和路程成正比，因此本文把尋找最短路徑作為目標函數(shù)。但是考慮到配送過程中可能由于交通情況配送車不能按時到達配送站，這里引入時間窗系數(shù)ei和超時懲罰系數(shù)Pe，將等待時間等效成距離，也就是下文提到的超時成本。

總路程S如式（3）所示。

假設集中充電站在第k輛車的配送路徑中排在第s位完成配送后，總的超時成本計算如式（5）所示：

目標函數(shù)為：

約束條件為：

上述模型中，式（8）為目標函數(shù)；式（9）保證每條路徑上各配送站的電池需求量之和不超過汽車的載重量；式（10）保證每條配送路徑的路程不能超過汽車一次配送的最大行駛里程；式（12）限制每個配送站僅能由1輛汽車送貨。

2 蟻群算法

2.1 基本蟻群算法

蟻群算法是人工智能算法之一，其模擬螞蟻的覓食行為，按啟發(fā)式思想，通過外激素的誘發(fā)作用逐漸收斂到問題的全局最優(yōu)解［14-15］。 設：di，j（i，j=1，2，…，n）表示路網(wǎng)中路段（Vi，Vj）間的距離，m是蟻群中螞蟻的數(shù)量，n為路網(wǎng)中的節(jié)點數(shù)；τij（t）表示t時刻在路段（Vi，Vj）上殘留的信息素濃度。初始時刻，設τij（0）=C（C為常數(shù)），即各條路徑上信息素濃度相等。人工螞蟻 k（k=1，2，…，m）在尋優(yōu)過程中，根據(jù)各條路徑上的信息素濃度決定轉(zhuǎn)移方向。這里用禁忌表tabuk來記錄螞蟻k當前所走過的節(jié)點；E表示所有節(jié)點的集合，集合隨著tabuk進化過程做動態(tài)調(diào)整；Ak=｛E-tabuk｝表示螞蟻k下一步允許選擇的節(jié)點集合。表示人工螞蟻k在t時刻由節(jié)點i轉(zhuǎn)移到節(jié)點j的概率：

其中，ηij（t）為能見度，在最短路徑問題中表示節(jié)點i轉(zhuǎn)移到節(jié)點 j的啟發(fā)式信息；α 表示在路徑（Vi，Vj）上信息素的重要程度；β表示在路徑（Vi，Vj）上啟發(fā)信息的重要程度。當所有人工螞蟻均完成對n個節(jié)點的遍歷（也即1個循環(huán)結(jié)束），此時禁忌表已經(jīng)填滿，應清空，并將螞蟻當前所在節(jié)點放入禁忌表tabuk中，準備下一次循環(huán)。同時，計算每一只人工螞蟻所走過的路徑長度Lk，并保存最短路徑。

隨著時間的積累，以前留下的信息素逐漸蒸發(fā)消逝，用參數(shù)1-ρ表示信息素殘留程度，當所有螞蟻均完成一次循環(huán)后，各條路徑上的信息素根據(jù)式（16）作調(diào)整。

設置周游次數(shù)計數(shù)器NC，當達到設定值時結(jié)束。最短路徑為：

2.2 算法改進

2.2.1 基于路網(wǎng)的算法改進

在基本的蟻群算法中，當螞蟻從節(jié)點i選擇下一個節(jié)點j時，需要將n-1個節(jié)點與禁忌表比較，再計算n-1個節(jié)點中不在禁忌表中的轉(zhuǎn)移概率，需要較長的計算時間。在實際應用中，螞蟻一定是在一個具有拓撲關系的網(wǎng)絡中爬行，螞蟻從節(jié)點i選擇下一個節(jié)點時，不會在所有非禁忌表中的節(jié)點間選擇，而只能是選擇與節(jié)點i之間存在直接路徑的節(jié)點，即存在邊（Vi，Vj）的節(jié)點中選擇。因此，在計算轉(zhuǎn)移概率時，僅需計算這部分節(jié)點的轉(zhuǎn)移概率，從而大幅降低了基本蟻群算法的計算量，提高了算法的計算速度。

類似地，在對信息素初始化時，對節(jié)點間有相連關系的道路的信息素初始化為τij（0）=C（C為常數(shù)，C≠0），對沒有相連關系的節(jié)點初始化為τij（0）=0。

2.2.2 全局信息素更新策略

道路網(wǎng)絡拓撲中會存在一些“死路”，即存在邊緣節(jié)點。算法對走入死路的螞蟻進行標記，并記錄與邊緣節(jié)點相連的路徑，如圖2所示，若螞蟻在尋找路徑過程中走入節(jié)點3或者節(jié)點4，無法到達終點，稱節(jié)點3、節(jié)點4為邊緣節(jié)點，同時將路徑L23或者路徑L14稱為死路。

圖2 死路和邊緣節(jié)點說明Fig.2 Illustration of dead-end and fringe-node

為避免下一只螞蟻在尋找路徑過程中進入死路，引入懲罰系數(shù)M，范圍是0～1。特別說明，這里的懲罰系數(shù)M與衰減系數(shù)ρ不一樣，衰減系數(shù)是模擬人體大腦的行為，在新的信息存入大腦的同時，舊的信息會隨著時間的推移而衰減，即道路網(wǎng)絡拓撲上的所有信息素都會受到衰減系數(shù)ρ的作用。但是懲罰系數(shù)只作用于與邊緣節(jié)點相連的道路上的信息素。因此，對走入死路中的螞蟻所經(jīng)過的與邊緣節(jié)點相連的路徑，利用τij（t）=τij（t）M，使信息素進一步衰減，減小下一次循環(huán)螞蟻選擇該條路徑的概率，提高算法的效率。

2.2.3 算法流程圖

綜上所述，可以得到改進后的算法流程圖如圖3所示。

圖3 改進的蟻群優(yōu)化算法的流程圖Fig.3 Flowchart of improved ant colony optimization algorithm

2.3 算法檢驗

利用圖1所示道路網(wǎng)絡拓撲，本文要求出從節(jié)點9到節(jié)點48之間的最短路徑。選取：信息啟發(fā)式因子 α=1.2，期望啟發(fā)式因子 β=0.6，信息素揮發(fā)因子 ρ=0.5，螞蟻數(shù)目 m=35，信息量 Q=1，迭代次數(shù)為100。仿真得到最短路徑圖如圖4所示。

多次運用改進蟻群算法進行實驗仿真，在第7次循環(huán)發(fā)現(xiàn)最優(yōu)路徑最優(yōu)路徑長度為 7.387 km。而應用基本蟻群算法在第31次收斂到局部最優(yōu)，對應的最優(yōu)路徑長度為7.68 km，如圖5所示?？梢钥闯?，改進的蟻群算法性能穩(wěn)定，具有很好的全局收斂性能。

圖4 最短路徑仿真結(jié)果Fig.4 Simulative results of the shortest path

圖5 傳統(tǒng)蟻群算法與改進蟻群算法的性能比較Fig.5 Comparison of performance between traditional and improved ant colony optimization algorithms

通過以上仿真分析，可以發(fā)現(xiàn)本文算法在信息素更新時引入懲罰因子和在信息素初始化時加入方向引導，很大程度上減少了不必要的劣質(zhì)解。信息素初始化時的差異指引著螞蟻尋找較優(yōu)解，可以有效地避免螞蟻一開始盲目的尋優(yōu)甚至誤導后來的螞蟻進行路徑選擇，明顯加快搜索最優(yōu)解的速度，提高解空間質(zhì)量。同時，改進蟻群算法可以保證算法收斂到全局最優(yōu)解。

3 模型求解

3.1 搶修系統(tǒng)模型求解

對于搶修車的動力電池配送最優(yōu)路徑選擇，考慮道路等級、道路擁堵指數(shù)和實際道路長度等，在前面研究的基礎上，假設事故點為節(jié)點1，其附近的配送站點為節(jié)點51，搶修車從配送站出發(fā)，載著動力電池到事故點對電動汽車進行換電操作。下面對搶修車的動力電池配送路徑分不同的時間段進行仿真，使其更接近實際情況。由于早高峰與晚高峰的交通擁堵情況類似，白天與其他時間段類似，本文僅對早高峰（07∶00 — 10∶00）和白天（10∶00 — 16∶00）2 個時段仿真，仿真結(jié)果如圖6、圖7所示。

在早高峰時段，城中的擁堵指數(shù)是 6.6～7.1，處于中度擁堵狀態(tài)；城東的擁堵指數(shù)是3.7，處于基本暢通狀態(tài)；城西的擁堵指數(shù)是 4.1～5.4，處于輕度擁堵狀態(tài)；城南的擁堵指數(shù)是 3.3～3.7，處于基本暢通狀態(tài)；城北的擁堵指數(shù)為4.5，處于輕度擁堵狀態(tài)；西湖風景區(qū)的擁堵指數(shù)為3.2～3.4，處于基本暢通狀態(tài)。城區(qū)整體的擁堵指數(shù)較高，選擇比較暢通的道路成為關鍵。仿真結(jié)果表明，最優(yōu)路徑的選擇避開了較為擁堵的城中，除了事故地點城西比較擁堵外，最終選擇的路段交通擁堵指數(shù)在3.7～4.5之間，處于基本暢通階段。同時，在滿足道路基本暢通的前提下，實驗還較多地選擇了快速路，避免選擇支路，具體選擇結(jié)果如表2所示。

圖6 早高峰07∶00—10∶00某時刻搶修車最優(yōu)配送路徑Fig.6 An optimal path of recovery vehicle during morning peak from 07∶00 to 10∶00

圖7 白天10∶00—16∶00某時刻搶修車最優(yōu)配送路徑Fig.7 An optimal path of recovery vehicle during daytime from 10∶00 to 16∶00

表2 早高峰07∶00—10∶00搶修車最優(yōu)配送路徑分析Table 2 Analysis of optimal path of recovery vehicle for morning peak from 07∶00 to 10∶00

10∶00— 16∶00 時段全城區(qū)的擁堵指數(shù)是 1.0 ～3.1，道路處于暢通或基本暢通狀態(tài)。此時，決定選擇最優(yōu)路徑的因素主要是道路的實際長度及道路等級。仿真結(jié)果表明，最優(yōu)路徑主要選擇快速路，同時考慮路網(wǎng)實際分布狀況和實際道路長度，選擇次干路的道路，避免選擇支路。選擇結(jié)果如表3所示。

3.2 配送系統(tǒng)模型求解

杭州市區(qū)集中充電站、配送站的分布以及各配送站的電池需求量如圖8所示。

配送車的載重為10 t，每日的最大行駛里程為100 km，路網(wǎng)抽象成完全連通圖，并利用蟻群算法進行仿真。選?。盒畔l(fā)式因子α=1，期望啟發(fā)式因子 β=4，信息素揮發(fā)因子 ρ=0.5，螞蟻數(shù)目 m=35，信息量Q=100，迭代次數(shù)為200，仿真得到電池配送路徑圖如圖9所示。

表3 白天10∶00—16∶00搶修車最優(yōu)配送路徑分析Table 3 Analysis of optimal path of recovery vehicle for daytime from 10∶00 to 16∶00

圖8 杭州市配送站每日電池需求量Fig.8 Daily battery demand of distribution stations in Hangzhou

圖9 配送車的配送路徑及算法收斂情況Fig.9 Delivery paths of delivery vehicles and convergence of algorithm

由圖9可以看出，選取載重為10 t的配送車輛，需要6輛，總的行駛里程為161.429 km。各車輛的配送路徑分別為

4 結(jié)論

本文以杭州市充換電服務網(wǎng)絡為背景，從電池配送的實際問題出發(fā)，分別建立電動汽車搶修路徑規(guī)劃和電池配送路徑規(guī)劃的數(shù)學模型。在搶修系統(tǒng)的數(shù)學模型中，以配送網(wǎng)絡中實際道路的路徑長度、交通堵塞系數(shù)和道路等級等效成的加權(quán)道路長度最小為目標函數(shù)，規(guī)劃省時省路的最優(yōu)路徑；在配送系統(tǒng)的數(shù)學模型中，考慮車輛在道路上的等待時間，并考慮配送車的行駛里程限制和最大載重量限制，以配送成本最小為目標函數(shù)。然后根據(jù)路網(wǎng)的特點，對蟻群算法的相鄰節(jié)點選擇策略、信息素初始化策略以及信息素更新策略進行改進，提高算法的收斂速度。同時，為了避免下一次循環(huán)螞蟻進入死路，引入懲罰因子，避免算法陷入局部最優(yōu)。

仿真結(jié)果表明，改進的蟻群算法能夠適應動態(tài)變化的路網(wǎng)結(jié)構(gòu)，有效而快速地求得電池配送路徑的最優(yōu)解。本文的研究內(nèi)容對電動汽車的發(fā)展具有很好的理論價值。