帶貨物權(quán)重車輛路徑問題的研究現(xiàn)狀

蘇永梅

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

【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.

【關(guān)鍵詞】載重量;燃料消耗;貨物權(quán)重;車輛路徑優(yōu)化

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

【中圖分類號(hào)】F570.7? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號(hào)】1673-1069（2020）03-0168-02

1 引言

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

2 帶貨物權(quán)重的車輛路徑問題研究現(xiàn)狀

2.1 國(guó)外研究

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

F∶Mindy

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

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

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

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

2015年Zachariadis 和Tarantilis為了區(qū)分與普通VRP的區(qū)別提出了車載量依賴型車輛路徑問題并引入?yún)?shù)λ，其中λ=（Q/T），當(dāng)λ值非常小時(shí)，車載量依賴型車輛路徑問題近似于經(jīng)典VRP，運(yùn)輸成本決定于車輛自身重量和行駛距離，當(dāng)λ值較大時(shí)，運(yùn)輸成本取決于車輛的載重和行駛距離，此時(shí)VRP問題便為車載量依賴型車輛路徑問題。

2.2 國(guó)內(nèi)研究

國(guó)內(nèi)對(duì)于將載重量引入目標(biāo)函數(shù)考慮對(duì)運(yùn)輸成本的影響起步較晚。2008年唐加福等人對(duì)散車運(yùn)輸進(jìn)行了進(jìn)一步的改進(jìn)，考慮到車輛使用數(shù)量對(duì)于成本的影響，加上了車輛的租車費(fèi)用提出了更為標(biāo)準(zhǔn)的目標(biāo)函數(shù)：

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

2010年唐加福等人將車輛的發(fā)車費(fèi)用考慮在目標(biāo)函數(shù)中，進(jìn)一步得出如下的目標(biāo)函：

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

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

3 算法

3.1 精確算法

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

3.2 啟發(fā)式算法

精確算法可以解決小規(guī)模的問題，但隨著實(shí)際問題規(guī)模的增大，啟發(fā)式算法相比于精確算法在求解難度和時(shí)間上更有優(yōu)勢(shì)。近幾年，不斷有研究者將啟發(fā)式算法應(yīng)用到求解帶貨物權(quán)重的車輛路徑問題上。

4 研究中存在的問題

4.1 模型構(gòu)建存在的局限性

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

4.2 求解結(jié)果的實(shí)用性不強(qiáng)

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

5 結(jié)語(yǔ)

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

【參考文獻(xiàn)】

【1】靳方平.基于低碳經(jīng)濟(jì)視角的車輛路徑優(yōu)化理論與方法研究[D].長(zhǎng)沙：中南大學(xué)，2013.

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