基于改進的蟻群算法求解多目標生鮮農產品車輛路徑

萬 杰,耿 麗,田 喆

1.河北工業大學 經濟管理學院,天津300401

2.河北工業大學 人工智能與數據科學學院,天津300401

當今社會，隨著人們對于生鮮農產品需求量不斷加大，其相應的物流業也得到了快速的發展，生鮮農產品由于易腐敗的性質造成其在調撥分配和運輸方面的問題比較突出，高效率的調配不僅有助于降低企業成本，提高供應效率，而且能夠保證產品質量，提高客戶滿意率[1]，此外，由于國家政策的強制要求和企業的社會責任感，越來越多的企業將碳排放納入發展的目標之中[2]，因此本文以生鮮農產品物流多目標為背景，研究該背景下的帶時間窗的車輛路徑問題(Vehicle Routing Problem with Time Windows,VRPTW)[3]，這是在車輛路徑問題(Vehicle Routing Problem,VRP)的基礎上加入了客戶的時間窗要求，屬于NP 難問題，當問題規模較大時，先驗法難以求出其最優解[4]，因此眾多的學者利用帕累托主導方法來求得滿意解，常見的求解VRPTW 的算法有蟻群算法[5,6]、遺傳算法[7,8]、粒子群算法[9,10]、人工神經網絡算法[11]、模擬退火算法[12]等，然而這些智能算法大多被用于求解單目標VRPTW 問題，很少用于多目標問題，因此研究多目標VRPTW 問題尤為重要。

多目標生鮮農產品車輛路徑問題(Multi-Objective Vehicle Routing Problem with Time Windows,MOVRPTW)是指：在中國“生產者—批發商—零售商—消費者”這樣的生鮮農產品流通過程中，給定若干具有一定裝載容量的車輛和需求量已知的零售商，車輛從批發商出發為所有客戶服務完畢后回到批發商處的過程，且同時盡可能地達到運營成本最低、服務質量最高和碳排放最少的多個目標。與單目標車輛路徑問題相比，多目標的車輛路徑問題更加貼近實際，此外，在決策者進行目標舍取與權重占比的設定上更加易于操作。本文在研究多目標生鮮農產品問題時加入了考慮生鮮農產品腐敗率的送達量和軟時間窗下的準時送達率表示的客戶滿意度，并用價格折扣來代替懲罰成本，因此本文所研究的問題是“考慮價格折扣的帶時間窗的多目標生鮮農產品車輛路徑問題”。

蟻群算法是20 世紀90 年代意大利學者M.Dorigo[13]提出來的，它是一種尋找優化路徑的機率型算法，其核心思想是利用一定數量人工螞蟻的群體協作來尋找最短路徑的過程：即每只螞蟻都遵循覓食規則、移動規則、避障規則、播撒信息素規則的指導，從初始狀態的某一點運動到下一點，逐步完成它們的搜索過程，形成可行解，重復上述過程直至找到最短路徑。這種算法被應用解決TSP問題[14]、Job-shop 調度問題[15]、背包問題[16]和二次指派問題[17]等問題上，但是在多目標車輛路徑問題中的研究比較少。

目前對于多目標問題的求解方法一般為加權法或確定優先因子，實質是求解單目標問題[18]，本文從多個角度出發，考慮生鮮農產品物流的運營成本、服務質量和碳排放等多個因素，將多個目標視為同等重要，應用蟻群算法同時優化多個目標。并在蟻群算法的啟發因子中加入了零售商的需求量，與時間窗一同指導信息素的更新，并將目標權重加入到信息素更新策略中，提高了目標準確度，加快了收斂效率，通過算例驗證了本文提出的模型及改進算法的有效性。

1 價格折扣的多目標生鮮農產品車輛路徑問題

1.1 問題描述與假設條件

本文所研究的是考慮價格折扣的兩級供應鏈的生鮮農產品調撥策略與VRPTW 的多目標優化問題，在車輛數和車輛容量均受限的條件下完成配送任務，并且達到總成本最低，客戶滿意率最高和碳排放最少的目標。本文的假設條件如下：

（1）服務：一輛車可以向多家零售商提供服務，每個零售商均能被服務且只能被服務一次；

（2）裝載：車型固定，且零售商的需求量不能超過車輛的最大載重量；

（3）碳排放：僅受運距和負載量的影響；

（4）軟時間窗：[em,lm]為零售商m的時間窗安排，若到達時間早于時間em，則必須等到em時才可交貨，若晚于lm，則需給予零售商相應的價格折扣作為懲罰。

1.2 參數及變量

對考慮價格折扣的多目標生鮮農產品車輛路徑問題進行參數、變量的設定。

一家批發商(V0)有K輛車，為多家零售商(Vm,m=0,1,2,…,R)提供服務，零售商Vm的需求量為dm；車輛載重為lk，車輛的最大載重量為lck；車輛k從批發商V0出發的時間為；零售商Vm到零售商Vn的距離為cmn，運輸時間為tmn，到達零售商Vm的時間為am，在零售商Vm服務的時間為fm；cf是車輛固定費用，tc是單位運輸成本；零售商Vm的時間窗為[em,lm]，晚于最晚到達時間lm的價格折扣為um(am)，價格折扣公式如下：

2 模型的構建

2.1 滿意度

本文假設每個零售商的時間窗安排不同，且均為軟時間窗約束，假定[em,lm]為零售商m的時間窗安排，若車輛到達時間早于時間em，則必須等到em時才可交貨，若晚于lm，會降低零售商的滿意度，整個運輸會產生附加的成本[19]，在本文中需給予零售商相應的價格折扣作為懲罰，折扣系數為um(am)，折扣系數越小滿意度越高，滿意度函數如圖1 所示。

圖1 零售商滿意度函數Fig.1 Retailers satisfaction function

記客戶m的滿意度函數為S(am)，表示在貨物送達時間為am的服務質量，具體形式如式(2)所示。

2.2 碳排放

估算碳排放的方法有許多，有的模型考慮的因素非常全面，對參數要求也很高，但通過文獻[20]和文獻[21]對模型的對比可知，車輛碳排放與眾多因素有關，包括與車輛相關的固定參數和其他變動因素，其中，油耗和燃油排放因子是影響碳排放最重要且最容易測量的兩個因素，因此，下面的模型估算碳排放量應用比較廣泛，計算結果也更加接近實際，如式（3）。

其中，FR為車輛油耗量率，cmn是從節點m到節點n的距離，cr是燃油排放因子，ζ是轉換系數，P是總牽引功率。

2.3 MO-VRPTW 模型

本文綜合考慮企業對于經濟效益的追求、服務質量的提高和企業的社會責任，將車輛固定費用和運輸成本綜合為運營成本，客戶滿意度為服務質量，考慮載重和運輸距離的碳排放，將三個目標相結合求其帕累托最優解。總成本為F，服務質量為S，碳排放為C，MO-VRPTW 模型的設計如下：

模型中，式（4）是成本目標函數，在考慮產品腐敗的情況下車輛固定成本、運輸成本和懲罰成本；式（5）是顧客平均服務質量目標函數，考慮產品數量到達率和準時到達率；式（6）為碳排放目標函數，考慮運輸距離和載重；式（7）（8）是車輛到達零售商時間的相關約束；式（9）～（12）表示每個零售商只能由一輛車服務一次；式（13）表示車輛從批發商處開始配送，配送完成后回到批發商處；式（14）表示載重不超過車輛的最大載重；式（15）表示在相應的時間范圍內車輛k 送達的有效產品數量；式（16）（17）表示變量非負限制；式（18）（19）為決策變量約束；式（20）為容量約束；式（21）為變量非負限制和時間窗約束。

3 改進的蟻群算法

基本蟻群算法包括啟發因子的構建、狀態轉移規則和信息素的更新等重要組成部分。本文針對基本蟻群算法收斂時間長、易陷入局部最優的缺點，做出了如下改進：在啟發因子中加入了需求量因素，狀態轉移規則采用偽隨機比例搜索和確定型搜索相結合的方法，信息素更新策略采用目標權重影響規則，既加快了算法求解速度，又提高了目標準確度。

3.1 啟發因子構建策略

本文設計的蟻群算法是基于生鮮農產品的車輛路徑問題，為避免錯過時間窗而受到的價格折扣懲罰，在啟發因子中加入需求量Qm變量，設計了以近距離、開始時間早、小時間窗為擇優性原則的蟻群算法，當進行路徑的下一步選擇時，時間窗跨度小的要比時間窗跨度大的零售商的服務更具有優先性[22]，并加入了大需求量的擇優性原則，即當am＞lm時，懲罰成本與需求量成正比，因此，為了規避因錯過時間窗而受到的折扣懲罰，當在進行路徑選擇時，需求量大的零售商比需求量小的零售商更具有配送優先性，啟發因子構建如下：

其中，τmn為零售商m到零售商n路徑上的信息素濃度，ηmn是啟發因子、能見度，零售商m的時間窗跨度wm，wm=lm-em。

3.2 狀態轉移規則構建

其中，r是在區間[0,1]上均勻分布的隨機數，r0（0≤r0≤1）是用來控制狀態轉移規則的參數，α、β分別為信息素和啟發因子的權重，分別表示其相對重要度，tabuk為螞蟻k已經走過的城市列表，即禁忌列表。

為克服隨機轉移搜索速度慢的缺陷，在狀態轉移過程中引入確定型搜索模型，即當r0≥r時，螞蟻k從零售商m到n的選擇規則如式：

令螞蟻k從批發商出發，按照上述規則依次選擇零售商，在達到約束限制時返回批發商處，即完成一次搜索。

3.3 信息素更新策略

本文的信息素更新吸收了蟻周系統模型的核心思想，即在所有螞蟻都形成路徑完成一次迭代后再更新所有路徑上的信息素，這避免陷入局部最優。當完成一次迭代后，將當前可行路徑R與當前最優路徑R*進行比較：（1）若R的總成本、服務質量和碳排放劣于R*，即R受R*支配，則將R路徑上的信息素進行蒸發，即τmn(N+1)=(1-ρ)τmn(N)）（25），其中ρ為揮發系數，0＜ρ≤1；（2）若R的總成本、服務質量和碳排放三個目標均優于R*，R不受R*支配，則對R路徑上的信息素進行沉淀，τmn(N+1)=τmn(N)+Δτmn(N)（26），其中，ω1，ω2，ω3為權重系數，其大小取決于三個目標的相對重要程度，Fmax，Fmin，Smax，Smin，Cmax，Cmin分別為當前迭代次數下相應目標的最大最小值。

3.4 算法流程

本文的算法流程如下：ForN=1 toNmax：#迭代Nmax次，達到一定次數重新初始化信息素矩陣。

Fork只螞蟻：K=1，lk=lck，R=100，tabuk=0，，xomk=0，#初始化參數。

While 存在未遍歷節點：If 超出返回倉庫的時間限制：K=1，lk=lck，R=100，tabuk=0，，xomk=0

Continue#放棄當前解，尋找新解

4 實驗分析

4.1 算例求解

目前研究VRPTW 問題一般采用Solomon 算例來進行驗證，由于本文研究是生鮮農產品VRPTW的多目標優化問題，沒有現成的算例可以使用，所以仍采用Solomon 算例來進行數據分析。實驗表明，蟻群算法的收斂性達到最好時，螞蟻數是節點數的0.6 到0.8 倍[23]，所以設置螞蟻數m=80，迭代次數Nmax=200，α=1，β=3，ρ=0.8，r0=0.8。本文假設柴油貨車以60 km/h 的速度勻速行駛，只考慮運輸距離和載重量，將車輛碳排放模型轉化為：

本文算法用Python3.6 進行編程，實驗環境為windows 10 系統core i5 處理器。

由于篇幅限制，本文改進的模型和算法的實驗下的實驗結果均以Solomon R201 為例，最優解進化曲線圖（以成本為例）如圖2 所示，本文的帕累托最優解分布如圖3 所示，在該組帕累托最優解集中隨機取一個解的車輛路徑分布圖如圖4 所示。

圖2 最優解進化曲線Fig.2 Optimal solution evolution curve

圖3 帕累托最優解分布Fig.3 Pareto optimal solution distribution

圖4 車輛路徑分布圖Fig.4 Vehicle path map

4.2 算法對比

為驗證模型和算法的有效性，將本文的計算結果與Solomon 數據中的目前最優計算結果和文獻[18]中計算結果相比較，由于篇幅限制，僅列出部分數據在本文數學模型下目前所得最優結果與在本文模型與改進的算法下的計算結果比較，以Solomon 數據中的R201 為例，具體結果如表1 所示。

表1 Solomon 最優解、文獻[18]最優解與本文運算結果的比較Table1 Comparison of Solomon optimal solution,reference[18]optimal solution and the results of this paper

通過實驗，將本文的計算結果與文獻[18]、已知最優解進行比較，由表1 可知，在Pareto 最優解集中比較，成本最低的解中，本文的計算結果在成本、服務質量和碳排放上均優于文獻[18]，由于在完成一次迭代后再進行信息素的更新，防止了最優解的局部優化，能夠得到全局最優解，雖然成本和碳排放分別高于已知最優解55.83%和19.42%，但是本文的服務質量優于已知最優解75%，平均成本每升高1%，服務質量提升1.34%，碳排放每多1%，服務質量提升3.86%，這是由于改進的蟻群算法在啟發因子中加入了需求量和時間窗限制，使得計算結果在服務質量上更優；在服務質量最高的解中，雖然成本和碳排放比已知最優解和文獻[18]中的解高，但是服務質量也比其高，這是由于改進的蟻群算法中加入了時間窗跨度和需求量限制，所以在服務質量上的收斂效率更高；在碳排放最低的解中，本文的計算結果在成本、碳排放和服務質量上均優于文獻[18]，雖然成本和碳排放高于已知最優解，但是成本和服務質量每升高1%，服務質量分別提升1.34%和3.86%，這是由于在狀態轉移的過程中受到加入了需求量和時間窗跨度的啟發因子的影響，若要使得三個目標達到完全平衡，可以根據需要調試權重，通過多個目標的靈敏度分析，達到決策者的理想狀態。

5 結論

本文用軟時間窗下的準時送達率和考慮產品腐敗率的準時送達量來表示服務質量，考慮了成本和碳排放量，構建了考慮價格折扣的多目標生鮮農產品車輛路徑問題模型，結合本文模型中懲罰成本與與價格折扣相關聯的特點，設計了改進的蟻群算法，用Solomon 算例證明了本文模型和算法的有效性。本文的模型和改進的算法可以為生鮮企業在配送活動中提供技術支持，極具參考價值。不同目標之間的相互影響程度即目標間的靈敏度分析是本文的后續研究內容。