基于改進蟻群算法的多類型車輛逆向物流路徑優化

郭元元 王 巍 蔣學微

（東北林業大學機電工程學院，黑龍江 哈爾濱 150040）

隨著全球物流網絡的不斷發展和擴展，作為物流管理領域中的重要組成部分，逆向物流逐漸受到關注[1]，研究如何優化逆向物流車輛路徑問題（Vehicle routing problem in reverse logistics，VRPRL）具有重要的理論和經濟意義。逆向物流強調廢棄物品的回收、再利用和環保處置，這一概念的興起為減少資源浪費、降低環境負擔提供了創新的解決途徑。通過將廢棄物重新納入生產循環，逆向物流為企業創造了機會，不僅促進了可持續發展，也有助于構建更環保、經濟且高效的供應鏈體系[2]。

本文研究了單個回收中心和多個回收點的路徑規劃，采用不同類型的車輛從回收中心出發去往若干回收點。為便于分析，做出以下9個假設。1）只有一個回收中心且能滿足全部需求。2）回收中心有多種不同型號的回收車輛，所有回收車輛的實際載重不能超過其額定載重Qk。3）回收車輛對所分配的所有客戶提供服務后，需要重新返回回收中心。4）每個回收點都有服務且只能被一輛車服務一次。5）每個回收點的位置、回收量和時間窗要求等信息都己知。6）所有車輛運行工作時間均相同且每輛車的工作時間不得超過其最大運輸時間。7）車輛的行駛速度為時變速度。8）每輛車均使用相同型號的消毒設施與消毒液。9）回收車輛應在客戶規定的時間窗內到達收集點。

1 模型的建立

1.1 車輛管理使用成本

車輛的使用管理成本包括車輛的發車成本和人力成本，其中人力成本為總行駛距離與單位費用的乘積。根據車輛型號的不同，發車成本和單位費用的值是不同的，則車輛的管理使用成本Z1如公式（1）所示。

式中：N為回收節點集合，N={i，j|i，j=0，1，2，...，N}；0代表回收中心；K為車型集合，K={k|k=1，2，...K}；Mk為k類型車輛的編號，集合為m，Mk={m|m=1，2，...，Mk}，m∈Mk；為k型車輛的發車成本，元；為k型車輛單位距離所產生的折舊費和人力成本，元/km；為0～1的變量，如果k類型車輛m從節點i駛向節點j，則為1，否則為0。

1.2 油耗成本

本文采用Barth等[3]提出的綜合模式排放模型（comprehensive modal emission model，CMEM），通過該模型計算車輛的燃油消耗量，如公式（2）所示，并進一步列出油耗成本，如公式（3）所示。

式中：、和分別為k類型車輛的發動機模塊系數、速度模塊系數和載重模塊系數；為k類型車輛m在時間段u內在道路（i，j）上的行駛距離；rk為k類型車輛的自重，kg；υiju為車輛在時間段u內在道路（i，j）上的行駛速度；為k類型車輛m在時間段u內行駛在道路（i，j）上的載質量，kg；為車輛m在時間段u內在道路（i，j）上的油耗量，L；Cf為單位油耗費用，元/L；為0～1的變量，如果k類型車輛m在時間段u內從節點i到j，則為1，否則為0。

1.3 碳排放成本

車輛的燃油消耗是造成碳排放的主要因素。研究表明，車輛的碳排放與燃油消耗呈正比。因此碳排放成本如公式（4）所示。

式中：FE為燃油排放參數，取值為2.621kg/L[4]；Ce為單位碳排放費用，元/kg。

1.4 時間懲罰成本

為保證按時完成回收任務滿意，應嚴格要求回收時間，時間懲罰成本函數Z4如公式（5）所示。

式中：c1為早到懲罰因數，元/min；c2為晚到懲罰因數，元/min；Tim為車輛m到達回收點i的時間；[ETi，LTi]為回收點i的服務時間窗。

1.5 消毒成本

消毒成本指的是對回收人員、車輛以及回收物品進行消毒所產生的費用。消毒費用主要包括車輛本身、回收人員和回收物品。總的消毒成本Z5如公式（6）所示。

式中：Sk為k類型車輛的表面積；p0為每個回收人員的消毒成本；p1為單位面積內消毒液的價格；p2為單位物品的消毒成本。

由上述分析可知，本文構建的多車型GVRPRL的非線性規劃模型如公式（7）所示。

2 算法設計

傳統的蟻群算法通常在靜止的情況下進行，但現實中道路條件會發生改變[5]。在靜態條件下，算法不能適應真實的交通狀況。同時，蟻群算法易受局部信息的影響，導致蟻群在搜索過程中只選取幾條路線，而忽視其他可能更好的路線。蟻群進行路徑選擇時采用的局部信息素或啟發式方法，會使蟻群只選取一條路徑，不能對整個搜索空間進行高效搜索。為了改善上述問題，該文采用改進的蟻群算法。

2.1 算法中揮發因子ρ的改進

對揮發系數進行動態調節來提高算法的適應性。在初始階段，增大揮發系數可以使螞蟻搜索可能解的空間更廣闊，從而得到全局最優結果。在迭代中，逐步降低揮發系數可以延長信息素在路徑上的累積時間，加快收斂速度，由此可得揮發系數如公式（8）所示。

式中：t為當前迭代次數；T為總迭代次數；x為最優解連續未進化的循環次數；xmax為一常數值；λ為控制揮發因子衰減速度的一個常數。

為了避免ρ衰減太多進而影響算法的性能，本文設置了一個ρmin值，當x=xmax時，就按照ρ（t）的方式降低ρ值，并將x置為0再次計數，按照此過程進行循環，直至ρ衰減到最小值ρmin為止。

2.2 基于精英螞蟻策略的信息素更新方法

本文引入精英螞蟻策略來提升算法的收斂速度，將每次迭代過程中總回收成本最小的精英螞蟻a作為優化目標，對其進行信息素更新，如公式（9）～公式（11）所示。

式中：ρ為揮發率，0≤ρ＜1；為螞蟻b在路段（i，j）上的信息素增加量；為精英螞蟻a在路段（i，j）上的信息素增加量；H為與信息素軌跡相關的常數；Zb為螞蟻b的總配送費用；ε為精英螞蟻信息素的權重。

2.3 狀態轉移概率的設置

在蟻群算法中，最主要的問題是狀態轉移和信息素更新[6]。本文研究的是為回收中心提供一種總成本最小的回收策略，因此啟發式因子ηij如公式（12）所示。

狀態轉移概率的計算過程如公式（13）所示。

式中：allowedm為螞蟻m在下一步可以選擇的位置集合；α為信息素的相對重要程度；β為期望啟發因子的相對重要程度；Tij為節點i、j間的信息素濃度；τis為位置點i到初始點的信息素濃度。

3 算例分析

程序在MATLAB R2021a 中進行編程和實現，蟻群算法的種群數量為20，迭代次數為400，ρ=0.3，ρmin=0.1，xmax=10，λ=3，ε=4，H=10，α=1，β=3。對某回收中心的回收路徑進行優化，采用3種類型車輛進行回收服務。回收中心的工作時間為6:00～22:00，共16h，即960min.根據城市交通規律，將上午7:00～9:00和下午18:00～20:00設定為交通擁堵時間段（即早、晚高峰時間段）。在此期間，車輛以擁堵速度υc行駛，在非擁堵時間段，車輛以正常速度υf行駛，υf和υc的取值分別為60km/h和20km/h。回收車輛參數[7]來自慶鈴汽車官方網站。回收車輛信息見表1，其中包括每種車型的自重、最大載質量、發車成本、折舊和人力成本、各項模塊系數以及車輛表面積等信息。涉及的回收點需求信息見表2，其中0表示回收中心；編號1～20表示20個回收點；X、Y分別表示回收中心和回收點的橫、縱坐標。

表1 回收車輛信息表

表2 回收點需求信息表

分別采用傳統蟻群算法（ACO）和改進后的蟻群算法（IACA）來實現該回收中心與各回收點間的運輸，所求結果如圖1、圖2和表3所示。

圖1 傳統蟻群算法的回收路徑

圖2 改進蟻群算法的回收路徑

表3 蟻群算法和改進后的蟻群算法對算例的運算結果

從上述算例的運算結果可知，傳統的蟻群算法和改進后的蟻群算法均需要3種車型來運輸。在傳統蟻群算法的路徑優化方法下，車輛載重率波幅較大，最大載重率為91.89%，最低為63.90%，最終總運輸距離為555.79km，總行駛時間為2465.60min，總運輸成本為3287.86元，油耗和碳排放成本之和為1125.15元。在本文改進蟻群算法的路徑優化方法下，車輛載重率相對穩定，載重率最大為90.85%，最低為74.66%。最終總運輸距離為464.20km，減少了91.59km；總行駛時間為2377.43min，減少了88.17min；總運輸成本為2651.80元，減少了636.06元；油耗和碳排放成本之和為1022.25元，減少了102.90元。從上述各項結果的分析可知，改進后的蟻群算法無論在車輛使用數量和載重率方面，還是在總運輸距離、總行駛時間、總成本、油耗和碳排放成本等方面均優于傳統蟻群算法，說明改進后的蟻群算法性能更優，能得到更小的總目標值，而且油耗和碳排放量的降低也響應了國家綠色物流的號召，達到了節能減排的目的。

4 結語

優化和改善逆向物流回收過程中的車輛路徑問題可以更有效地利用車輛和人力資源，降低資源浪費。同時，通過車輛優化路徑，可以減少行駛距離和行駛時間，從而降低運輸成本，也有效降低了車輛行駛過程中產生的油耗和碳排放。科學合理的車輛路徑優化不僅有助于企業提高效益和競爭力，還有助于保護環境，推動可持續發展。比傳統蟻群算法相比，本文的改進蟻群算法在尋優能力和尋優效率方面均有明顯改善，對企業高效利用資源有重要現實意義，也符合可持續發展的理念。