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

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

引言

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

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

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

1.問題描述

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

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

2.問題求解

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

2.1 狀壓dp方法

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

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 蟻群算法

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

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 數據集

采用國際學術界公認的關于NP問題測試數據的網站[10]上關于TSP問題的權威數據。不失一般性地，使用該網站上文件名為“ali535.tsp.gz”的前一百個數據。

3.2 結果分析

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

表1 算法結果對比

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

4.總結及展望

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

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

本項目由大學生創新創業基金支持（項目號：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]楊濤． 低碳經濟下的多運輸方式物流網絡規劃[D]． 上海：上海交通大學． 2011．

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

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

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

[9]李亞男，劉聯輝等．低碳約束下城市冷鏈物流配送系統優化研究[J]．中國市場，2016，10（36）：36～37．

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