高英騰，廖志高

廣西科技大學(xué) 經(jīng)濟(jì)與管理學(xué)院，廣西 柳州 545006

2020年突發(fā)疫情使得用戶的消費(fèi)行為向線上遷移，生鮮電商呈爆發(fā)式增長(zhǎng)，當(dāng)年冷鏈物流市場(chǎng)規(guī)模為4 698 億元，同比增幅38.5%，冷鏈物流市場(chǎng)規(guī)模及同比增幅均創(chuàng)歷史新高。生鮮產(chǎn)品有著易腐敗的特質(zhì)，在運(yùn)輸過程中極易產(chǎn)生損耗。同時(shí)，由于存在制冷環(huán)節(jié)，冷鏈運(yùn)輸產(chǎn)生的碳排放要遠(yuǎn)高于普通貨物運(yùn)輸時(shí)產(chǎn)生的碳排放，隨著配送路程及配送時(shí)間的增加，運(yùn)輸成本及碳排放量也會(huì)大大增加。為提高冷鏈運(yùn)輸效率，減少資源消耗，眾多學(xué)者對(duì)冷鏈車輛路徑問題展開了研究。

車輛路徑問題最初以總路程最短為目標(biāo)，運(yùn)用貪婪算法[1]、模擬退火算法[2]等進(jìn)行求解。隨著研究的深入，葛斌等[3]在最短路徑的基礎(chǔ)上引入時(shí)間窗的概念，融合蟻群算法和遺傳算法，為蟻群算法增加動(dòng)態(tài)參數(shù)，提高了算法的收斂速度。易云飛等[4]則在此基礎(chǔ)上引入軟時(shí)間窗的概念，運(yùn)用改進(jìn)伊藤算法進(jìn)行求解。宋芹[5]引入“油耗節(jié)約最大化”和“高載重路段延后”的思想，基于禁忌搜索法提出最大油耗節(jié)約算法，從最小油耗的角度對(duì)路徑進(jìn)行規(guī)劃。為突出運(yùn)輸過程中碳排放對(duì)環(huán)境的影響，Bekta?等[6]提出了污染路徑問題。王智憶等[7]建立了以碳排放量最低為目標(biāo)的配送路徑優(yōu)化模型，并采用蟻群算法進(jìn)行求解。Jabir等[8]則在綜合考慮經(jīng)濟(jì)成本和碳排放成本的情況下，構(gòu)造了多基地綠色車輛路徑問題，提出了一種將可變鄰域搜索與蟻群算法結(jié)合的混合算法，每只螞蟻求出初始解后，通過可變鄰域搜索再進(jìn)行連續(xù)優(yōu)化，不斷提高解的質(zhì)量。

相比于車輛路徑問題，冷鏈車輛路徑問題需要考慮的因素更多。Ahumada等[9]以生產(chǎn)者收益最大為優(yōu)化目標(biāo)，建立了帶時(shí)間窗的冷鏈車輛路徑問題優(yōu)化模型。Shukla 等[10]以運(yùn)輸成本、腐爛程度為優(yōu)化目標(biāo)函數(shù)，構(gòu)建數(shù)學(xué)模型來(lái)解決生鮮農(nóng)產(chǎn)品冷鏈物流問題。梁承姬等[11]則從制冷成本的角度出發(fā)，將溫度引入決策變量中，通過調(diào)節(jié)車廂溫度來(lái)降低配送成本。王淑云等[12]考慮了不同產(chǎn)品的保存溫度不同，建立了隨機(jī)需求下帶有時(shí)間窗的冷鏈多溫共配路徑優(yōu)化模型。陳久梅等[13]在此基礎(chǔ)上，綜合考慮生鮮農(nóng)產(chǎn)品多品種與小批量以及易腐性的特性，以車輛行駛成本最小為優(yōu)化目標(biāo)構(gòu)建數(shù)學(xué)模型，設(shè)計(jì)了一種改進(jìn)粒子群算法求解。

在某些場(chǎng)景中生鮮產(chǎn)品由配送時(shí)間產(chǎn)生的成本遠(yuǎn)高于由配送距離產(chǎn)生的成本，而路況的變化嚴(yán)重影響著運(yùn)輸時(shí)間。為了減小由路況問題導(dǎo)致的成本偏差，學(xué)者們開始在冷鏈運(yùn)輸路徑問題中引入交通路況信息，考慮道路擁堵如何通過影響車輛行駛速度來(lái)影響道路選擇。蘭輝等[14]將配送路段的距離矩陣轉(zhuǎn)化為運(yùn)輸時(shí)間矩陣，以總成本最小為目標(biāo)構(gòu)建了冷鏈物流車輛路徑問題數(shù)學(xué)模型，設(shè)計(jì)遺傳算法與2-opt 算法結(jié)合的混合遺傳算法進(jìn)行求解。Xu、Fan 等[15-16]考慮到實(shí)際情況中車速的變化是平滑的而不是階梯狀的變化，使用三角函數(shù)來(lái)替代階梯變化的速度。Woensel等[17]考慮了車輛隨機(jī)行駛時(shí)間，在考慮配送成本的同時(shí)引入農(nóng)產(chǎn)品配送的服務(wù)質(zhì)量，設(shè)計(jì)改進(jìn)禁忌搜索算法尋找配送服務(wù)質(zhì)量與配送成本之間的平衡點(diǎn)。

可以看到，隨著研究不斷深入，對(duì)車輛路徑問題的研究逐漸由單一算法向混合算法過渡，算法所得結(jié)果越來(lái)越精確，對(duì)冷鏈車輛路徑問題的研究也越來(lái)越貼合實(shí)際需求。但上述研究?jī)H考慮配送點(diǎn)之間只有一條道路通行。在實(shí)際配送時(shí)由于市區(qū)道路的復(fù)雜性，車輛往往有多條道路可以選擇，使得問題與傳統(tǒng)的旅行商問題不同，除配送點(diǎn)外還存在許多可重復(fù)到達(dá)的轉(zhuǎn)運(yùn)節(jié)點(diǎn)。此時(shí)若采用蟻群算法，螞蟻會(huì)在行駛成本較低的路段重復(fù)搜索，而采用貪心規(guī)則的Dijkstra算法計(jì)算量大，且易陷入局部最優(yōu)。針對(duì)這一問題，本文嘗試?yán)孟伻核惴ㄕ答伒奶攸c(diǎn)以及Dijkstra 搜索能力強(qiáng)的特點(diǎn)設(shè)計(jì)蟻群-Dijkstra 混合算法，用蟻群算法選擇下一配送點(diǎn)，通過Dijkstra 算法搜索兩配送點(diǎn)之間的最短路徑，并在每輪迭代后利用蟻群算法留下的信息素調(diào)整不同時(shí)刻的道路運(yùn)輸成本，使得貪心規(guī)則的Dijkstra 算法能考慮到總成本最低而不是當(dāng)前路徑的最低成本。同時(shí)預(yù)留修正成本文件，減少計(jì)算量，最終達(dá)到提高響應(yīng)速率、優(yōu)化行駛路徑的目的。

1 模型建立

本文研究基于市區(qū)實(shí)況路網(wǎng)的冷鏈車輛運(yùn)輸規(guī)劃問題，考慮配送點(diǎn)之間有多條道路可以選擇，綜合考慮固定成本、時(shí)間變動(dòng)成本、路程變動(dòng)成本、時(shí)間窗懲罰成本及碳成本，以總成本最低為目標(biāo)函數(shù)建立數(shù)學(xué)模型。

1.1 問題假設(shè)

為更好地界定研究問題，提出假設(shè)如下：（1）有且僅有一個(gè)配送中心，車輛從配送中心出發(fā)，在車內(nèi)貨物配送完畢后返回配送中心，且車輛僅負(fù)責(zé)送貨，不負(fù)責(zé)取貨。（2）配送中心車輛充足，每個(gè)零售商的需求量不會(huì)高于單次配送能力。（3）每個(gè)零售商的位置、需求量、服務(wù)時(shí)間以及時(shí)間窗已知，且所需貨品為同一品類。（4）配送點(diǎn)與物流中心約定好貨品送達(dá)時(shí)間窗，若車輛未按時(shí)間窗約定的時(shí)間送達(dá)，需要付出罰金。（5）運(yùn)輸車輛型號(hào)統(tǒng)一，能耗及油耗相同，司機(jī)均接受過相同的技能培訓(xùn)，油耗不會(huì)隨主觀因素變化。（6）車輛在每條道路上的行駛速度為該道路當(dāng)前能夠行駛的最大速度。

1.2 符號(hào)和變量

為方便研究描述，引入符號(hào)及相關(guān)含義如下：α為信息素啟發(fā)因子；β為成本啟發(fā)因子；λ為信息素?fù)]發(fā)因子；N為配送點(diǎn)數(shù)量；K為所需車輛總數(shù)；fk為第k輛冷藏車的固定成本；a為運(yùn)輸時(shí)制冷成本系數(shù)；b為裝卸時(shí)制冷成本系數(shù)；qj為客戶j對(duì)產(chǎn)品的需求量；為車輛k選擇從客戶點(diǎn)i到客戶點(diǎn)j的概率；P為產(chǎn)品單位價(jià)格；?1為貨物運(yùn)輸時(shí)的衰減系數(shù)；?2為貨物裝卸時(shí)的衰減系數(shù)；為車輛k從配送中心出發(fā)時(shí)間；為車輛k對(duì)客戶點(diǎn)j的服務(wù)時(shí)間；為車輛k從客戶點(diǎn)i到客戶點(diǎn)j時(shí)的載重；Q為車輛最大載重；ε1為車輛早于時(shí)間窗送達(dá)的懲罰系數(shù)；ε2為車輛晚于時(shí)間窗送達(dá)的懲罰系數(shù)；ρ0為車輛空載行駛時(shí)的燃油消耗率；ρQ為車輛滿載行駛時(shí)的燃油消耗率；為車輛從客戶i到客戶j的運(yùn)輸距離；R為最高賠償金額；為車輛k從配送點(diǎn)i到配送點(diǎn)j的行駛速度；Pf為單位體積的燃油價(jià)格；PC為碳排放價(jià)格；TC為單位燃料產(chǎn)生的碳排放量。

1.3 決策變量的制定

客戶點(diǎn)由i、j表示(i,j=1,2,…,n)，決策變量xijk為0-1變量，取值如下：

決策變量yjk為0-1變量，取值如下：

1.4 成本分析

（1）固定成本C1

固定成本包括司機(jī)的工資，車輛折損、保養(yǎng)等費(fèi)用。這部分成本僅與運(yùn)輸車輛的數(shù)量有關(guān)，故固定成本C1可表示為：

（2）路程變動(dòng)成本C2

路程變動(dòng)成本主要為車輛行駛產(chǎn)生的油耗，油耗的計(jì)算方式采用負(fù)載估計(jì)法[18]。車輛負(fù)載量為時(shí)的燃油消耗率ρM為：

則在車輛行駛過程中的總油耗fuel為：

路程變動(dòng)成本等于油耗成本C2，表示為：

（3）時(shí)間變動(dòng)成本C3

考慮時(shí)間變動(dòng)成本時(shí)，需要考慮不同路況對(duì)運(yùn)輸時(shí)間的影響，車輛k從點(diǎn)i到點(diǎn)j所需的時(shí)間可表達(dá)為：

時(shí)間變動(dòng)成本包括制冷成本及貨損成本。制冷成本包括運(yùn)輸時(shí)消耗制冷劑的成本及制冷的油耗?？紤]運(yùn)輸及裝卸時(shí)車廂溫度不同，對(duì)制冷劑及燃油的消耗不同，在模型中將二者系數(shù)分別合并為a、b，分別代表運(yùn)輸及裝卸時(shí)的制冷成本系數(shù)。此時(shí)制冷成本C31可表達(dá)為：

由于生鮮產(chǎn)品的品質(zhì)會(huì)隨著運(yùn)輸時(shí)間的增長(zhǎng)而不斷下降，且隨時(shí)間的增長(zhǎng)，品質(zhì)的下降程度呈指數(shù)型增長(zhǎng)，故在此使用L(t)表示貨物的衰減程度[19]：

卸貨時(shí)，由于貨物已經(jīng)送達(dá)，此時(shí)貨損僅計(jì)算卸貨后剩余部分，則貨物在運(yùn)輸過程中的貨損成本為：

在裝卸時(shí)的貨損成本為：

貨損成本C32可表達(dá)為：

（4）時(shí)間窗懲罰成本C4

在實(shí)際情況中，配送點(diǎn)和配送中心約定時(shí)間窗(Ei,Li)，商品j應(yīng)在時(shí)間窗內(nèi)送達(dá)。若商品提前送達(dá)，需賠償配送點(diǎn)由于未做好接貨準(zhǔn)備而造成的損失，若商品延遲送達(dá)，則需賠償由延誤造成的損失。但是由于商品價(jià)值有限，該成本不會(huì)無(wú)限量地增加，故在此設(shè)定賠償上限R，使得賠償成本不會(huì)高于R值。時(shí)間窗懲罰成本C4可表示為：

（5）碳排放成本C5

車輛運(yùn)行中所產(chǎn)生的碳排放主要分為兩部分，一部分是車輛行駛的燃油消耗成本，另一部分則來(lái)自制冷所消耗的燃油及制冷劑。考慮到制冷劑消耗量較少，以制冷成本消耗的燃油代替計(jì)算相應(yīng)的碳排放量。這兩部分成本見式（5）及式（8），則車輛行駛中的碳排放主要由燃油燃燒產(chǎn)生。

2021年全國(guó)碳排放市場(chǎng)上線交易啟動(dòng)，若企業(yè)總碳排放未超出碳配額，可以交易出售；反之則需購(gòu)買超排數(shù)量。此時(shí)碳配額可看作企業(yè)已有收益，產(chǎn)生的碳排放需以碳市場(chǎng)價(jià)格支付成本，故此處以碳市場(chǎng)價(jià)格描述單位碳排放成本。故碳排放成本C5可表示為：

綜上所述，總成本C的表達(dá)式為：

式（16）表示每個(gè)客戶都被服務(wù)且僅被服務(wù)一次。式（17）表示車輛服務(wù)于客戶時(shí)其貨物數(shù)量能夠滿足客戶需求。式（18）表示每輛車從配送中心出發(fā)，返回配送中心。

2 模型求解

首先嘗試采用蟻群算法求解。在算法初期，由于路徑之間的信息素相同，螞蟻較大概率選擇兩點(diǎn)之間成本較低的節(jié)點(diǎn)，而經(jīng)過中轉(zhuǎn)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)不被列入禁忌表，也不會(huì)觸發(fā)時(shí)間窗懲罰成本，因此螞蟻會(huì)在某些抵達(dá)成本較低的節(jié)點(diǎn)中來(lái)回走動(dòng)。Dijkstra算法能夠避免重復(fù)搜索問題，故擬利用蟻群算法選擇下一配送點(diǎn)，通過Dijkstra 算法搜索兩配送點(diǎn)之間的最短路徑，并在每輪迭代后利用蟻群算法留下的信息素調(diào)整不同時(shí)刻的道路搜索成本，使得貪心規(guī)則的Dijkstra 算法能考慮到總成本最低而不是當(dāng)前路徑的最低成本。

2.1 啟發(fā)式因子設(shè)計(jì)

啟發(fā)式因子是螞蟻選擇下一目的地的重要依據(jù)，通常隨目的地的重要程度增大而增大。算法以總成本最低為目標(biāo)，故以成本因素作為啟發(fā)式因子。因此設(shè)計(jì)啟發(fā)式因子ηij為：

其中，Cij代表車輛從點(diǎn)i到點(diǎn)j的成本。

2.2 信息素更新

螞蟻在經(jīng)過的道路上會(huì)留有信息素，并通過信息素的含量判斷該道路是否重要。為防止算法陷入局部最優(yōu)，在交通擁堵時(shí)找到更好的代替配送路徑，在每輪所有螞蟻巡回完畢后，同時(shí)選擇所有輪次總成本最低以及當(dāng)前輪次總成本最低的螞蟻經(jīng)過路徑更新信息素。

最優(yōu)路徑上信息素更新規(guī)則為：

非最優(yōu)路徑上信息素更新規(guī)則為：

其中，λ為信息素?fù)]發(fā)因子，目的是減少最初搜索時(shí)殘留信息素的影響。但為了使得算法在交通變動(dòng)時(shí)仍能選出次優(yōu)路徑，該值不宜過小。

為防止算法過快收斂，在此引入一個(gè)不斷增大的q0(q0∈[0,1])，在每次螞蟻選擇下一個(gè)配送點(diǎn)時(shí)會(huì)先產(chǎn)生一個(gè)隨機(jī)數(shù)qi，將q0與qi進(jìn)行比較，根據(jù)比較結(jié)果來(lái)選擇下一配送點(diǎn)。具體表達(dá)式如下：

當(dāng)qi小于等于q0時(shí)，在可選路徑中選擇修正成本最高（實(shí)際成本最低）的路徑。反之按照輪盤賭的方式進(jìn)行選擇。

2.3 混合算法流程設(shè)計(jì)

考慮到運(yùn)輸過程中需要根據(jù)交通變化情況實(shí)時(shí)調(diào)整路線，而Dijkstra算法計(jì)算量較大，故將算法分為兩階段進(jìn)行求解計(jì)算。第一階段為預(yù)處理過程，此時(shí)算法以蟻群算法為主，通過反復(fù)迭代更新不同時(shí)刻不同道路上的信息素含量，得到初始配送路徑及修正成本地圖。預(yù)處理階段混合算法流程如圖1所示。

圖1 預(yù)處理階段的混合算法流程Fig.1 Hybrid algorithm flow in preprocessing stage

當(dāng)途經(jīng)路況發(fā)生變化時(shí)，無(wú)需全部重新計(jì)算，通過已有的修正成本地圖，修正對(duì)應(yīng)時(shí)刻的道路成本，然后按照貪心規(guī)則的Dijkstra算法搜索即可。此時(shí)算法流程如圖2所示。

圖2 路況變動(dòng)時(shí)混合算法流程Fig.2 Hybrid algorithm flow when road conditions change

3 實(shí)證分析

3.1 數(shù)據(jù)獲取

高德開放平臺(tái)提供了API接口，可以查詢指定區(qū)域內(nèi)所有道路的交通態(tài)勢(shì)。反饋內(nèi)容包括當(dāng)前時(shí)間、道路名稱、道路坐標(biāo)、道路速度以及當(dāng)前擁堵情況。數(shù)據(jù)獲取間隔為5 min，得到2020年9月至2020年12月共三個(gè)月的交通態(tài)勢(shì)信息，根據(jù)獲取到的道路坐標(biāo)繪制出街道道路圖如圖3所示。

圖3 市區(qū)街道道路圖Fig.3 Urban street map

3.2 車速預(yù)測(cè)

車速使用BP 神經(jīng)網(wǎng)絡(luò)方法進(jìn)行預(yù)測(cè)，設(shè)輸出層有m個(gè)神經(jīng)元，BP網(wǎng)絡(luò)的實(shí)際輸出為y，期望輸出為y′，則損失函數(shù)ε為：

權(quán)值的修正值為：

考慮到坐標(biāo)點(diǎn)較多，對(duì)每個(gè)點(diǎn)的速度進(jìn)行預(yù)測(cè)計(jì)算量極大，故對(duì)同一道路速度取平均值，預(yù)測(cè)整條路的速度。綜上，將當(dāng)前時(shí)間、道路名稱以及道路速度三個(gè)因素作為輸入值，確定輸入節(jié)點(diǎn)數(shù)為3，輸出值為預(yù)測(cè)道路名稱及道路所對(duì)應(yīng)的速度。經(jīng)處理，共有115 條道路，即輸出層所對(duì)應(yīng)的節(jié)點(diǎn)數(shù)為115。隱藏層選為4 層，節(jié)點(diǎn)數(shù)分別為64、128、256、128。網(wǎng)絡(luò)結(jié)構(gòu)如圖4 所示。經(jīng)檢驗(yàn)，日均速度誤差為4.24%，預(yù)測(cè)結(jié)果在可接受范圍內(nèi)。

圖4 車速預(yù)測(cè)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)Fig.4 Neural network structure of vehicle speed prediction

通過數(shù)據(jù)清洗，剔除外圍高速、高架等道路，以交通路口為節(jié)點(diǎn)，根據(jù)主城區(qū)交通布局得到路口節(jié)點(diǎn)分布及其連通情況。

3.3 參數(shù)設(shè)計(jì)

在算法運(yùn)行時(shí)，考慮到希望算法在初期能夠盡可能擴(kuò)大搜索范圍，避免陷入局部最優(yōu)，而在后期則能夠較好收斂，設(shè)置隨機(jī)數(shù)q0與當(dāng)前搜尋次數(shù)相關(guān)，隨著搜尋次數(shù)的增加而增大。

其中，l為當(dāng)前輪次，lmax為總輪次，此處取50。其余參數(shù)設(shè)置：信息素啟發(fā)因子α=3，成本啟發(fā)因子β=2，螞蟻數(shù)量m=15，為在搜索后期保留更多次優(yōu)路徑以供路況發(fā)生擁堵時(shí)選擇，信息素?fù)]發(fā)因子λ=0.9。冷藏車以福田祥菱M1后雙輪冷藏車為原型，空車燃油消耗系數(shù)ρ0=1.2，滿載燃油消耗系數(shù)ρQ=2.4，空車重量Qk=3 385 kg，滿載重量Qm=4 880 kg。考慮裝載時(shí)貨物不能填滿空間，設(shè)載質(zhì)利用系數(shù)Ψ=0.92，貨物單價(jià)P=20 元/kg，運(yùn)輸時(shí)衰減系數(shù)?1=0.03，裝卸時(shí)衰減系數(shù)?2=0.06，早到懲罰系數(shù)ε1=0.002，晚到懲罰系數(shù)ε2=0.005，運(yùn)輸時(shí)制冷成本系數(shù)a=0.01，裝卸時(shí)制冷成本系數(shù)b=0.02，油價(jià)Pf=7.62 元/L，公路運(yùn)輸中單位燃料燃燒產(chǎn)生的碳排放量通常為2～5 kg/L，綜合考慮載重、配送距離、坡度等因素確定單位燃料的碳排放成本為2.67 kg/L[20-21]。2021年首批全國(guó)碳交易市場(chǎng)中碳交易價(jià)格為50 元/T，算得單位碳排放價(jià)格PC=0.138 元/L。

各節(jié)點(diǎn)分布及連通情況如圖5所示，其中藍(lán)色點(diǎn)為交通節(jié)點(diǎn)，橙色點(diǎn)為配送點(diǎn)，綠色點(diǎn)為配送中心，連線表示兩節(jié)點(diǎn)之間可以通行（連線長(zhǎng)度不代表兩點(diǎn)之間實(shí)際距離，實(shí)際距離為獲取數(shù)據(jù)中道路真實(shí)長(zhǎng)度）。

圖5 各節(jié)點(diǎn)分布及連通情況Fig.5 Distribution and connectivity of nodes

考慮到市區(qū)規(guī)劃，模擬出各配送點(diǎn)的坐標(biāo)及其配送需求如表1所示。其中點(diǎn)（14，4）為配送中心，其余點(diǎn)為配送點(diǎn)。

表1 配送點(diǎn)坐標(biāo)及需求（情景1）Table 1 Coordinates and demand of point（Scene 1）

3.4 對(duì)比分析

情景1配送需求如表1所示。

（1）交通情況正常

交通情況正常時(shí)，單獨(dú)使用蟻群算法，在算法運(yùn)行過程中螞蟻會(huì)在運(yùn)輸成本較低的節(jié)點(diǎn)中循環(huán)往復(fù)，即使將最近經(jīng)過的若干節(jié)點(diǎn)引入禁忌表依然無(wú)法收斂。

交通情況正常時(shí)，單獨(dú)使用Dijkstra 算法得到的運(yùn)行軌跡如圖6所示，算法之間運(yùn)算結(jié)果對(duì)比如表2所示。

表2 交通正常時(shí)各算法對(duì)比（情景1）Table 2 Comparison of algorithms in normal traffic（Scene 1）

圖6 交通正常時(shí)Dijkstra算法車輛A-B行駛路線Fig.6 Vehicle A-B route in normal traffic when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運(yùn)行軌跡如圖7所示。

圖7 交通正常時(shí)混合算法車輛A-B行駛路線Fig.7 Vehicle A-B route in normal traffic when using hybrid algorithm

（2）交通發(fā)生擁堵

模擬5：40某路段發(fā)生交通事故造成擁堵且擁堵在40 min 后恢復(fù)時(shí)，單獨(dú)使用Dijkstra 算法時(shí)得到運(yùn)行軌跡如圖8所示。

圖8 交通擁堵時(shí)Dijkstra算法車輛A-B行駛路線Fig.8 Vehicle A-B route in traffic congestion when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運(yùn)行軌跡如圖9所示，運(yùn)算結(jié)果對(duì)比如表3所示。

圖9 交通擁堵時(shí)混合算法車輛A-B行駛路線Fig.9 Vehicle A-B route in traffic congestion when using hybrid algorithm

表3 交通擁堵時(shí)各算法對(duì)比（情景1）Table 3 Comparison of algorithms in traffic congestion（Scene 1）

情景2配送需求如表4所示。

表4 配送點(diǎn)坐標(biāo)及需求（情景2）Table 4 Coordinates and demand of point（Scene 2）

（1）交通情況正常

交通情況正常時(shí)，單獨(dú)使用Dijkstra 算法得到運(yùn)行軌跡如圖10所示，算法之間運(yùn)算結(jié)果對(duì)比如表5所示。

表5 交通正常時(shí)各算法對(duì)比（情景2）Table 5 Comparison of algorithms in normal traffic（Scene 2）

圖10 交通正常時(shí)Dijkstra算法車輛A-B-C行駛路線Fig.10 Vehicle A-B-C route in normal traffic when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運(yùn)行軌跡如圖11所示。

圖11 交通正常時(shí)混合算法車輛A-B-C行駛路線Fig.11 Vehicle A-B-C route in normal traffic when using hybrid algorithm

（2）交通發(fā)生擁堵

模擬5：40某路段發(fā)生交通事故造成擁堵且擁堵在40 min 后恢復(fù)時(shí)，單獨(dú)使用Dijkstra 算法得到運(yùn)行軌跡如圖12所示。

圖12 交通擁堵時(shí)Dijkstra算法車輛A-B-C行駛路線Fig.12 Vehicle A-B-C route in traffic congestion when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運(yùn)行軌跡如圖13所示，運(yùn)算結(jié)果對(duì)比如表6所示。

圖13 交通擁堵時(shí)混合算法車輛A-B-C行駛路線Fig.13 Vehicle A-B-C route in traffic congestion when using hybrid algorithm

可見，在城市交通網(wǎng)絡(luò)內(nèi)蟻群算法無(wú)法完成搜尋任務(wù)。相比于Dijkstra算法，混合算法通過預(yù)留信息素，綜合考慮需求時(shí)間窗、懲罰成本等因素，緩解了在純貪心規(guī)則下由于選擇當(dāng)前道路成本最低而提高整體成本的問題。同時(shí)，由于在每輪搜索時(shí)在當(dāng)前成本最低和總成本最低的路徑上同時(shí)留下信息素，使得當(dāng)總成本最低路徑出現(xiàn)擁堵時(shí)，也能較好找到次優(yōu)解。

在情景1與情景2中，當(dāng)路徑出現(xiàn)擁堵時(shí)，若采用貪心Dijkstra 算法進(jìn)行計(jì)算，所得路徑總成本較使用貪心Dijkstra 算法計(jì)算且交通情況不擁堵時(shí)分別增加了16.76%、11.01%；若采用混合算法進(jìn)行計(jì)算，所得路徑總成本較混合算法進(jìn)行計(jì)算且交通情況不擁堵時(shí)分別僅增加了11.51%、8.38%；而當(dāng)路徑出現(xiàn)擁堵時(shí)，采用混合算法進(jìn)行計(jì)算較Dijkstra 算法相比，所得路徑總成本降低了14.89%、8.02%。同時(shí)，由于預(yù)留了成本修正地圖，在交通情況發(fā)生變化時(shí)不需要重新計(jì)算所有路徑成本，只需計(jì)算交通情況變化路段的成本，因此計(jì)算時(shí)間大大縮短，由原先的124.03 s分別降低到了34.17 s、41.03 s。

通過對(duì)比分析，混合算法能夠有效降低搜尋路徑成本，同時(shí)通過預(yù)留修正成本地圖，減少計(jì)算量，提高搜尋效率，進(jìn)而提高反應(yīng)速度。

4 結(jié)束語(yǔ)

本文以城市局部網(wǎng)絡(luò)模型為對(duì)象，利用歷史數(shù)據(jù)對(duì)未來(lái)一段時(shí)間內(nèi)不同道路的車輛運(yùn)行速度進(jìn)行預(yù)測(cè)，并在此基礎(chǔ)上，分別用蟻群算法、Dijkstra 算法以及蟻群-Dijkstra混合算法進(jìn)行求解。實(shí)例證明：（1）在城市內(nèi)交通網(wǎng)絡(luò)復(fù)雜的情況下，混合算法能夠有效改善蟻群算法無(wú)法有效收斂、Dijkstra算法易陷入局部最優(yōu)的問題，得到較優(yōu)結(jié)果。（2）通過預(yù)留修正成本文件，能夠大幅降低算法計(jì)算時(shí)間，提高應(yīng)對(duì)交通異常時(shí)的響應(yīng)速率。（3）計(jì)算電腦配置為Intel Xeon Processor（Skylake，IBRS）2.30 GHz（4處理器），考慮到單臺(tái)電腦計(jì)算能力有限，若使用邊緣云計(jì)算有望能提高運(yùn)算速度，達(dá)到實(shí)時(shí)處理交通異常問題的能力。