基于蟻群算法對調(diào)度車輛進(jìn)行路徑最優(yōu)化設(shè)計(jì)

曾 勝，戴賢君，胡徐勝，滕官宏偉

（1.皖江工學(xué)院 電氣工程學(xué)院，馬鞍山 243000；2.中國計(jì)量大學(xué) 生命科學(xué)學(xué)院，杭州 310018；3.中國人民解放軍陸軍裝備部，株洲 412002）

冷鏈物流泛指冷鏈產(chǎn)品在運(yùn)輸、銷售、消費(fèi)的全過程，冷鏈運(yùn)輸是一項(xiàng)非常復(fù)雜的系統(tǒng)工程，自從物聯(lián)網(wǎng)大會(huì)成立以來，國家重視發(fā)展冷鏈物流行業(yè)，但是隨著新冠疫情的來臨，冷鏈行業(yè)受到重挫，但是其功能的強(qiáng)大是不容忽視的。文獻(xiàn)[1]針對已知工作環(huán)境，研究了移動(dòng)機(jī)器人在復(fù)雜三維環(huán)境的路徑規(guī)劃的問題，提出一種改進(jìn)的蟻群優(yōu)化算法。文獻(xiàn)[2]基于蟻群算法對水下潛器三維空間路徑規(guī)劃問題進(jìn)行了研究。文獻(xiàn)[3]基于改進(jìn)蟻群算法，提高了在倉儲(chǔ)系統(tǒng)三維空間內(nèi)路徑規(guī)劃的效率與速度。文獻(xiàn)[4]針對傳統(tǒng)二維平面的隨機(jī)搜索算法—蟻群優(yōu)化算法不能滿足三維空間路徑搜索以及快速性要求等問題，提出了改進(jìn)的方法。文獻(xiàn)[5]針對蟻群優(yōu)化（ACO）算法存在收斂速度慢以及易陷入局部最優(yōu)的問題，提出了一種改進(jìn)的ACO 算法來解決機(jī)器人路徑規(guī)劃問題。文獻(xiàn)[6]提出一種改進(jìn)的蟻群算法，引入了障礙探索的方法，將下一節(jié)點(diǎn)附近一定區(qū)域的障礙狀況作為影響因素，如果影響螞蟻尋找最優(yōu)路徑，則會(huì)規(guī)避此節(jié)點(diǎn)。文獻(xiàn)[7]提出一種基于多目標(biāo)優(yōu)化的改進(jìn)蟻群算法，在考慮路徑長度的基礎(chǔ)上將轉(zhuǎn)向次數(shù)加入啟發(fā)函數(shù)中。文獻(xiàn)[8]提出一種基于資源狀態(tài)的自適應(yīng)蟻群優(yōu)化算法 （MACO），利用虛擬機(jī)的狀態(tài)來修正啟發(fā)式因子和釋放信息素濃度。文獻(xiàn)[9]提出了基于改進(jìn)蟻群算法規(guī)劃機(jī)器人全局路徑，在柵格地圖中劃定優(yōu)選區(qū)域，并建立新的初始信息素濃度設(shè)置模型，對各點(diǎn)初始信息素濃度進(jìn)行差異化設(shè)置，避免尋優(yōu)的盲目性。文獻(xiàn)[10]提出改進(jìn)蟻群算法的有效性和合理性，其降低了復(fù)雜程度，優(yōu)化了傳統(tǒng)蟻群算法容易陷人局部最優(yōu)的問題，提升了迭代運(yùn)算的收斂速度。文獻(xiàn)[11]在傳統(tǒng)蟻群算法基礎(chǔ)上提出一種改進(jìn)的蟻群算法，先后分別采用局部最優(yōu)和全局最優(yōu)兩種方式對傳統(tǒng)蟻群算法的信息素更新方式加以擴(kuò)大至最優(yōu)解尋覓范圍。文獻(xiàn)[12]采用改進(jìn)的蟻群算法對靜態(tài)交通網(wǎng)絡(luò)和動(dòng)態(tài)交通網(wǎng)絡(luò)分別進(jìn)行最短路徑的求解。本文利用傳統(tǒng)的蟻群算法對配送車輛以及配送路徑作出最優(yōu)化選擇并建立模型，達(dá)到節(jié)約運(yùn)輸成本并準(zhǔn)時(shí)運(yùn)送貨物的目的。

1 車輛調(diào)度模型的建立

1.1 模型條件的假設(shè)

此模型設(shè)計(jì)假設(shè)只有一個(gè)物流中心點(diǎn)并把冷鏈物流食品運(yùn)送到各個(gè)網(wǎng)點(diǎn)，確保冷鏈?zhǔn)称房焖龠\(yùn)輸?shù)侥康牡兀竺總€(gè)配送點(diǎn)只能由一輛車進(jìn)行配送且完成配送任務(wù)后需重返配送中心，其目標(biāo)是優(yōu)化配送車輛的路徑使得在時(shí)間窗約束下總成本最低。圖1所示為冷鏈物流中心點(diǎn)到各個(gè)城市的調(diào)度點(diǎn)。

圖1 車輛行駛路徑示意圖Fig.1 Schematic diagram of vehicle driving path

對于冷鏈物流調(diào)度設(shè)置以下幾個(gè)條件：

（1）調(diào)度中心只有一個(gè)調(diào)度點(diǎn)。

（2）不同的城市所對應(yīng)的路徑不同。

（3）中途配送過程中不增加新的任務(wù)。

（4）調(diào)度過程中要保證道路行駛過程通暢，無障礙物阻擋。

（5）配送車輛行駛距離必須能滿足車輛配送條件。

（6）車輛調(diào)度數(shù)量應(yīng)滿足具體使用數(shù)量；配送車輛必須集中到唯一的調(diào)度中心點(diǎn)。

（7）每次調(diào)度車輛的數(shù)量必須滿足客戶需求；調(diào)度車輛中心必須知道客戶使用車輛的具體位置，客戶也必須知道調(diào)度車輛的具體位置。

（8）所有調(diào)度車輛的硬件設(shè)施、速度與型號相同；在配送車輛時(shí)保證每個(gè)車輛的油箱是加滿狀態(tài)以便于調(diào)度時(shí)的費(fèi)用計(jì)算；調(diào)度點(diǎn)把車駕駛到客戶的具體位置時(shí)其花費(fèi)的每公里費(fèi)用一樣。

1.2 調(diào)度模型相關(guān)參數(shù)的設(shè)定

首先對調(diào)度車輛模型的目標(biāo)函數(shù)進(jìn)行設(shè)定：n 表示車輛調(diào)度點(diǎn)具體車輛數(shù)；B 表示用戶調(diào)度車輛所花費(fèi)的固定費(fèi)用；sn表示所有車輛調(diào)度花費(fèi)的固定成本；n 輛車中每輛車單獨(dú)所花費(fèi)的固定成本為r0；Q 表示調(diào)度車輛每行駛1 km 所花的行駛費(fèi)用；dij表示調(diào)度點(diǎn)第i 輛車與第j 個(gè)客戶之間的距離；λ1表示車輛在調(diào)度過程中所產(chǎn)生的油耗；λ2表示在調(diào)度車輛過程中單位時(shí)間產(chǎn)生的額外費(fèi)用；t 表示調(diào)度車輛所消耗的時(shí)間；v 表示在調(diào)度過程中的車輛行駛的平均速度；ρ1表示用戶在等待時(shí)所產(chǎn)生的額外費(fèi)用系數(shù)；k1表示單位時(shí)間內(nèi)產(chǎn)生的費(fèi)用；ρ2表示客戶在還車時(shí)單位時(shí)間內(nèi)所產(chǎn)生的損失系數(shù)；k2表示在還車時(shí)產(chǎn)生的單位比例費(fèi)用。

運(yùn)輸車輛固定成本為

假設(shè)本模型的運(yùn)輸過程中的成本只與車輛行駛的距離有關(guān)，其運(yùn)輸過程成本分別包括車輛行駛成本、車輛行駛額外成本、車輛還車時(shí)的成本為

調(diào)度過程中產(chǎn)生損失的運(yùn)算公式即為

即整個(gè)車輛調(diào)度費(fèi)用為

2 傳統(tǒng)蟻群算法的模型建立

2.1 ACO 蟻群算法具體步驟

對蟻群中各螞蟻的爬行路徑進(jìn)行仿真模擬，根據(jù)具體情況定義各個(gè)參數(shù)：設(shè)m 表示螞蟻爬行的總體數(shù)量；bi（t）表示在某個(gè)t 時(shí)刻某個(gè)位置i 的螞蟻個(gè)數(shù)；dij表示位置點(diǎn)i 與螞蟻爬行位置點(diǎn)j 之間的距離；ηij表示坐標(biāo)（i，j）的螞蟻爬行能見度，反映了由調(diào)度點(diǎn)第i 個(gè)螞蟻爬行位置點(diǎn)移到調(diào)度點(diǎn)j 的啟發(fā)程度；τij表示螞蟻位置（i，j）上的信息素強(qiáng)度；Δτij表示螞蟻在坐標(biāo)（i，j）上留下的軌跡信息素量單位長度；表示螞蟻的轉(zhuǎn)移概率，i 是螞蟻目前的具體坐標(biāo)，j 是螞蟻還沒有訪問的具體位置；Lk表示螞蟻爬行的總路程；Nc表示此路線迭代次數(shù)；Nmax表示此路線最大迭代次數(shù)；Q 表示螞蟻在爬行過程中釋放的信息素濃度。

螞蟻總數(shù)為

兩地行駛距離為

螞蟻單次循環(huán)不可重復(fù)訪問的轉(zhuǎn)移概率為

設(shè)定ρ 表示信息素?fù)]發(fā)程度，揮發(fā)程度表示為

式中：ΔCijk為第k只螞蟻在車輛行駛位置點(diǎn)i 與車輛行駛位置點(diǎn)k之間釋放的增加的信息素濃度；ΔCij為所有螞蟻在i 與j 之間釋放的增加的信息素濃度，其信息素增加公式為

比較NC和Nmax的大小，計(jì)算結(jié)果并輸出。該算法中螞蟻個(gè)數(shù)為m=100，信息素濃度隨路徑改變進(jìn)行設(shè)定。Nmax=200 表示最大路線迭代次數(shù)。

2.2 傳統(tǒng)蟻群算法仿真模型

（1）假設(shè)迭代次數(shù)為N=200，螞蟻數(shù)量為100，信息素濃度為0.1，Alpha=1。圖2所示為迭代次數(shù)與行駛路徑圖。

圖2 蟻群算法仿真Fig.2 Ant colony algorithm simulation

（2）假設(shè)迭代次數(shù)為N=200，螞蟻數(shù)量為100，信息素濃度為0.2，Alpha=2。圖3為迭代次數(shù)與行駛路徑圖。

圖3 蟻群算法仿真Fig.3 Ant colony algorithm simulation

（3）假設(shè)迭代次數(shù)為N=200，螞蟻數(shù)量為10，信息素濃度為0.3，Alpha=3。圖4為迭代次數(shù)與行駛路徑圖。

圖4 蟻群算法仿真Fig.4 Ant colony algorithm simulation

2.3 基于傳統(tǒng)蟻群算法模型改進(jìn)

n 表示路徑數(shù)量，螞蟻在爬行過程中適當(dāng)改變信息素濃度，即引入?yún)?shù)α，稱為信息素減弱系數(shù)，其取值范圍為（0，1），針對信息素增量調(diào)整如下：

信息素更新公式為

通過這種優(yōu)化信息素更新的方法，不僅能夠加快算法的收斂速度，同時(shí)還會(huì)增加最優(yōu)路徑被選中的機(jī)率，但又不會(huì)完全排除其它路徑成為最優(yōu)路徑的可能性。

由三維的路徑公式可知，其m 只螞蟻當(dāng)中的第k 只螞蟻的轉(zhuǎn)移公式為

式中：q0為［0，1］隨機(jī)分配函數(shù)，為其中一個(gè)函數(shù)。

基于啟發(fā)函數(shù)的基礎(chǔ)，Πβ（β＝1，2，3，…，n）上的任一點(diǎn)Pβ（iβ，jβ，kβ）的螞蟻選擇平面上Πβ+1（iβ+1，jβ+1，kβ+1）的概率為

式中：τβ+1為Πβ+1平面上點(diǎn)Pβ+1（iβ+1，jβ+1，kβ+1）的信息素量。

傳統(tǒng)的二維蟻群路徑優(yōu)化算法已不能滿足復(fù)雜眾多的數(shù)據(jù)，三維蟻群算法的改善增強(qiáng)了其優(yōu)化功能，如下取迭代次數(shù)為N=200，螞蟻數(shù)量為100，信息素濃度為0.1，Alpha=3。其車輛調(diào)度路徑添加其優(yōu)化函數(shù)，則改進(jìn)后的三維螞蟻爬行路徑與迭代次數(shù)如圖5所示。

圖5 改進(jìn)后蟻群算法路徑圖Fig.5 Path diagram of improved ant colony algorithm

3 調(diào)度實(shí)際花費(fèi)計(jì)算

3.1 配送路徑規(guī)劃

傳統(tǒng)的車輛調(diào)度只是利用二維調(diào)度，沒有考慮實(shí)際因素，而三維調(diào)度可以把實(shí)際情況考慮到調(diào)度因素上。表1為二維與三維坐標(biāo)表。

表1 8 個(gè)調(diào)度點(diǎn)二維與三維坐標(biāo)Tab.1 Two-dimensional and three-dimensional coordinates of 8 scheduling points

設(shè)定蟻群螞蟻數(shù)量N=100，運(yùn)算次數(shù)為200 次，其釋放信息素濃度隨之改變，Alpha 也隨之改變。表2為車輛行駛實(shí)際距離所示。

表2 給客戶派送車輛時(shí)其實(shí)際距離Tab.2 Actual distance when sending vehicles to customers

3.2 配送費(fèi)用函數(shù)

配送中心對各個(gè)客戶點(diǎn)進(jìn)行配送，在同一個(gè)配送中心進(jìn)行調(diào)度車輛。每輛車每公里運(yùn)輸費(fèi)用為3元，平均車速為60 km/h，駕駛員正常工作費(fèi)用為每小時(shí)10 元。利用上述模型，應(yīng)用Matlab 進(jìn)行算列求解，表3為兩種算法的成本對比。

表3 算法改進(jìn)前后具體調(diào)度成本Tab.3 Specific scheduling costs before and after algorithm improvement

在應(yīng)用Matlab 仿真后，利用蟻群算法求解物流路徑最優(yōu)解。在相同的迭代次數(shù)情況下，未優(yōu)化路徑之前物流配送路徑的平均長度要遠(yuǎn)遠(yuǎn)大于最優(yōu)路徑長度。在人員調(diào)度的情況下行駛里程最大節(jié)約了將近22 km，在二維算法調(diào)度距離為22 km，三維則為20.5 km。在模擬實(shí)現(xiàn)物流運(yùn)輸車配送軌跡時(shí)，根據(jù)不斷調(diào)整道路的擁堵情況時(shí)物流車的配送軌跡也會(huì)得到相應(yīng)的改變，從表3可以看出三維路徑其優(yōu)化距離更短。在算法中，路徑是不斷變化的，所以需要實(shí)時(shí)觀察，選取接近直線路徑的最優(yōu)解。

4 結(jié)語

本文對冷鏈物流路徑優(yōu)化的研究是圍繞路徑優(yōu)化求解算法和數(shù)學(xué)模型展開的，首先給出了冷鏈物流研究的背景和意義，根據(jù)冷鏈物流配送路徑優(yōu)化問題的特性，分析其成本構(gòu)成要素，給出貨損成本的數(shù)學(xué)模型，以配送過程中總成本最小為優(yōu)化目標(biāo)，建立對應(yīng)的目標(biāo)函數(shù)，并一一列出存在的約束條件；接著對求解路徑優(yōu)化問題的算法做簡要闡述，同時(shí)說明了蟻群算法的特性和適用性，并將蟻群算法應(yīng)用到冷鏈物流路徑優(yōu)化配送問題中。之后，給出基礎(chǔ)蟻群算法的基本步驟和原理，驗(yàn)證模型和算法的有效性和優(yōu)越性，假設(shè)某種模型配送為例，從軟件分析結(jié)果找到配送方案，給出一系列分析數(shù)據(jù)，最終結(jié)果表明，利用三維蟻群算法求解最優(yōu)路徑時(shí)具有一定的優(yōu)越性。