帶貨物權重車輛路徑問題的研究現狀

蘇永梅

【摘? 要】在經典車輛路徑問題中運輸成本往往只與行駛距離有關，但在實際情況中由于載重量引起的燃料消耗也是導致企業運輸成本增加的重要因素。所以在解決車輛路徑問題模型中，目標函數同時考慮車輛載重量和行駛距離導致的成本變化對于企業優化車輛行駛線路具有更多實際意義。論文整理了有關載重量引起燃料消耗進而影響車輛行駛路線的相關國內外研究文獻，并總結近幾年解決此類問題的算法，最后提出問題存在的局限性和未來的研究方向。

【Abstract】In the classical vehicle routing problem， the transportation cost is usually only related to the travel distance， but in the actual situation， the fuel consumption caused by the load is also an important factor leading to the increase of the transportation cost of enterprises. Therefore， in the model of solving the vehicle routing problem， the objective function considers the cost changes caused by vehicle load and driving distance at the same time， which has more practical significance for enterprises to optimize the vehicle routing. This paper sorts out the relevant domestic and foreign research literature about the fuel consumption caused by load and the influence of vehicle driving route， summarizes the algorithms to solve such problems in recent years， and finally puts forward the limitations of the problem and the future research direction.

【關鍵詞】載重量;燃料消耗;貨物權重;車輛路徑優化

【Keywords】load; fuel consumption; cargo weight; vehicle routing optimization

【中圖分類號】F570.7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號】1673-1069（2020）03-0168-02

1 引言

近年來，電子商務發展快速，根據中國電子商務研究中心的數據統計顯示，截止到2016年我國在線電子商務網購規模己經超過7億人次，使用人數的逐漸增多對末端物流配送效率和效益提出了更高的挑戰。國家發改委發布的數據顯示，2016年度我國社會物流總費用為11.1萬億元，其中運輸成本占據6萬億元，如何優化運輸車輛的行駛路線對降低運輸成本具有重要意義。同時有研究表明，在物流配送和運輸環節所消耗的能源占到了整個物流環節90%的能耗[1]，隨著我國對能源消耗概念的提出，在考慮車輛行駛路線中考慮能耗問題更具有實際意義。車輛路徑問題在1959年由Dantzing和Ramser[2]提出后，基于實際情況的考慮便衍生出帶有不同約束條件的車輛路徑模型，在眾多的數學模型中都假設客戶之間的運輸費用與運輸距離有關，目標函數旨在優化車輛的最小行駛距離。然而，從車輛本身消耗的燃料來看，車輛載重量的變化對于燃料的消耗存在差異，同樣的運輸距離在經典車輛路徑問題中會產生同樣的運輸費用，但由于同樣的距離運載量的不同，對燃料的消耗也會有明顯的差異，運輸成本不僅僅與運輸距離有關更與運載量有關。

2 帶貨物權重的車輛路徑問題研究現狀

2.1 國外研究

2007年Kara and Yetis將車輛自身重量和車輛的載貨量作為車輛行駛過程中能源消耗的一部分，提出了最小燃料消耗的車輛路徑問題（EMVRP），基于行駛距離和重量建立了如下的目標函數，其中y表示車輛在顧客之間的總重量：

F∶Mindy

2008年Taveares、Zaigraiova在廢物收集和運輸中同時考慮了行駛距離、路面坡度和車載量對燃料消耗的影響，結果表明在運輸成本中考慮車載量會節約更多的燃料消耗，存在路線梯度因素時影響會更大。2012年xiao和zhao等對行駛車輛的總重量引起燃料消耗的目標函數進行改進，得出如下的線性關系式，其中ρ為車輛本身引起的燃料消耗：

ρ=ρ+y=ρ+ay? ? ? ? i，j=1，…，r

在提出車輛總重量對燃料消耗的影響之后，2012年Huang等由于車輛載重量引起的燃料消耗與CO2氣體排放結合求解了同時取送貨車輛路徑問題的最小目標值，并建立了CO2氣體排放與貨物重量之間的關系：

carbon emissions=μ×（a×10×load+b）

2015年Zachariadis 和Tarantilis為了區分與普通VRP的區別提出了車載量依賴型車輛路徑問題并引入參數λ，其中λ=（Q/T），當λ值非常小時，車載量依賴型車輛路徑問題近似于經典VRP，運輸成本決定于車輛自身重量和行駛距離，當λ值較大時，運輸成本取決于車輛的載重和行駛距離，此時VRP問題便為車載量依賴型車輛路徑問題。

2.2 國內研究

國內對于將載重量引入目標函數考慮對運輸成本的影響起步較晚。2008年唐加福等人對散車運輸進行了進一步的改進，考慮到車輛使用數量對于成本的影響，加上了車輛的租車費用提出了更為標準的目標函數：

Min C=（adZ+bdu）+（dZ）

2010年唐加福等人將車輛的發車費用考慮在目標函數中，進一步得出如下的目標函：

Min cos t=Dx（c+cy）+cx

在已存在的文獻中，考慮油耗影響的因素包括載重量、速度和路面坡度，Kuo假設在某一速度恒定下耗油量與載重量成正比，而從實際和文獻中可以看出當考慮載重量和速度時，耗油量和載重量并不成正比，Franceschetti在瞬時油耗的基礎上推導出在兩時間段下恒定速度下的油耗模型，但僅用CPLEX求解了較為小規模的問題。近幾年，帶貨物權重的問題被大家研究并結合在更多的實際問題中，如2009年朱才華等人將時間窗約束引入帶貨物權重的車輛路徑中，并利用遺傳算法進行求解。2010年吳思、丁以中將貨物權重和計重收費結合考慮，目標函數不僅包括固定費用還有由于運量引起的燃料消耗和路橋費用。2016年張琳琳提出了帶貨物權重的軟時間窗開放式車輛路徑問題研究，并用遺傳算法進行求解。

3 算法

3.1 精確算法

2015年Zachariadis和Tarantilis利用分支定價的方法求解了小規模的車載量依賴型車輛路徑問題。2016年Ricardo Fukasawa利用分支定價的方法求解了最小耗能的車輛路徑問題，提出了兩種新的混合整數規劃公式，基于循環消除的弧載重和附加約束的集劃分公式，結果明顯優于其他方法。

3.2 啟發式算法

精確算法可以解決小規模的問題，但隨著實際問題規模的增大，啟發式算法相比于精確算法在求解難度和時間上更有優勢。近幾年，不斷有研究者將啟發式算法應用到求解帶貨物權重的車輛路徑問題上。

4 研究中存在的問題

4.1 模型構建存在的局限性

帶貨物權重的車輛路徑問題的目標函數考慮運輸成本的最小化，包括行駛距離、載重量等，雖然考慮因素符合實際需要但缺乏合理性，燃料的消耗不僅與車載量有關，還與車型、行駛速度、出發時間相關，目標函數的考慮無疑會導致燃料消耗的重復計算。對于行駛速度已有的文獻都在考慮交通擁堵和不擁堵時間段下對燃料消耗的影響，但在實際情況中，城市各個時間段的行駛速度都會有所不同。在現有的文獻中很多都假設配送中心有相同車型的車輛，但在實際情況中，配送企業往往會有不同的車輛運輸貨物，并且這些車輛有不同的裝載能力和運行速度。如何在充分考慮各因素的情況下建立正確的燃料消耗與載重函數對優化車輛出行具有更多實際意義。

4.2 求解結果的實用性不強

在研究過程中，學者們大多利用啟發式算法對問題進行求解。雖然隨著研究的深入，有學者對其算法進行改進，采用兩階段法、混合算法等，但問題本身存在的復雜性和局限性導致算法結果的收斂性和有效性不強，在一定程度上影響了運用到實際情況下的合理性和實用性。此外，由于影響燃料消耗的因素眾多，但目前很少有學者對不同的影響因素進行敏感度分析，進而對不同的因素包括車型、速度、出發時間和路面坡度對考慮載重量下的燃料消耗進行比較，從而更有效地貼合實際問題。

5 結語

在能源消耗的大背景下，在車輛路徑問題中考慮能源消耗的最小化，一方面可以優化行車路線，降低企業的運輸成本，一方面也符合國家對能源消耗的政策。因此，對于帶貨物權重一類問題的研究具有更多實際意義，但目前對于燃料消耗問題更多的關注于載重量的影響，但實際情況并非如此，燃料的消耗還與車型、速度等有關，未來的研究應從實際出發考慮。同時現有的研究大多只能用啟發式算法進行大規模問題的求解，未來應該采用精確算法解決規模較大的問題。由于車輛路徑問題具有多種不同的約束條件，可以將更多的約束條件考慮在帶貨物權重的車輛路徑問題中，提出更多符合實際條件的問題模型，如多車型、多車程的帶貨物權重的車輛路徑問題。

【參考文獻】

【1】靳方平.基于低碳經濟視角的車輛路徑優化理論與方法研究[D].長沙：中南大學，2013.

【2】Dantzig G B， Ramser J H. The Truck Dispatching Problem[J].Management Science，1959，6（1）：80-91.