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

郭元元 王 巍 蔣學(xué)微

（東北林業(yè)大學(xué)機電工程學(xué)院，黑龍江 哈爾濱 150040）

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

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

1 模型的建立

1.1 車輛管理使用成本

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

式中：N為回收節(jié)點集合，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型車輛的發(fā)車成本，元；為k型車輛單位距離所產(chǎn)生的折舊費和人力成本，元/km；為0～1的變量，如果k類型車輛m從節(jié)點i駛向節(jié)點j，則為1，否則為0。

1.2 油耗成本

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

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

1.3 碳排放成本

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

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

1.4 時間懲罰成本

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

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

1.5 消毒成本

消毒成本指的是對回收人員、車輛以及回收物品進行消毒所產(chǎn)生的費用。消毒費用主要包括車輛本身、回收人員和回收物品?？偟南境杀綵5如公式（6）所示。

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

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

2 算法設(shè)計

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

2.1 算法中揮發(fā)因子ρ的改進

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

式中：t為當(dāng)前迭代次數(shù)；T為總迭代次數(shù)；x為最優(yōu)解連續(xù)未進化的循環(huán)次數(shù)；xmax為一常數(shù)值；λ為控制揮發(fā)因子衰減速度的一個常數(shù)。

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

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

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

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

2.3 狀態(tài)轉(zhuǎn)移概率的設(shè)置

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

狀態(tài)轉(zhuǎn)移概率的計算過程如公式（13）所示。

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

3 算例分析

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

表1 回收車輛信息表

表2 回收點需求信息表

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

圖1 傳統(tǒng)蟻群算法的回收路徑

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

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

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

4 結(jié)語

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