帶時(shí)間窗的低碳車輛配送路徑優(yōu)化研究

文/王浩青 鄭金諾

針對(duì)當(dāng)前環(huán)境問(wèn)題日益嚴(yán)峻，低碳車輛配送路徑優(yōu)化在減少碳排放方面有著重要意義。在以往的車輛配送路徑問(wèn)題中只考慮經(jīng)濟(jì)成本最小而忽略了碳排放。本文首先將碳排放轉(zhuǎn)化為碳排放成本，構(gòu)建了總成本最小的目標(biāo)優(yōu)化模型，其次采用蟻群算法對(duì)優(yōu)化模型進(jìn)行求解，最后通過(guò)算例驗(yàn)證了模型的有效性，為減少車輛碳排放提供參考和決策支持。

0.引言。

近年來(lái)，物流活動(dòng)成為了我社會(huì)經(jīng)濟(jì)發(fā)展的必要條件，隨著配送需求不斷增加，配送車輛數(shù)量也隨之增加，勢(shì)必會(huì)產(chǎn)生更多的碳排放，實(shí)現(xiàn)低碳車輛配送路徑是解決環(huán)境的關(guān)鍵。優(yōu)化車輛行駛路線，即求解車輛路徑問(wèn)題（Vechicle Routing Problem，VRP），1959年由Dantzi和RamserP[1]首次提出，是0-1整數(shù)規(guī)劃的NP-Hard問(wèn)題。Solomom[2]等首次引入時(shí)間窗概念，即（Time Windows VRP）TWVRP。Jabali[3]等提出了軟時(shí)間窗的VRP問(wèn)題模型。低碳車輛路徑問(wèn)題（Low-carbon Vehicle Routing Problem,LCVRP）是基于傳統(tǒng)車輛路徑問(wèn)題（VRP）的研究基礎(chǔ)，加入了碳排放的約束。已有不少文獻(xiàn)研究了碳排放因素對(duì)物流運(yùn)輸業(yè)的影響，當(dāng)市場(chǎng)中存在碳交易機(jī)制時(shí)，物流配送路徑問(wèn)題便需要考慮碳排放帶來(lái)的成本。在減少車輛碳排放方面，吳麗榮[4]等建立了車輛燃料消耗的模型并進(jìn)行求解?？祫P[5]等人在模糊約定時(shí)間窗車輛路徑優(yōu)化問(wèn)題研究中考慮了碳排放因素并轉(zhuǎn)化為碳排放成本。代楚楚和徐菱[6]建立了基于時(shí)間依賴車輛路徑問(wèn)題模型的快遞企業(yè)低碳配送車輛路徑選擇模型，并設(shè)計(jì)了多種群遺傳算法對(duì)模型進(jìn)行求解。王鈺青[7]等將車輛行駛路程、運(yùn)輸途中載貨量和碳排放量進(jìn)行綜合考慮，建立基于最小碳排放量的廣義旅行商模型來(lái)尋求最優(yōu)配送路徑。本文從上述問(wèn)題入手，研究考慮碳排放因素的帶時(shí)間窗車輛物流配送路徑優(yōu)化問(wèn)題，引入碳排放成本機(jī)制，構(gòu)建以總成本為目標(biāo)的數(shù)學(xué)模型，同時(shí)采用蟻群算法進(jìn)行求解出最優(yōu)路徑方案。

1.問(wèn)題描述。

一個(gè)配送中心為多個(gè)客戶點(diǎn)提供配送服務(wù)，客戶點(diǎn)的坐標(biāo)、時(shí)間窗、需求量已知，目標(biāo)是求解出總成本最小化的最優(yōu)路徑方案。為了界定研究范圍，作出如下假設(shè)：（1）車輛為同質(zhì)車輛，車輛完成任務(wù)后返回配送中心（2）各個(gè)客戶點(diǎn)均有時(shí)間窗要求，不能提前或者延后服務(wù)（3）客戶需求量小于車輛最大裝載量（4）車輛配送過(guò)程中速度保持恒定，不受道路情況影響（5）車輛在客戶點(diǎn)服務(wù)時(shí)，不會(huì)產(chǎn)生碳排放。

2.模型構(gòu)建

2.1 符號(hào)定義

為配送客戶點(diǎn)的集合，u∈U；U0為配送中心和客戶點(diǎn)構(gòu)成的集合，U0=U∪{0}，0表示配送中心；A為節(jié)點(diǎn)之間弧的集合，A={（i，j），i≠j，i∈N，j∈N}；K為配送車輛k的集合，k∈K；qt為客戶點(diǎn)q的需求，且maxqt≤Q，i∈U；[ei，li]為客戶點(diǎn)i的服務(wù)時(shí)間窗；dij為客戶點(diǎn)i和客戶j之間的距離；r為每使用一輛車的租賃成本；v為車輛行駛速度；γ為二氧化碳排放系數(shù)；s為碳排放成本。

Xik為0-1變量，當(dāng)節(jié)點(diǎn)i由車輛k服務(wù)時(shí)值為1，否則為0；Xik為0-1變量，當(dāng)弧（i，j）上有車輛行駛時(shí)值為1，否則為0。yik為0-1變量，當(dāng)車輛在?。╥，j）上行駛時(shí)值為1，否則為0。

2.2 碳排放計(jì)算公式。由于Barth的綜合油耗模型考慮到車輛載重、速度和行駛距離對(duì)車輛油耗的影響，能夠給出任意載重和速度組合下車輛勻速行駛時(shí)的綜合油耗，所以本文采用其油耗模型，并引入碳排放系數(shù)γ，以此將油耗量轉(zhuǎn)換為碳排放量，N表示發(fā)動(dòng)機(jī)轉(zhuǎn)速，V表示機(jī)排量，v表示車輛速度，d表示行駛距離，μ代表車輛自重，f表示車輛的裝載量，ξ表示燃料與空氣質(zhì)量比，A表示車輛正面表面積，κ表示常量，ηtf表示車輛轉(zhuǎn)動(dòng)效率，θ表示道路角度，g表示引力常數(shù)，Cd表示空氣阻力系數(shù)，Cr表示滾動(dòng)阻力系數(shù)，ρ表示空氣密度，λ=ξ/κψ，γ=1/（1000ηtfη），α=τgsinθ+gCrcosθ，β=0.5CdAρ，化簡(jiǎn)后如式（1）所示，F(xiàn)=λ（kNV+γβv3+γα（μ+f）v）d/v=λ

式（1）可以分為三個(gè)部分，第一部分kNV/v可以認(rèn)為是發(fā)動(dòng)機(jī)模塊的油耗，為與行駛時(shí)間呈正比例關(guān)系的線性函數(shù)，第二部分γβdv2可以被認(rèn)為是速度模塊的油耗，為速度的二次函數(shù)，第三個(gè)部分γα（μ+f）d為重量模塊的油耗，獨(dú)立于速度和行駛時(shí)間，與車重和行駛距離直接相關(guān)。

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

式（3）表示每輛車只使用一次；式（4)表示流量守恒；式（5）表示每個(gè)客戶需求得到滿足；式（6）表示車輛服務(wù)完客戶點(diǎn)離開(kāi)；式（7）表示車輛到達(dá)和離開(kāi)是同一客戶點(diǎn)；式（8）表示每個(gè)客戶只被服務(wù)一次；式（9）-（11）表示決策變量。

3.蟻群算法求解。

蟻群算法是螞蟻之間是相互幫助，如果螞蟻在一條沒(méi)有走過(guò)的路上行走時(shí)，會(huì)隨機(jī)選擇一條路，在此路程中會(huì)留下信息素，路徑越長(zhǎng)，留下的信息素濃度會(huì)越少，相反，信息素的濃度就會(huì)越多，后面行走的螞蟻通過(guò)自身感知信息素濃度的高低來(lái)決定走哪條路，信息素濃度越高，螞蟻選擇這條路的概率就會(huì)越大。經(jīng)過(guò)長(zhǎng)時(shí)間后，螞蟻通過(guò)傳遞自身的信息素從而形成一種正反饋機(jī)制。最終，所有的螞蟻會(huì)找到一條距離最短的路徑也就是最優(yōu)路徑。蟻群算法具有較強(qiáng)的魯棒性[8]，因?yàn)橄伻核惴ǖ膮?shù)較少，對(duì)初始解的依賴性低，對(duì)它的基本模型進(jìn)行簡(jiǎn)單修改便可以應(yīng)用到其他眾多領(lǐng)域。因此在車輛配送中，車輛對(duì)初始路線選擇的隨機(jī)性較高，基于蟻群算法這一特性，在對(duì)車輛行駛路線搜索過(guò)程中不斷調(diào)整，從而獲取最優(yōu)路徑。本文研究的配送車輛路徑規(guī)劃中，每個(gè)車輛代表螞蟻，各個(gè)客戶點(diǎn)與配送中心之間的相互距離表示行走的路線?；谏厦嫠龅脑韺④囕v的行駛路線形成一個(gè)正反饋機(jī)制，在本文設(shè)計(jì)配送路線中，形成一個(gè)滿足約束條件的最短路徑，從而降低車輛產(chǎn)生的碳排放。蟻群算法在解決帶時(shí)間窗的車輛配送問(wèn)題時(shí)，算法步驟如下：Step 1初始化蟻群算法各個(gè)參數(shù)，設(shè)置蟻群數(shù)量m，t時(shí)刻時(shí)?。╥，j）的信息素濃度為τij；Step 2每只螞蟻從配送中心出發(fā)，爬行路徑由信息素濃度確定，將所有在客戶點(diǎn)的螞蟻下一個(gè)訪問(wèn)的客戶點(diǎn)集合存儲(chǔ)到禁忌表中；Step 3蟻群重復(fù)以下步驟，最后將所有客戶點(diǎn)遍歷一遍；Step 3.1通過(guò)轉(zhuǎn)移概率計(jì)算公式，螞蟻將選擇下一個(gè)客戶點(diǎn)。具體為螞蟻根據(jù)每條弧上的信息素濃度選擇下一個(gè)客戶點(diǎn)，假設(shè)螞蟻在時(shí)刻從客戶點(diǎn)i出發(fā)，選擇客戶點(diǎn)j的狀態(tài)轉(zhuǎn)移概率表達(dá)式為式（12）：

τij（t）表示客戶點(diǎn)i和客戶點(diǎn)j之間的信息量濃度，α表示信息素濃度，β為期望啟發(fā)因子，Ak表示車輛k可以被允許選擇的客戶點(diǎn)，ηij表示客戶點(diǎn)j對(duì)于客戶點(diǎn)i的啟發(fā)程度。Step 3.2如果客戶點(diǎn)i滿足約束條件，則螞蟻m轉(zhuǎn)移到客戶點(diǎn)；

Step 3.3將符合約束條件的客戶點(diǎn)加入到禁忌表中；

Step 4更新全局信息素。信息素濃度更新表達(dá)式為式（13）：

△τij（t，t+1）表示在（t，t+1）時(shí)間段內(nèi)，弧上（i，j）的信息素增加量，ρ表示信息素?fù)]發(fā)系數(shù)；

Step 5每次迭代Nc=Nc+1，如果Nc=Ncmax，則返回到Step2；否則就輸出最優(yōu)解并結(jié)束算法。

4.算例分析。

為了驗(yàn)證本文提出的模型有效性，現(xiàn)采用Solomon的VRP數(shù)據(jù)集中的算例C101對(duì)模型算法進(jìn)行檢驗(yàn)。選取數(shù)據(jù)集中1個(gè)配送中心和25個(gè)客戶點(diǎn)，蟻群算法參數(shù)設(shè)置為：m=100，Ncmax=100，α=1，β=3，ρ=0.8，車輛參數(shù)設(shè)定如下：r租賃成本=100，ξ空氣與燃料質(zhì)量比=1，κ標(biāo)準(zhǔn)柴油燃料的熱值(kg/g)=44，ψ從克g/s到升l/s的換算系數(shù)=737，k發(fā)動(dòng)機(jī)摩擦系數(shù)（kj/rev/l）=0.2，N發(fā)動(dòng)機(jī)轉(zhuǎn)速（rev/s）=33，V發(fā)動(dòng)機(jī)排量（l）=5，ρ空氣密度（kg/m3）=1.2，A迎風(fēng)表面積m2=3.19，μ車輛自身重量（kg）=6300，g引力常數(shù)=9.8，θ道路角度=0，Cd氣動(dòng)阻力系數(shù)=0.7，Cr滾動(dòng)阻力系數(shù)=0.01，ε車輛傳動(dòng)系效率=0.4，ω燃 油 機(jī) 效 率 參 數(shù)=0.45，γ碳 排 放 系 數(shù)=2.61（kg/l），s碳排放成本=20（kg/元），v車輛行駛速度=50（km/h）。在CPU為2.9GHz，內(nèi)存為8GB，使用MATLAB2020a計(jì)算機(jī)上編程計(jì)算得到以下優(yōu)化方案：當(dāng)不考慮碳排放，以運(yùn)輸成本最小為目標(biāo)函數(shù)時(shí)，車輛總使用數(shù)為4輛，車輛總行駛距離為182.3257，租賃成本為400，碳排放量為403.2565；優(yōu)化后，車輛總使用數(shù)為3輛車，車輛總行駛距離191.8136，最低碳排放量為400.3714，租賃成本為300，碳排放成本為8007.428，1號(hào)車輛配送路線為0→5→3→7→8→10→11→9→6→4→2→1→0，2號(hào)車輛配送路線為0→13→17→18→19→15→16→14→12→0，3號(hào)車輛配送路線為0→20→24→25→23→22→21→0。相比于優(yōu)化前，雖然車輛總行駛距離增加了，但碳排放量減少了0.71%。以上結(jié)果僅僅是對(duì)于25個(gè)客戶點(diǎn)來(lái)進(jìn)行計(jì)算求解，如果對(duì)于實(shí)際生活，減少的碳排量會(huì)更多。

5.結(jié)論

本文綜合考慮包含配送車輛租賃成本和碳排放成本，建立了考慮時(shí)間窗的低碳車輛配送路徑優(yōu)化數(shù)學(xué)模型，采用蟻群算法求解所提模型，并通過(guò)具體算例對(duì)本文的模型和算法進(jìn)行仿真，與不考慮碳排放的車輛配送路徑方案對(duì)比，可以得到優(yōu)化后的路徑方案，這對(duì)于我國(guó)物流企業(yè)實(shí)施低碳物流有很大的促進(jìn)作用。因此本文所建模型和求解算法對(duì)于帶時(shí)間窗的低碳車輛配送路徑規(guī)劃具有適用性和有效性，對(duì)低碳物流的發(fā)展提供了有效的支持。