基于低碳的快遞路徑選擇問題研究

文/蘆立華 邱煜浩 蔣濤 李恒洗

引言

近些年我國的空氣質(zhì)量日益惡化，據(jù)世界衛(wèi)生組織調(diào)查顯示，機動車尾氣污染是大氣環(huán)境污染的一種重要組成部分。其中，以化石燃料為能源的交通運輸業(yè)是碳排放的主要來源之一，由此導(dǎo)致低碳經(jīng)濟運行模式備受關(guān)注。本文以優(yōu)化快遞車輛配送路徑為出發(fā)點，旨在通過提高物流配送效率和減少物流配送成本，以降低機動車燃油消耗、減少碳排放，進(jìn)而實現(xiàn)綠色低碳環(huán)保交通運輸模式的理念，這對于實現(xiàn)可持續(xù)發(fā)展具有重要的理論價值和現(xiàn)實意義。

自1985年開始，國內(nèi)外就有研究者提出城市運輸存在空氣污染的問題。2013年，針對異構(gòu)車隊路線規(guī)劃問題進(jìn)行建模，Kwon等人[1]考慮碳排放。2014年，LinC和ChoyK[2]給出碳排放問題的VRP研究綜述。2014年，Konur基于碳排放約束條件下的庫存控制和異型車輛的配送路徑問題，并采用啟發(fā)式算法進(jìn)行優(yōu)化求解，可以明顯降低車輛運行中的碳排放量。2015年，Mohammad等[3]考慮了車輛在行駛過程中速度、距離以及道路是否堵塞等因素，建立燃料消耗模型，并用蟻群算法優(yōu)化求解。2016年，YoshinoriSuzuki[4]建立以能耗最低和碳排放量最少為目標(biāo)函數(shù)的車輛路徑模型?？紤]低碳經(jīng)濟的研究背景，楊濤[5]構(gòu)建了一個三級的物流網(wǎng)絡(luò)數(shù)學(xué)模型，用遺傳算法求解并進(jìn)行線路規(guī)劃。2013年，吳麗榮等[6]從低碳的角度考慮帶容量限制的VRP，建立了以最小化燃料消耗為優(yōu)化目標(biāo)的車輛路徑模型。2014年，饒衛(wèi)振等[7]考慮了道路坡度，提出了以配送車輛總能耗最小為目標(biāo)的低碳車輛路徑問題模型（ECM-LCVRP）。2015年，張如云等[8]在傳統(tǒng)帶時間窗VRP的基礎(chǔ)上，建立了考慮低碳、節(jié)能和成本節(jié)約的城市車輛配送問題模型，設(shè)計改進(jìn)的遺傳算法進(jìn)行求解。2016年，李亞男等[9]基于城市發(fā)展的理念，以碳排放為約束條件，構(gòu)建冷鏈物流配送網(wǎng)絡(luò)優(yōu)化模型，用遺傳算法得到模型的最優(yōu)解，實現(xiàn)冷鏈物流企業(yè)減少碳排放和降低配送成本的雙目標(biāo)。

本文以快速發(fā)展的快遞行業(yè)配送問題為出發(fā)點，研究了影響碳排放的主要因素——配送路徑，以期通過科學(xué)選擇和合理規(guī)劃車輛配送路徑來降低碳排放量。通過采用DP方法和蟻群算法解決該問題，分析了他們的性能。

1.問題描述

假設(shè)快遞公司有n個站點，快遞車輛需要經(jīng)過每一個指定站點再回到起點。如果起點固定，那么從起點出發(fā)經(jīng)過每一個站點再回到起點共有（n-1）種路徑，如何確定這些路徑中的最短路徑來最大限度地減少汽車的行駛距離是需要解決的關(guān)鍵問題。

假設(shè)有n個站點，兩個站點i和j間的距離為dij ，則目標(biāo)函數(shù)如（1）所示,約束條件如（2）-（4）。

2.問題求解

文中采用狀壓dp方法和蟻群算法對上述模型進(jìn)行求解，詳細(xì)方法如下所述。

2.1 狀壓dp方法

狀態(tài)壓縮動態(tài)規(guī)劃（狀壓dp）是一類典型的動態(tài)規(guī)劃方法，常使用在小規(guī)模NP問題求解中。雖然其復(fù)雜度為指數(shù)級，但是速度快。Dp算法將每一個站點的選取與否壓縮進(jìn)一個二進(jìn)制位里，0表示未訪問，1表示已訪問，S=2n用來表示所有的訪問情況，v表示現(xiàn)在所處的站點，以此創(chuàng)建一個二維數(shù)組dp[S][v]來表示目前在點v回到最初節(jié)點的距離，通過計算出dp數(shù)組的每一個值來得出經(jīng)過每個站點并回到起點的最小值，其偽碼如下所示。

function dpslove（site_number,site_distance）

dp[0..（1<

dp[1][0]= 0

for i=1 -> （1<

if （the first site not visited） then

continue

end if

for j=1 -> site_number do

join the next site which has not been joined

compute the min dp[（1<

//“|”represents the OR operation.“<<”describes the shift operation.

end for

end for

ans = min（ans,dp[（1<

return ans

end function

2.2 蟻群算法

蟻群算法是根據(jù)仿生學(xué)理論而得出的一種仿生算法，螞蟻走過的路線會留下與路徑長度有關(guān)的信息素，路徑越短釋放的信息素越多，隨著時間的積累，較短路徑上累計的信息素濃度逐步增加，選擇該路徑的螞蟻也會增加，最終可以得到優(yōu)化問題的最短路徑。偽碼描述如下所示。

function monodomous（site_number）

ants = sqrt（site_number）

for iterative time=0 -> iterative time max do

for i=0 -> ants do

randomly assignment ant i to a city

end for

for i=0 -> site_number do

for k=0 -> ants do

choose the next site for ant k

end for

end for

compute the length of route the increment of pheromone

hold the bestsolution

for each path do

update the pheromone value

end for

end for

reutrn bestsolution

end functiondp

3.實驗

3.1 數(shù)據(jù)集

采用國際學(xué)術(shù)界公認(rèn)的關(guān)于NP問題測試數(shù)據(jù)的網(wǎng)站[10]上關(guān)于TSP問題的權(quán)威數(shù)據(jù)。不失一般性地，使用該網(wǎng)站上文件名為“ali535.tsp.gz”的前一百個數(shù)據(jù)。

3.2 結(jié)果分析

實驗分別選取了n=15、20、50和100個城市作為快遞站點來仿真運行程序。針對每個算法各運行10次，統(tǒng)計最短距離、最長距離和平均距離，如表1所示。根據(jù)表1可以觀察，在n=15和n=20時，dp狀壓算法得出的最好、最差和平均距離都是相同的，均優(yōu)于蟻群算法。其中蟻群算法十次運行結(jié)果中最好的距離為597.601，要高于dp算法17.361。這主要歸因于dp算法是精確算法，而蟻群算法是啟發(fā)式算法，后者不能保證每次都能夠?qū)か@最優(yōu)解。當(dāng)站點數(shù)量增大到50和100時，對于該規(guī)模的數(shù)據(jù)集，由于dp狀壓算法本身的局限性，已不能很好地獲得結(jié)果。相反地，蟻群算法仍然適用，且誤差逐漸減少，在Matlab中生成的最短路徑圖如圖1所示?？傊?，在數(shù)據(jù)規(guī)模較小時，采用dp狀壓算法可以得到較好的結(jié)果，而當(dāng)問題規(guī)模逐漸增大時，蟻群算法的性能要遠(yuǎn)遠(yuǎn)優(yōu)于dp狀壓算法。

表1 算法結(jié)果對比

圖1 蟻群算法最短路徑生成圖

4.總結(jié)及展望

本項目對快遞車輛行駛的路徑進(jìn)行了研究，通過假定路徑的長度和碳排放有直接的關(guān)系，即，車輛行駛路徑越長碳排放量越多，反之越少。采用dp狀壓算法和蟻群算法分別計算快遞車輛經(jīng)過每一個目的地再回到起點的最短路徑，從而更合理地規(guī)劃車輛在站點間行駛的路徑，從而削減車輛能耗，降低企業(yè)運營成本，進(jìn)而減少空氣污染。

盡管本文已通過車輛路徑規(guī)劃達(dá)到降低碳排放的目的，但是由于受dp狀壓算法和蟻群算法本身的局限性，仍存在一些問題未得到很好地解決。如：在建立的優(yōu)化模型中，一方面沒有加入某時段某路段車輛具體行駛情況，沒有實現(xiàn)分時段的最短路徑規(guī)劃；另一方面未考慮道路擁堵、道路坡度等情況和碳排放量之間的關(guān)系，這都是在今后要重點研究的內(nèi)容。

本項目由大學(xué)生創(chuàng)新創(chuàng)業(yè)基金支持（項目號：A1-5701-17-009-02-64）

[1]Kwon Y，Choi Y，Lee D．Heterogeneous fixed fleet vehicle routing problem considering carbon emission[J]．Transportation Research Part D：Transport and Environment，2013，16（5）：81～89

[2]Lin C，Choy K L．Survey of Green Vehicle Routing Problem：Past and Future Trends[J]．Expert Systems with Applications，2014，41（4）：1118～1138．

[3]Mohammad Reza，Jabbarpour，RafidahMd Noor．Green vehicle traffic routing system using ant ～based algorism [J]．Journal of Network and Computer Applications，2015，12（58）：294～308．

[4]Yoshinori Suzuki．A dual～objective metaheuristic approach to solve practical pollution routing problem[J]．International Journal of Production Economics，2016，6（176）：143～153．

[5]楊濤． 低碳經(jīng)濟下的多運輸方式物流網(wǎng)絡(luò)規(guī)劃[D]． 上海：上海交通大學(xué)． 2011．

[6]吳麗榮，胡祥培，饒衛(wèi)振．考慮燃料消耗率的車輛路徑問題模型與求解[J]． 系統(tǒng)工程學(xué)報，2013，28（6）：804～811．

[7]饒衛(wèi)振，金淳，王新華．考慮道路坡度因素的低碳VRP問題模型與求解策略[J]．系統(tǒng)工程理論與實踐，2014，34（8）：2092～2105．

[8]張如云，劉清等． 考慮低碳的城市配送車輛路徑優(yōu)化模型研究[J]．工業(yè)工程與管理，2015，20（4）：29～34．

[9]李亞男，劉聯(lián)輝等．低碳約束下城市冷鏈物流配送系統(tǒng)優(yōu)化研究[J]．中國市場，2016，10（36）：36～37．

[10]http://comopt．ifi．uni-heidelberg．de/software/TSPLIB95/tsp/