考慮動態(tài)擁堵的城市配送綠色車輛路徑問題研究

摘 要：針對目前研究城市配送車輛路徑多未考慮交通動態(tài)擁堵對運(yùn)營成本的影響，本文將道路擁堵因素引入綠色車輛路徑問題（GVRP）的優(yōu)化數(shù)學(xué)模型中，以不同的擁堵速度來反應(yīng)各時間段的交通狀況，并考慮碳排放和客戶時間窗的影響，建立了以總成本最小化為目標(biāo)的優(yōu)化模型，設(shè)計了蟻群-遺傳混合算法（ACO-GA）進(jìn)行求解。并結(jié)合案例進(jìn)行分析，將所得結(jié)果與蟻群算法（ACO）、遺傳算法（GA）進(jìn)行比較，驗證了模型和算法的可行性和有效性，降低了總成本和碳排放，為企業(yè)節(jié)約成本和綠色轉(zhuǎn)型提供了有力支持。

關(guān)鍵字：綠色車輛路徑問題；動態(tài)擁堵；碳排放；蟻群-遺傳混合算法

中圖分類號：TP 30" " " " " 文獻(xiàn)標(biāo)志碼：A

隨著城市化進(jìn)程加速，城市交通狀況越來越復(fù)雜，環(huán)境污染問題也越來越嚴(yán)重。因此，城市配送綠色車輛路徑問題是目前綠色物流的重要研究領(lǐng)域[1]。在城市配送環(huán)節(jié)中，車輛的合理使用和規(guī)劃可以有效提高交通運(yùn)輸效率、縮短配送時間并降低物流成本，同時也能降低對環(huán)境的負(fù)面影響，保護(hù)生態(tài)環(huán)境，提高城市居民的生活質(zhì)量。將綠色交通理念和城市可持續(xù)發(fā)展理念相結(jié)合，不僅可以推動城市綠色發(fā)展，還可以提高城市的品牌形象和吸引力[2]。

本文關(guān)注城市交通動態(tài)擁堵的GVRP，即一個配送中心為多個客戶點(diǎn)進(jìn)行配送?？紤]不同時間段的車輛行駛速度受交通狀況影響，找到最佳的車輛調(diào)度和路徑規(guī)劃方案，以達(dá)到最小化總成本的目標(biāo)。為了便于分析，本文做出以下7個假設(shè)。1）配送的車輛為同類型車輛且能滿足全部需求。2）車輛配送完成后，需要返回配送中心。3）每個客戶點(diǎn)的需求量不超過車輛的載重且只能被服務(wù)一次。4）已知每個客戶點(diǎn)的需求量、位置坐標(biāo)和時間窗要求等信息。5）車輛的工作運(yùn)營時間不得超過其最大運(yùn)輸時間。6）車輛為非恒速行駛。7）車輛提早或者遲到到達(dá)需要承擔(dān)相應(yīng)懲罰。

1 模型構(gòu)建

1.1 車輛碳排放率和油耗率的計算

不僅行駛距離會影響車輛的碳排放量，車速、車輛載重、交通擁堵和車輛特征等因素也會影響油耗和碳排放。本文使用HICKMAN[3]提出的MEET模型進(jìn)行計算，碳排放率估計函數(shù)如公式（1）所示。

（1）

式中：υ為車輛行駛速度，使碳排放率最小的最優(yōu)速度υ*為71km/h[4]；r0、r1、r2、r3、r4、r5、r6分別為預(yù)定義參數(shù)。

載重修正因子LC如公式（2）所示。

（2）

式中：γ為車輛實(shí)際載重與額定載重的比值；ω0、ω1、ω2、ω3、ω4、ω5、ω6、ω7分別為預(yù)定義參數(shù)，其取值受車輛載重的影響。

由此可得車輛的碳排放率ciju（kg/km），如公式（3）所示。

ciju=σ（υ）LC/1000 （3）

本文取1L汽油可以產(chǎn)生2.32kg的碳排放量[5]，計算得出1kg碳排放量對應(yīng)的油耗量為?=1/2.32=0.431L/kg，進(jìn)而得出車輛的油耗率如公式（4）所示。

fiju=?ciju （4）

1.2 數(shù)學(xué)模型

根據(jù)上述分析，將所有車輛的使用成本、油耗成本、碳排放成本以及時間懲罰成本之和作為優(yōu)化目標(biāo)構(gòu)建GVRP模型，如公式（5）～公式（13）所示。

總成本最小化如公式（5）所示，其中車輛的使用成本包括固定發(fā)車成本、行駛時間成本、服務(wù)時間成本和等待時間成本。

（5）

式中：N為節(jié)點(diǎn)集合，N={i，j|i，j=0，1，1，...，N}；0為配送中心；M代表車輛的編號集合，M={m|m=1，2，...，M}；U為路段劃分集合，U={u|u=1，2，...，U}；f1、f2、f3分別為車輛的單位發(fā)車成本、單位時間成本和單位人力成本；υiju為車輛在時間段u內(nèi)在道路（i，j）上的行駛速度；tijum為車輛m在時間段u內(nèi)以速度υiju在道路（i，j）上行駛的時間；stim為車輛m在節(jié)點(diǎn)i的服務(wù)時間；wtim為車輛m提前到達(dá)節(jié)點(diǎn)i的等待時間；cf為單位油耗費(fèi)用；ce為單位碳排放費(fèi)用；Gi為懲罰系數(shù)；Tim為車輛m到達(dá)節(jié)點(diǎn)i的時間；[ETi，LTi]為客戶點(diǎn)i的服務(wù)時間窗；Lim為車輛m離開節(jié)點(diǎn)i的時間；xm是0～1的變量，當(dāng)車輛m使用時為1，否則為0。

每個客戶點(diǎn)只能被服務(wù)一次，如公式（6）所示。

（6）

式中：xijm是0～1的變量，當(dāng)車輛m從客戶點(diǎn)i駛向客戶點(diǎn)j則為1，否則為0。

車輛只能從配送中心出發(fā)，并在工作完成后返回配送中心，如公式（7）所示。

（7）

如果客戶點(diǎn)i由車輛m服務(wù)，則為1，否則為0，如公式（8）所示。

（8）

式中：yim是0～1的變量。

車輛的m實(shí)際載質(zhì)量不得超過該車輛的負(fù)載能力，如公式（9）所示。

（9）

式中：qi為客戶點(diǎn)i的需求量；Q為配送車輛的容量。

車輛使用數(shù)量不能超過配送中心車輛可用數(shù)量，如公式（10）所示。

（10）

各車輛的運(yùn)行工作時間不得高于其最大運(yùn)輸時間，如公式（11）所示。

（11）

式中：tij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的運(yùn)輸時間；Tm為車輛m的最大運(yùn)輸時間。

dijum和dij間的限制關(guān)系如公式（12）所示。

dijum≤ dijhijum" i∈N，j∈N，u∈U，m∈M （12）

式中：dijum代表車輛m在時間段u內(nèi)在道路（i，j）上的行駛距離；dij代表從節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離；hijum代表0～1的變量，當(dāng)車輛m在時間段u內(nèi)從節(jié)點(diǎn)i到j(luò)時則為1，否則為0。

車輛到達(dá)客戶的時間、服務(wù)時間與離開時間的關(guān)系如公式（13）所示。

Tim+stim≤ Lim，i∈N，m∈M （13）

2 算法設(shè)計

2.1 對選擇下一節(jié)點(diǎn)概率的改進(jìn)

在蟻群算法中，改進(jìn)選擇下一節(jié)點(diǎn)的概率對優(yōu)化搜索效率和結(jié)果質(zhì)量至關(guān)重要。這種改進(jìn)可以增強(qiáng)算法的靈活性，使其更好地適應(yīng)復(fù)雜多變的問題環(huán)境。通過調(diào)整概率計算方式，算法能夠在探索新路徑和利用已知最優(yōu)路徑間找到更好的平衡，從而提高找到全局最優(yōu)解的概率。此外，這種改進(jìn)還有助于加快算法的收斂速度，減少無效探索，有效提升算法的總體性能和應(yīng)用價值。本文通過引入顧客點(diǎn)時間窗口間隔因素widthj=LTj-ETj來求解下一節(jié)點(diǎn)服務(wù)的緊急程度，并將等待時間長度因素waitj=ETj-Tj加入蟻群算法中。因此，螞蟻從一個點(diǎn)向另一個點(diǎn)的移動遵循公式（14）所示的規(guī)則[6]。

（14）

式中：τij和ηij分別為信息素濃度和能見度（ηij=1/dij）；α、β、φ、δ分別為信息素濃度、能見度、時間窗口間隔因素和等待時間長度因素的相對重要性，取值分別為1、2、2、3；r為隨機(jī)變量，在[0，1]上服從均勻分布，r0（0≤r0≤1）是用來控制轉(zhuǎn)移規(guī)則的參數(shù)。

2.2 信息素?fù)]發(fā)因子ρ的改進(jìn)

通過對蟻群算法中的信息素?fù)]發(fā)因子ρ進(jìn)行改進(jìn)，能夠進(jìn)一步提高算法解決問題的能力。調(diào)整信息素?fù)]發(fā)速度有助于保持算法在全局搜索和局部搜索間的動態(tài)平衡，避免算法過早陷入局部最優(yōu)而忽視了其他潛在的優(yōu)秀解。這種平衡確保了算法在搜索過程中既能廣泛探索解空間，又能有效利用當(dāng)前已知的最優(yōu)路徑，從而在提高解的質(zhì)量和搜索效率方面有更好的表現(xiàn)。當(dāng)ρ過小時，蟻群很容易重新選擇以前的路徑，從而極易陷入局部最優(yōu)值；當(dāng)ρ取較大的數(shù)值時，雖然可以提高其整體尋優(yōu)能力，但是迭代次數(shù)也會顯著增加，從而影響其收斂速度。在此基礎(chǔ)上，本文引入了一種隨迭代次數(shù)增加呈高斯分布的信息素?fù)]發(fā)因子ρ，如公式（15）所示。

（15）

式中：k為迭代次數(shù)，服從參數(shù)σ、μ的高斯分布；σ、μ、a的值可進(jìn)行自適應(yīng)調(diào)整，本文σ、μ取值分別為7.6、100。

2.3 路徑交叉

針對蟻群算法的迭代問題，本文提出了一種基于遺傳算法的改進(jìn)方法，因此擬采用遺傳算法中的染色體交叉作業(yè)，對每一次迭代后獲得的運(yùn)動軌跡進(jìn)行二次優(yōu)化，以提高解決問題的效率和質(zhì)量。通過模擬自然選擇的機(jī)制，遺傳算法可以在蟻群算法的基礎(chǔ)上進(jìn)一步探索解空間，提供更多樣化的解候選。這種結(jié)合能夠加快算法的收斂速度，提高找到全局最優(yōu)解的概率，尤其是在處理復(fù)雜多變的優(yōu)化問題的過程中，能夠有效避免陷入局部最優(yōu)解，增強(qiáng)算法的魯棒性，具體操作包括以下4點(diǎn)。1）在現(xiàn)有算法的迭代過程中選取當(dāng)前最好的路線，將所有路線的1/n作為群體的一部分，采用輪盤賭的方式，產(chǎn)生剩余的（n-1）/n個初始群體。2）在初始群體中隨機(jī)選擇2條路線，將其作為親本進(jìn)行染色體交叉。3）在此基礎(chǔ)上，對親代路徑上所有相同的節(jié)點(diǎn)進(jìn)行隨機(jī)選擇，并對其進(jìn)行分段交叉作業(yè)，得到2條子路徑。4）在所有的子路線中尋找最佳路線，如果路線的總費(fèi)用低于目前路線或者全局路線，就用它來替代目前路線和全局路線。

2.4 算法步驟

本文的改進(jìn)蟻群算法求解優(yōu)化模型共包括7個步驟。1）構(gòu)建車輛運(yùn)輸模型，調(diào)試算法參數(shù)，設(shè)置起點(diǎn)和終點(diǎn)位置。2）螞蟻從起點(diǎn)出發(fā)尋找最優(yōu)運(yùn)動路徑。3）根據(jù)引入的啟發(fā)式函數(shù)的概率公式，得出螞蟻的下一個移動節(jié)點(diǎn)。4）判斷每只螞蟻是否移動到終點(diǎn)，如果到達(dá)終點(diǎn)，算法運(yùn)行下一步，否則返回第3步。5）記錄每只螞蟻的路徑長度，選擇當(dāng)前迭代中的最優(yōu)路徑，并更新全局最優(yōu)路徑。6）在當(dāng)前迭代中，根據(jù)遺傳算法的染色體交叉操作來選取路徑進(jìn)行交叉重組，用交叉后的路徑替換當(dāng)前最優(yōu)路徑與全局最優(yōu)路徑。7）判斷是否達(dá)到終止條件，如果是，則輸出全局最優(yōu)解，否則返回第2步。

3 算例仿真

對某配送中心的配送路徑進(jìn)行優(yōu)化，使用同種類型車輛來進(jìn)行服務(wù)，運(yùn)輸車輛容量為4t，車輛對應(yīng)的碳排放率的系數(shù)r為r0=110、r1=0、r2=0、r3=0.000375、r4=8702、r5=0和r6=0[3]。與其相對應(yīng)的載重修正因子系數(shù)為ω0=1.27、ω1=0.0614、ω2=0、ω3=-0.0011、ω4=-0.00235、ω5=0、ω6=0和ω7=-1.33。其他費(fèi)用的參數(shù)設(shè)置為f1=550元/輛、f2=80元/h、f3=30元/h、cf=7.95元/L和ce=0.0528元/kg[4]。配送中心的工作時間是6：00～22：00，總計16h，即960min。本文將早上7：00～9：00、晚上18：00～20：00設(shè)置為交通擁擠時段，在這段時間內(nèi)，車輛會以擁堵速度υc行駛，其他時段以正常車速υf行進(jìn)，υf和υc分別取值為71km/h和20km/h?？蛻粜畔⒁姳?，其中0代表配送中心。

本文在MATLAB R2021a中對程序進(jìn)行編程和實(shí)現(xiàn)，其中蟻群算法的種群數(shù)量為50，迭代次數(shù)設(shè)置為400，、α、β、φ、δ取值分別為1、2、2、3；遺傳算法的種群規(guī)模為80，迭代次數(shù)為400，交叉算子為0.9，變異算子為0.1。

分別采用傳統(tǒng)的ACO、GA和改進(jìn)后的ACO-GA來求解該問題模型，所求結(jié)果見表2。

由表2的數(shù)據(jù)結(jié)果可知，在基于ACO算法的求解方法下，車輛最終配送總成本為7007.12元，總運(yùn)行距離為757.93km，總行駛時間為1182.67min，其中車輛使用成本為4687.01元，油耗和碳排放成本為1567.73元，時間懲罰成本為752.38元。在基于GA算法的求解方法下，車輛最終配送總成本為7619.74元，總運(yùn)行距離為887.83km，總行駛時間為1411.57min，其中車輛使用成本為4924.72元，油耗和碳排放成本為1874.87元，時間懲罰成本為820.15元。在本文ACO-GA算法的求解方法下，車輛最終配送總成本為6675.72元，比對照組減少了331.28元、943.9元；總運(yùn)行距離為887.83km，比對照組減少了45.88km、175.78km；總行駛時間為1411.57min，比對照組減少了215.69min、444.59min。其中車輛油耗和碳排放成本為1486.68元，比對照組減少了81.05元、388.19元；時間懲罰成本為586.12元，比對照組減少了166.26元、234.03元。由此可以得出結(jié)論，本文算法比對照組具有較好的可行性和有效性，不僅能為企業(yè)節(jié)約總成本，減少資源浪費(fèi)，還能有效降低碳排放量，推動城市的綠色發(fā)展。另外，時間懲罰成本的降低也表明，用該算法對模型進(jìn)行求解能使車輛到達(dá)客戶點(diǎn)更準(zhǔn)時，用戶體驗感更好。

4 結(jié)語

隨著對環(huán)境保護(hù)意識的提升，綠色物流在城市配送中越來越重要。在車輛路徑規(guī)劃中提高配送效率、減少配送成本和提升客戶體驗是城市配送中的重要目標(biāo)。配送效率的提升需要更快速、更準(zhǔn)時的配送，而成本的降低則能提高企業(yè)的競爭力。同時，優(yōu)質(zhì)的客戶體驗也能增加客戶的忠誠度，促進(jìn)業(yè)務(wù)增長。同時，考慮環(huán)保因素、降低碳排放并推動城市朝著可持續(xù)的方向發(fā)展也具有重要的現(xiàn)實(shí)意義。因此本文提出了一種考慮動態(tài)擁堵的城市配送綠色車輛路徑優(yōu)化模型，并設(shè)計了蟻群-遺傳混合算法進(jìn)行求解。研究發(fā)現(xiàn)，本文建立的模型和提出的算法可有效降低車輛的配送成本、縮短運(yùn)輸距離并減少行駛時間。同時，車輛油耗和碳排放量也得到了有效降低，這不僅減少了溫室氣體排放，對環(huán)境有益，也為企業(yè)的可持續(xù)發(fā)展奠定了良好基礎(chǔ)。

參考文獻(xiàn)

[1]張得志，張湘鵬，王潤澤，等.基于兩階段的超大型城市物流網(wǎng)絡(luò)選址與服務(wù)路徑優(yōu)化[J].鐵道科學(xué)與工程學(xué)報，2023，20（4）：1270-1279.

[2]王常博.低碳城市視角下我國綠色物流發(fā)展研究[J].物流科技，2022，45（18）：24-26.

[3]HICKMAN A J.Methodology for calculating transport emissions and energy consumption[R].European：Cold Starts，1999.

[4]李進(jìn)，張江華.基于碳排放與速度優(yōu)化的帶時間窗車輛路徑問題[J].系統(tǒng)工程理論與實(shí)踐，2014，34（12）：3063-3072.

[5]TORO E M，F(xiàn)RANCO J F，ECHEVERRI M G，et al.A multi-objective model for the green capacitated location-routing problem"considering environmental impact [J].Computers amp; Industrial engineering，2017（110）：114-125.

[6]吳雋，陳定方，李文鋒，等.基于改進(jìn)蟻群算法的有時間窗車輛路徑優(yōu)化[J].湖北大學(xué)學(xué)報，2008，23（3）：9-12.