基于改進的蟻群算法的目標物流車輛路徑優化

曾 勝，王 兵，戴賢君

（1.皖江工學院電氣信息工程學院，安徽馬鞍山 243000；2.安徽工業大學電氣與信息工程學院，安徽馬鞍山 243000；3.中國計量大學生命科學學院，浙江杭州 310000）

0 引 言

冷鏈物流是指在整個物流過程中對溫度敏感的產品（如食品、藥品、化學品等）進行溫度控制和監測的一種物流管理方式。冷鏈物流的發展受到全球經濟、技術創新和消費者需求等多方面因素的影響。全球化趨勢促使企業將供應鏈整合到全球范圍內，這對冷鏈物流提出了更高的要求。協同作業、跨國合作和全球供應鏈的整合需要更高水平的冷鏈技術和管理。

冷鏈物流的發展已經近幾十年了，但是冷鏈物流的路徑設計一直困擾著物流公司，在路徑行駛過程中總會遇到障礙物或者路況復雜的情況，針對此類情況車輛在行駛過程中應找到一條無障礙路線，縮短運輸時間，降低運輸成本，為物流公司節約成本。文獻[1]提出了一種自適應調整啟發函數解決機器人路徑規劃問題的改進蟻群算法；文獻[2]改進了蟻群算法的狀態轉移方式和信息素更新方式，引入最大最小蟻群算法與2-opt 局部搜索算法；文獻[3]在文中闡述所有螞蟻遍歷完所有待訪問的收貨點后搜索到的所有路徑上的信息素進行更新而導致算法收斂和計算效率降低等缺陷，改進了算法中的狀態轉移概率公式，優化了信息素濃度設定和更新方式；文獻[4]構建多核心的蟻群選擇算法，并設計深度選擇定義模型，利用臨界預設法設計路徑優化的選擇方法。文獻[5]針對傳統蟻群優化（ACO）算法搜索路徑時易陷入局部最優、路徑過長、轉彎角度過大等問題，提出一種基于轉彎角度約束的改進ACO 算法。文獻[6]提出一種改進的蟻群優化（IACO）算法，利用工作環境的全局信息建立目標吸引函數，提高蟻群選擇最佳路徑到達目標點的概率，縮短了算法的迭代時間；文獻[7]提出一種改進蟻群算法，動態改進信息素更新策略和啟發因子，并采用可行解先行策略；文獻[8]基于多約束條件對傳統蟻群算法狀態轉移啟發函數和信息素進行了改進，較好地改善了算法的動態優化性能；文獻[9]針對傳統蟻群算法在解決室內疏散問題時存在收斂速度慢、容易陷入局部最優的缺陷問題，將火場的動態參數引入到蟻群算法中，對其路徑選擇策略、啟發函數和信息素更新策略進行改進，為整個疏散群體求解更優的疏散路徑；文獻[10]研究物流路徑優化問題，目的是有效降低物流配送距離，實現配送任務完成的高效率與低成本，通過對基本蟻群算法啟發函數的優化提出改進蟻群算法。文獻[11]采用局部最優和全局最優兩種方式對傳統蟻群算法的信息素更新方式加以擴大至最優解尋覓范圍，并對啟發因子的函數定義范圍擴展至初始節點。文獻[12]對客戶選擇策略采取分段計算的方法，以加快算法的收斂速度，并在構建一條完整的閉合路徑時過濾距離路徑較遠的客戶，提高搜索最優路徑的能力。文獻[13]設計隨迭代時間改變的信息素濃度更新機制，改進蟻群算法實現放牧路徑隨牧場條件變化的及時優化，解決持續放牧的盲目性。

基于上面的研究成果，本文提出一種改進最優最差蟻群算法和啟發因子算法進行路徑優化的方法，此類方法可以縮短車輛行駛路徑、節約時間，以最快的時間把生鮮產品運輸到目的地。

1 目標物流車輛路徑優化模型

本文以某H 公司為例，該公司的主要營業產品為運送冷鏈物流產品，產品主要由食品、生鮮產品等組成，其主要配送任務是把產品運輸到各個網點，以達到客戶的需求。為了下面建模方便，本文調查了該公司每月的運輸量，圖1 為2022 年一年的運輸量。

圖1 冷鏈物流每個月運輸量

根據圖1 可以看出，2022 年各月份對冷鏈物流產品需求量不一樣，特別在夏季的時候對冷鏈物流的需求量大幅度增加，此時就會增加冷鏈物流公司的壓力，為了解決面臨的問題，要在時間、成本上節約，那此時就需要規劃好路徑。

1.1 問題描述

目標車輛運輸過程中其目的在于降低運輸成本，保證生鮮冷鏈物流產品在規定的時間內到達目的地。針對本文研究狀況提出以下假設：

1）冷鏈物流運輸車輛必須從始發地裝滿貨物出發運送到目的地，再從目的地空車返回始發地。

2）對于車輛在運輸過程中，保證其在每個運輸點消耗的時間在一定的范圍內。

3）車輛在滿載過程中與空載過程中其行駛速度穩定，不考慮其擁堵情況。

4）對于運輸所有車輛必須要保證滿載貨物不能超過其車輛運輸的最大限度。

5）所有車輛型號保持一樣且司機身體健康良好。

6）每輛車只服務本次指派的任務，不增加其他任務指標。

1.2 數學模型

傳統的車輛運輸沒有考慮碳的排放運輸成本，本文研究設計主要從兩個方面降低運輸成本：一是降低碳的排放成本；二是車輛運輸成本。式（1）為總的運輸成本。

1.2.1 碳排放因素成本

《碳排放權交易管理辦法（試行）》已于2020 年12 月25 日由生態環境部部務會議審議通過，自2021年2月1 日起施行。此政策的出臺致力于解決碳排放對環境產生的影響，本文冷鏈物流車的運輸是通過燃油車進行運輸，由于電動車行駛距離較近，不適合冷鏈物流的運輸，所以采用燃油車進行運輸，在使用燃油車的同時也應最大程度降低其運輸成本，其中如下兩個因素影響碳的排放成本：

1）冷鏈物流車的行駛速度影響碳的排放成本；

2）冷鏈物流車重量影響冷鏈物流車的排放標準。

G為冷鏈物流車重量，v為車輛行駛的速度，dij為倉庫到客戶之間的距離，xi為坐標點的橫坐標，yi為坐標點的縱坐標，(xi1,yi1)為倉庫坐標，(xi2,yi2)為客戶點坐標，k為運輸車輛數量，每千米固定燃油消耗為M，碳的每千米固定排放量為q，每千米碳排放成本為s，N= 1,2,…,n為物流點坐標點，α1為速度系數，α2為冷鏈物流車重量系數。

車輛行駛速度與重量不同，則排放成本不同，其成本計算公式如下：

速度成本：

重量成本：

碳排放總成本：

1.2.2 運輸成本

1）固定成本

假設B0為冷鏈物流車與工作人員固定費用，xijk為決策變量，該固定費用主要包括運輸過程中折損費用、司機的工資等費用。以下公式為冷鏈物流運輸過程中固定費用：

2）制冷成本

為保證冷鏈產品足夠新鮮，本文要控制制冷箱的溫度，針對此類情況就會產生一個制冷成本，由于制冷成本與時間有關系，由此假設t1為倉庫到卸貨點時間，由于卸貨過程中也會產生一個時間，設定為t2，假設每分鐘行駛過程中的固定成本為Y1元，卸貨過程中每分鐘花的成本為Y2元，則制冷總成本如下：

3）運輸成本

冷鏈物流車運輸過程中也會產生相應的成本，比如車輛的油費，但是由于運輸車輛重量影響油費的高低，那么設置每千米油耗率為β，β0為初始油耗率，公式如下：

4）損耗成本

?1為貨物在勻速行駛過程中新制冷系數，?2為打開車廂物品制冷系數，t3為打開車廂時間。

5）總運輸成本

總的運輸成本主要由碳排放因素成本與運輸成本構成。

約束條件：

2 算法模型

2.1 環境建模

本文針對蟻群算法采用柵格法進行路徑規劃，柵格法在Matlab 中仿真矩陣主要采用0、1 兩個數據，0 代表無障礙物，1 代表有障礙物，柵格的設計主要以黑白為主，模型中柵格設計主要以正方形或者長方形為主，依次對網格區間設計各個區域。為表示網格的各個位置，使用了一種連續的標序，從左到右、從上到下依次排列，形成了一個完整的柵格圖，圖2 為環境模擬圖。

圖2 路徑模型柵格圖

2.2 傳統的算法模型

傳統的蟻群算法的研究設計如下：假設t時刻第k只螞蟻從i位置點爬行到下個位置點j，設置初始釋放的信息素為τij和啟發信息βij，同時設置轉移概率為Pk ij，α為信息素啟發因子，β為期望啟發式因子，dij表示從i位置點到j位置點的距離，ηij為期望啟發式函數。則有：

螞蟻在經過路徑時會釋放信息素，由于信息素隨時間的推移產生揮發，傳統蟻群在爬行過程中會產生迭代，此時會更新信息素，信息素更新公式如下：

式中：ρ是信息素揮發系數，一般設置為0 ＜ρ＜1；Δτij(t)表示是螞蟻爬行從i城市到j城市t時刻的最佳釋放信息素量；Q表示釋放信息素的強度；Lbest表示螞蟻爬行的最佳路徑長度。

2.3 改進后的算法模型

改進后的蟻群算法主要對螞蟻爬行過程中的釋放因子進行改進，由于螞蟻在爬行過程中其信息會發生很大的變化，對其信息素的收集會發生兩種變化：一是所有螞蟻爬行過程中螞蟻群會選擇另外一只優等螞蟻而不是起初的優等螞蟻，此時螞蟻爬行過程中不同路徑釋放的信息素濃度會發生改變，由于在爬行過程中選擇優等的螞蟻，此時通過計算公式得出多個螞蟻釋放的信息素濃度；二是所有螞蟻在爬行結束過程中選擇其信息素濃度，但是由于優等螞蟻不只是一個，有多條路徑由多只螞蟻釋放的信息素濃度，此時尋找出的路徑看不出哪條路徑是最優路徑，可能隨機尋找出其中一條釋放出信息素濃度比較多的一條路徑，這種表面選擇出來的路徑并不代表是最優的路徑，導致路徑的選擇發生改變。針對這兩類情況，本文對蟻群算法的路徑進行優化。

對于最優路徑的尋找，規定了只有在最優路徑上面的信息素濃度才會逐漸增加，非最優路徑上的信息素都會慢慢揮發直至沒有；其次，為了盡量避免出現搜索停滯的現象，把信息素限定在一個區間[τmin,τmax]中，任何大于或低于這個區間的信息素都會相應的用τmin、τmax進行替換。優化公式如下：

若τij(t) ≥τmax，則：

若τij(t) ＜τmin，則：

1）最優最差蟻群算法改進

最優最差蟻群算法的改進思想是通過更大限度地增強最優解，縮減更小的最差解，這樣做的目的是使得螞蟻在爬行路徑中優化路線的信息素濃度與劣勢路徑信息素濃度彼此之間差距變大，促使螞蟻都爬向優化路線那條路徑，此時螞蟻爬行基本上聚集在最優路線上，該方法也是改變傳統的螞蟻爬行路徑，當信息素釋放完，更新最差路徑信息素濃度。

式中：ε為引入的算法參數；τ(i,j)為兩地之間的信息素軌跡；Lbest為搜索路徑中最優長度；Lworst為搜索路徑中最差長度。

2）啟發因子算法改進

由于螞蟻在爬行過程中有熱搜索過程，螞蟻爬行過程中所謂繞開障礙物是指，由于在爬行過程中遇到路徑區域溫度高于其正常生存溫度，此時螞蟻就會繞開此路徑，那此時螞蟻的整個爬行路徑會隨之發生改變，對其啟發因子就會產生影響。針對此類情況，本文對其傳統的啟發因子進行改進，引入一個自適應因子μ，dik為第k輛車到i點的距離，djk為第k輛車到j點的距離，啟發因子的改進公式如下：

轉移概率公式為：

2.4 改進后的算法步驟

改進后算法步驟如下：

Step1：初始化信息素。在問題空間中的每個可能的解都有一個與之相關的信息素值τij。初始時，信息素值通常被設置為與τij相等的小值。

Step2：初始化蟻群。在問題空間中隨機放置螞蟻數量為k，每只螞蟻從問題的一個解空間點開始。

Step3：螞蟻路徑選擇。每只螞蟻按照一定的規則選擇移動路徑，通常螞蟻選擇路徑的概率與路徑上的信息素濃度和路徑距離dij有關，信息素濃度高的路徑和之前螞蟻走過的路徑有更大的概率被選擇。

Step4：改進算法螞蟻移動。螞蟻按照選擇的路徑移動到下一個解空間點。在移動過程中可以考慮引入一些隨機性，加入最優最差、啟發因子算法的多樣性。

Step5：更新信息素。當所有螞蟻完成移動后，根據其走過的路徑更新路徑上的信息素。通常路徑上的信息素會蒸發，則引入[τmin,τmax]信息素濃度，此外由于熱區域的影響，引入新的啟發因子η*ij，然后根據螞蟻的移動路徑和問題的優化目標增加新的信息素。

Step6：重復迭代最大迭代次數Ncmax。重復上述步驟多次，直到滿足停止條件Ncmax＜N。停止準則可以是達到一定的迭代次數、找到滿意的解或其他預定條件。

Step7：輸出結果。最后從所有螞蟻的移動路徑中選擇一條最優解作為算法的輸出。

3 目標物流車路徑優化實證

3.1 路徑模擬仿真

設置初始釋放的信息素為τij和啟發信息βij，同時設置轉移概率為Pkij，α為信息素啟發因子，β為期望啟發式因子，ρ是信息素揮發系數，Q表示釋放信息素的強度，ε為引入的算法參數，μ為自適應因子，Ncmax為最大迭代次數。各參數設置如表1 所示。

表1 參數設置

圖3 為傳統蟻群算法的路徑優化仿真圖。圖4 為改進后蟻群算法的路徑優化仿真圖。

圖3 傳統的蟻群算法仿真

圖4 改進后的蟻群算法仿真

根據圖3 與圖4 仿真對比可以看出，經過改進后的蟻群算法路徑更近且收斂性更好，更符合冷鏈物流公司的設計方案。

3.2 成本計算

本文以H 冷鏈物流公司為例，對其參數與路徑坐標進行設置。G為冷鏈物流車標準重量6 t，v為車輛行駛的速度60 km/h，dij為倉庫到客戶之間的距離，k為運輸車輛數量，每千米固定燃油消耗為M=0.08 L，碳的每千米固定排放量為q=0.3 mg，每千米碳排放成本為s=0.5 元，設置物流車數量為k=15，α1為速度系數0.2，α2為冷鏈物流車重量系數0.3。t1為倉庫到卸貨點時間3 h，卸貨過程中也會產生一個時間t2為1 h，假設每分鐘行駛過程中的固定成本為Y1=10 元，卸貨過程中每分鐘花的成本為Y2=2 元，每千米油耗率為β=0.06 L，初始油耗率β0=0.03 L，?1為貨物在勻速行駛過程中新制冷系數0.3，?2為打開車廂物品制冷系數0.5，t3為打開車廂時間2 min。車輛行駛坐標如表2 所示。

表2 車輛行駛坐標

表2 為車輛可供選擇的路線，通過蟻群算法和優化后蟻群算法選擇出路徑最短的路線，再計算相應的成本。從表中可以看出3號路線路徑最短，那么所花的成本最低。

根據表2 選擇dij為3 號路線的距離。表3 為成本計算表。通過表3 成本計算可以看出：利用蟻群算法的模型可以降低運輸成本；優化后的成本比傳統蟻群算法的成本要低。

表3 成本計算表元

4 結 語

本文通過研究表明，H 冷鏈物流公司運輸量較大，通過蟻群算法模型設計明顯提升了運輸效率，大大增加了公司的運輸量，但本文同時也對傳統蟻群算法進行改進，優化車輛路徑，使得H 冷鏈物流公司達到了最低成本，有效地節約了配送成本，改善了物流配送的效率。

注：本文通訊作者為曾勝。