時(shí)間依賴型綠色車輛路徑問題研究

珠蘭，馬瀟，劉卓凡

（西安郵電大學(xué)，現(xiàn)代郵政學(xué)院，西安 710061）

0 引言

隨著環(huán)境污染與能源危機(jī)的加劇，以綠色可持續(xù)發(fā)展理念為導(dǎo)向的低排放、低能耗發(fā)展模式成為總體趨勢。目前，交通運(yùn)輸已成為全球最重要的溫室氣體排放源之一，交通擁堵也成為影響城市運(yùn)輸綠色化發(fā)展的重要因素。擁堵時(shí)段低速行駛的車輛不僅造成更高的溫室氣體排放，還導(dǎo)致了運(yùn)輸效率的降低和運(yùn)輸時(shí)間的不可預(yù)測。物流企業(yè)作為交通運(yùn)輸行業(yè)的重要主體，其運(yùn)作過程的合理性與社會的可持續(xù)發(fā)展息息相關(guān)。因此，不良交通狀況下運(yùn)輸過程的綠色化，是物流運(yùn)輸企業(yè)在路徑規(guī)劃階段需要考慮的重要因素。

運(yùn)輸企業(yè)的路徑規(guī)劃問題通常被抽象為車輛路徑問題(Vehicle Routing Problem，VRP)進(jìn)行研究。隨著運(yùn)輸導(dǎo)致的環(huán)境問題日益嚴(yán)重，考慮溫室氣體排放等環(huán)境要素的綠色車輛路徑問題(GVRP)成為研究熱點(diǎn)。車輛燃油消耗量、全球變暖潛能值(GWP)[1]、碳排放等價(jià)成本等，是常見的溫室氣體排放的度量指標(biāo)。由于車輛的燃油消耗量與溫室氣體排放量直接相關(guān)，燃油消耗量被認(rèn)為是運(yùn)輸過程綠色化的重要指標(biāo)。此外，由于車輛的燃油消耗量同時(shí)受車速、載重、發(fā)動機(jī)性能等多重因素影響，因此，學(xué)者通過一系列燃油消耗模型準(zhǔn)確估計(jì)運(yùn)輸車輛產(chǎn)生的環(huán)境影響。污染-路徑問題(Pollution Routing Problem，PRP)[2]由LAPORTE 團(tuán)隊(duì)提出，基于綜合模式排放模型計(jì)算車輛的燃油消耗，分析燃油消耗量與車輛路徑選擇間的關(guān)系，實(shí)現(xiàn)環(huán)境污染問題與經(jīng)典VRP 的深度融合，并提出一種改進(jìn)的大鄰域搜索算法求解該問題[3]。在此基礎(chǔ)上，他們又將PRP 拓展到最小化油耗和旅行時(shí)間的多目標(biāo)情形[4]。BRAVO M.等[5]研究了考慮同時(shí)取、送貨情形的多目標(biāo)PRP，并設(shè)計(jì)進(jìn)化算法進(jìn)行求解。QIU R.等[6]研究了基于碳定價(jià)倡議的雙層PRP 模型，分析了碳定價(jià)策略與企業(yè)車輛路徑?jīng)Q策間的關(guān)系，并設(shè)計(jì)粒子群算法解決該問題。上述基于燃油消耗的GVRP相關(guān)研究中，并沒有考慮交通狀況對車輛行駛速度、運(yùn)行時(shí)間、燃油消耗以及運(yùn)輸成本的一系列影響，實(shí)際中，外在交通狀況是隨著不同時(shí)間段而變化的。

出于這種研究需求，學(xué)者開始研究時(shí)間依賴型綠色車輛路徑問題(TDGVRP)。交通擁堵是時(shí)間依賴型路徑問題的一個(gè)體現(xiàn)，F(xiàn)RANCESCHETTI 等[7]在最小化油耗的車輛路徑問題中，考慮了擁堵時(shí)段的出發(fā)時(shí)間優(yōu)化問題和順暢時(shí)段的速度優(yōu)化，但模型中僅設(shè)定交通擁堵和交通順暢兩個(gè)連續(xù)時(shí)段的旅行時(shí)間分段函數(shù)。范厚明[8]研究了客戶需求模糊且有時(shí)間窗約束的TDGVRP，針對不同時(shí)間段道路的交通情況，采用Ichoua速度時(shí)間依賴函數(shù)表征車輛的行駛速度，依據(jù)可信性理論構(gòu)建模糊機(jī)會約束優(yōu)化模型處理客戶點(diǎn)模糊需求，并設(shè)計(jì)自適應(yīng)大規(guī)模鄰域搜索算法(ALNS)對其求解。GMIRA M. 等[9]研究1 條路段上存在多條路徑的情形下，不同交通狀況下的路徑選擇問題，定義了基于交通狀況的速度函數(shù)。上述研究考慮交通狀況影響下的綠色車輛路徑問題，多從速度優(yōu)化的角度開展研究，而通過優(yōu)化車輛各節(jié)點(diǎn)出發(fā)時(shí)間的研究還十分有限。

綜上，本文以城市配送系統(tǒng)為對象，研究時(shí)變交通狀況下考慮車輛油耗的車輛路徑問題。構(gòu)建一個(gè)時(shí)間依賴型綠色車輛路徑(TD-GVRP)模型，模型最小化包括燃油消耗、駕駛員勞動和車輛使用折損成本的總成本，定義了允許車輛在節(jié)點(diǎn)處等待的情形，通過優(yōu)化車輛在各節(jié)點(diǎn)處的出發(fā)時(shí)間，以規(guī)避擁堵時(shí)段并尋求最優(yōu)路徑方案，并設(shè)計(jì)基于RSM 參數(shù)調(diào)整的遺傳算法求解模型，通過PRPLIB數(shù)據(jù)庫中的算例驗(yàn)證本文所提模型和算法的優(yōu)勢。

1 問題描述

研究的問題描述如下：配送中心的車輛為城市中不同的客戶點(diǎn)進(jìn)行配送，高峰時(shí)段的交通擁堵影響車輛運(yùn)行速度，從而影響車輛的旅行時(shí)間和燃油消耗情況；此外，不同路徑的選擇也將對車輛的旅行時(shí)間和燃油消耗產(chǎn)生影響。本文旨在尋求時(shí)變交通狀況下使得車輛運(yùn)行總成本最低的路徑以及路徑上各節(jié)點(diǎn)處車輛的出發(fā)時(shí)間。建?；谌缦录僭O(shè)：(1)配送中心所有車輛為有固定容量限制的同質(zhì)車隊(duì)；(2)服務(wù)期間，車輛發(fā)動機(jī)關(guān)閉，無燃料消耗；(3)擁堵狀況以平均速度表示，車輛在途過程中不允許停留。

1.1 旅行時(shí)間模型

研究的TD-GVRP問題的時(shí)間依賴性主要表現(xiàn)在：不同交通狀況下車輛運(yùn)行速度不同，因而，在不同出發(fā)時(shí)間對應(yīng)的旅行時(shí)間也不同，即旅行時(shí)間是基于出發(fā)時(shí)間的連續(xù)分段函數(shù)。出發(fā)時(shí)間-旅行時(shí)間函數(shù)的獲得過程為：首先，根據(jù)路段上時(shí)變的車流速度繪制路段上的出發(fā)時(shí)間-速度函數(shù)圖；然后，根據(jù)路段長度、某一車流速度持續(xù)的時(shí)間等數(shù)據(jù)，計(jì)算各出發(fā)時(shí)間對應(yīng)的總旅行時(shí)間；最后，繪制出發(fā)時(shí)間-旅行時(shí)間函數(shù)圖。由于某一出發(fā)時(shí)間對應(yīng)的總旅行時(shí)間可能覆蓋多個(gè)運(yùn)行速度，因此，旅行時(shí)間函數(shù)的斜率變化點(diǎn)與速度變化點(diǎn)并不對應(yīng)。以旅行時(shí)間斜率的變化點(diǎn)作為各時(shí)間段的分界點(diǎn)，記M={m|m=1,2,…} 為時(shí)間段集合；為旅行時(shí)間函數(shù)斜率變化點(diǎn)；為節(jié)點(diǎn)(i,j)間第m個(gè)時(shí)間段；為時(shí)刻出發(fā)對應(yīng)的旅行時(shí)間。則在出發(fā)時(shí)間時(shí)間段內(nèi)的旅行時(shí)間曲線的斜率為，該時(shí)間段內(nèi)任何出發(fā)時(shí)間點(diǎn)對應(yīng)的旅行時(shí)間可通過旅行時(shí)間函數(shù)的斜率求出，如圖1所示。

圖1 旅行時(shí)間計(jì)算示意Fig.1 Calculation of travelling time

1.2 燃油消耗模型

本文采用綜合模式排放模型(CMEM)計(jì)算運(yùn)輸車輛的燃油消耗量。經(jīng)簡化，車輛以恒定速度v(m·s-1)和載重l(kg)運(yùn)行距離d(m)時(shí)的總?cè)加拖牧縁為

由式(2)可知，燃油消耗量取決于3 方面，即發(fā)動機(jī)性能、運(yùn)行速度和車輛載重。

2 TD-GVRP模型構(gòu)建

2.1 符號說明

本文模型中涉及的符號說明如表1所示。

表1 符號說明Table 1 Notations description

2.2 模型表達(dá)

式(3)為車輛總旅行成本最小，其中，前3 項(xiàng)分別為與車輛發(fā)動機(jī)、車輛行駛速度、車輛負(fù)載相關(guān)的燃油消耗成本；后2項(xiàng)分別為駕駛員勞動成本和車輛折損成本。式(4)為共有K輛車離開配送中心。式(5)和式(6)保證每個(gè)客戶節(jié)點(diǎn)只被訪問1次。式(7)定義了弧上的流量平衡。式(8)為車輛容量約束。式(9)規(guī)定了車輛的離開時(shí)間。式(10)和式(11)表示車輛在服務(wù)結(jié)束后可以在客戶點(diǎn)等待且無時(shí)間限制，當(dāng)允許等待但對等待時(shí)間有限制時(shí)，以式(17)代替式(10)和式(11)。式(12)用于計(jì)算車輛返回配送中心前的總旅行時(shí)間。式(13)為出發(fā)時(shí)間變量與弧遍歷變量之間的關(guān)系。式(14)～式(16)為變量的屬性約束。

3 基于RSM參數(shù)調(diào)整的嵌套遺傳算法

本文設(shè)計(jì)了遺傳算法(GA)求解模型。由于啟發(fā)式算法的性能對其參數(shù)設(shè)置十分敏感，利用基于響應(yīng)面法(Response Surface Methodology，RSM)的試驗(yàn)設(shè)計(jì)方法調(diào)試影響遺傳算法性能的關(guān)鍵參數(shù)。

3.1 算法概述

算法包含兩個(gè)優(yōu)化因子：車輛路徑和各節(jié)點(diǎn)處的出發(fā)時(shí)間，在外部GA 算法優(yōu)化車輛路徑的框架下，通過一個(gè)內(nèi)部GA算法優(yōu)化當(dāng)前路徑序列的出發(fā)時(shí)間。算法流程如圖2和圖3所示。

圖2 外部GA算法流程Fig.2 Flowchart of exterior GA

圖3 內(nèi)部GA算法流程Fig.3 Flowchart of interior GA

(1)外部GA算法

各節(jié)點(diǎn)按0,1,2,3,…,N順序編碼，其中，0為配送中心，N為客戶點(diǎn)的數(shù)量。隨機(jī)生成Ps個(gè)0～N的隨機(jī)序列構(gòu)建路徑初始種群。對于本文最小化問題，選取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，當(dāng)某條路徑上的總負(fù)載超過車輛容量，則為對應(yīng)的目標(biāo)函數(shù)乘以一個(gè)懲罰系數(shù)，降低適應(yīng)度函數(shù)。選擇操作中，基于輪盤賭策略選擇父代P（1），父代P（2）隨機(jī)選取。交叉操作基于多點(diǎn)交叉算子進(jìn)行，過程如下：在P（1）中隨機(jī)選擇3 個(gè)基因，將其復(fù)制到子代相同基因位上；去掉P（2）中與P（1）所選基因值相同的基因；將P（2）中剩余基因按順序依次填入子代O（1）中，如果遇到某一基因位上已經(jīng)存在基因值，則跳過該基因位繼續(xù)填入下一個(gè)位置。變異操作基于位值變異，以碼長為上限隨機(jī)確定兩個(gè)不同點(diǎn)，互換基因，通過預(yù)設(shè)最大迭代次數(shù)作為算法終止規(guī)則。以10個(gè)客戶節(jié)點(diǎn)的問題為例，外部GA算法交叉算子如圖4所示。

圖4 外部GA算法交叉算子示意Fig.4 Crossover operator of exterior GA

(2)內(nèi)部GA算法

當(dāng)前路徑序列的出發(fā)時(shí)間通過實(shí)數(shù)編碼實(shí)現(xiàn)。隨機(jī)生成PS（1）個(gè)染色體長度為N+K的初始種群，其中，K為車輛數(shù)；選取目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)；選擇操作中兩父代P（1）和P（2）均通過輪盤賭策略選出；采用基于算數(shù)交叉的算子進(jìn)行交叉操作，子代O（1）和O（2）每一個(gè)基因位上的值為

式中：實(shí)數(shù)θ∈[0 ,1] 為乘子；變異操作采用實(shí)數(shù)變異法，在父代上隨機(jī)選擇1個(gè)基因位，將定義域內(nèi)的1個(gè)隨機(jī)數(shù)賦值給該位置；算法停止通過當(dāng)前迭代最優(yōu)值與前1次最優(yōu)值的差值來控制，當(dāng)連續(xù)n次(本文為30 次)前后迭代最優(yōu)值的差值小于10-6，則停止運(yùn)算返回最優(yōu)值。

3.2 RSM概述

響應(yīng)面法(RSM)是通過近似構(gòu)造1個(gè)顯函數(shù)得到復(fù)雜系統(tǒng)輸入(變量)與輸出(響應(yīng))之間關(guān)系的方法，通過近似構(gòu)造1個(gè)顯函數(shù)構(gòu)造待測量的全局逼近。如果當(dāng)前輸入變量的水平接近響應(yīng)面的最優(yōu)位置，一階逼近模型即可準(zhǔn)確擬合響應(yīng)曲面，當(dāng)擬合區(qū)域存在彎曲，則必須用更高階的二階模型逼近。復(fù)合中心設(shè)計(jì)(CCD)是擬合二階模型非常有效的一類設(shè)計(jì)。本文選取外部GA算法的4個(gè)關(guān)鍵參數(shù)：種群規(guī)模Ps、進(jìn)化代數(shù)n、交叉率Pc以及變異率Pm作為優(yōu)化因子，以本文算法的目標(biāo)函數(shù)作為響應(yīng)量，分析不同參數(shù)組合下的響應(yīng)情況，得到響應(yīng)與輸入變量之間的擬合關(guān)系，確定本文算法在求解模型時(shí)的最佳參數(shù)取值。

4 應(yīng)用與分析

本文提出的模型和算法應(yīng)用于一組城市配送系統(tǒng)算例，算例來源于DEMIR 等[3]提出的污染-路徑問題實(shí)驗(yàn)數(shù)據(jù)庫PRPLIB，該數(shù)據(jù)庫包含：10，15，20，25，50，75，100，200 個(gè)客戶節(jié)點(diǎn)的8 組算例，每組又包含20個(gè)不同算例，例如，算例UK25_01表示節(jié)點(diǎn)規(guī)模為25 的算例組中的第1 組算例。本算例考慮2輛車在擁堵-非擁堵兩階段下進(jìn)行配送活動的情形。研究時(shí)間段設(shè)為b=5 h；高峰擁堵持續(xù)時(shí)間a=2 h；車輛在擁堵時(shí)段的速度vc=20 km·h-1；其余時(shí)段的速度vf=40 km·h-1。車輛相關(guān)參數(shù)取自江淮HFC1082KD 廂式載貨車。算例通過CPLEX 12.5 求解器和基于MATLAB 的GA 算法求解。其中，CPLEX求解器的求解時(shí)間上限設(shè)為3 h。所有試驗(yàn)均在一臺Core i5處理器，內(nèi)存2.2 GHZ個(gè)人電腦上完成。出發(fā)時(shí)間-速度關(guān)系如圖5所示。對應(yīng)的旅行時(shí)間函數(shù)如圖6所示。

圖5 出發(fā)時(shí)間-速度關(guān)系Fig.5 Relationship between departure time and speed

圖6 出發(fā)時(shí)間-旅行時(shí)間關(guān)系Fig.6 Relationship between departure time and traveling time

4.1 算法參數(shù)調(diào)試

在本文RSM試驗(yàn)中，因子Ps、n、Pc、Pm分別以編碼符號x1,x2,x3,x4表示，取值范圍以及水平劃分如表2所示。

表2 輸入變量的范圍與水平劃分Table 2 Range and levels of input variables

本文選取的中心復(fù)合設(shè)計(jì)方案包含8 個(gè)分式因子試驗(yàn)點(diǎn)、8個(gè)坐標(biāo)軸試驗(yàn)點(diǎn)和4個(gè)中心試驗(yàn)點(diǎn)，共運(yùn)行20 組試驗(yàn)。試驗(yàn)算例選取UK25 系列的10組算例，求得各組試驗(yàn)方案的平均響應(yīng)值。然后，由Design Expert 軟件在5%的置信水平下進(jìn)行試驗(yàn)，得到二階回歸擬合模型為

通過Lingo 軟件求解二階多元回歸模型，最小化響應(yīng)值Y，得到本文GA 算法的最優(yōu)參數(shù)組合為：Ps=50、n=800、Pc=0.7、Pm=0.1。

4.2 算法性能比較

為檢驗(yàn)本文GA 算法的求解性能，本文分別通過CPLEX 求解器和GA 算法求解算例UK10～200，分別得出目標(biāo)函數(shù)值Z1、求解時(shí)間St、不可行解所占比例pf以及解的改善百分比pm，結(jié)果以每組10個(gè)算例的平均結(jié)果給出。其中，求解質(zhì)量的改善百分比由(CPLEX 解-GA 解)/CPLEX 解求得，用以表示GA 相對CPLEX 的求解精度。CPLEX 與GA 求解結(jié)果比較如表3所示。

表3 CPLEX與GA求解結(jié)果比較Table 3 Results comparison of CPLEX and GA

由表3可知，CPLEX 在包含10 個(gè)節(jié)點(diǎn)的算例中可以求得全局最優(yōu)；而當(dāng)節(jié)點(diǎn)規(guī)模上升至50時(shí)，10個(gè)算例中的1個(gè)不能求得可行解；當(dāng)節(jié)點(diǎn)規(guī)模上升至100時(shí)，所有算例無法在時(shí)間限制內(nèi)取得最優(yōu)解，且10個(gè)算例中的3個(gè)沒有在3 h內(nèi)找到可行解；當(dāng)節(jié)點(diǎn)規(guī)模上升至200 時(shí)，在時(shí)間限制內(nèi)，CPLEX求得的不可行解的比例達(dá)到60%。對不同規(guī)模算例，GA均能在短時(shí)間求出高質(zhì)量可行解，且隨著算例規(guī)模的增大，其相對于CPLEX 的求解質(zhì)量改善程度也在明顯增加，尤其是當(dāng)CPLEX 無法在時(shí)間限制內(nèi)求得最優(yōu)解時(shí)，在200個(gè)客戶節(jié)點(diǎn)的大規(guī)模算例中，改善比例高達(dá)28.57%。

此外，在求解速度方面，GA 明顯優(yōu)于CPLEX。對于10 個(gè)節(jié)點(diǎn)的小規(guī)模算例，兩者求解時(shí)間相近，隨后，求解時(shí)間的差距隨著算例規(guī)模的增加而顯著增加；對于50個(gè)節(jié)點(diǎn)的中等規(guī)模算例，GA 平均僅需27.49 s，而CPLEX 則需要861 s；對于100個(gè)節(jié)點(diǎn)的大規(guī)模算例，GA平均僅需111.5 s。由此說明，本文提出的基于RSM參數(shù)調(diào)整的GA算法可以有效求解本文提出的TD-GVRP模型。

4.3 不同目標(biāo)的影響分析

本文以GA 求解UK10_01、UK15_01 和UK20_013 個(gè)算例的結(jié)果，說明不同目標(biāo)對決策方案的影響。除總成本目標(biāo)外，設(shè)置3個(gè)決策者較為關(guān)心的目標(biāo)，分別是燃油消耗最小化Z2，傳統(tǒng)VRP目標(biāo)總旅行時(shí)間最小化Z3和總旅行距離最小化Z4，即

不同目標(biāo)下，各決策要素的值包括：總成本Tc，總CO2排放Te、總旅行行時(shí)間Tt和總旅行距離Td，如表4所示。表中所有值均以最小化燃油消耗目標(biāo)Z2求得的值為基準(zhǔn)進(jìn)行標(biāo)準(zhǔn)化。

本文設(shè)置的4個(gè)目標(biāo)函數(shù)中，與燃油消耗有關(guān)的目標(biāo)函數(shù)為Z1和Z2。由表4可知，以本文TDGVRP模型目標(biāo)函數(shù)Z1求得的燃油消耗僅比Z2結(jié)果高出4.9%，傳統(tǒng)VRP目標(biāo)Z3和Z4求得的平均燃油消耗則分別比Z2結(jié)果高出了65.78%和13.64%。由此可知，目標(biāo)函數(shù)中燃油消耗因素的引入，可以大大降低決策方案對應(yīng)的燃油消耗。此外，Z3結(jié)果顯示，較短的旅行時(shí)間將以較高的成本和CO2排放為代價(jià)。

表4 不同目標(biāo)對各決策要素的求解結(jié)果Table 4 Decision factors under different objectives

4.4 擁堵時(shí)長影響分析

為研究擁堵時(shí)長對決策要素的影響，本文通過求解UK20 系列算例，進(jìn)行總?cè)加拖暮涂偮眯袝r(shí)間對于擁堵時(shí)長參數(shù)的敏感度分析。以0.25 h 為步長，當(dāng)擁堵分別持續(xù)0～2 h，10個(gè)算例的平均燃油消耗量和平均旅行時(shí)間的變化如圖7所示。

圖7 擁堵時(shí)長參數(shù)的敏感度分析Fig.7 Sensitivity analysis of congestion parameter

由圖7可知，當(dāng)不允許車輛在客戶處停留等待時(shí)，擁堵持續(xù)的時(shí)間越長，將導(dǎo)致越高的燃油消耗量和越長的旅行時(shí)間。這是由于較長的擁堵時(shí)間導(dǎo)致車輛總行駛周期內(nèi)低速行駛比例增大。

4.5 等待時(shí)間影響分析

為研究等待時(shí)間Wt對決策要素的影響，即不同的出發(fā)時(shí)間對成本Tc、燃油消耗Te和旅行時(shí)間Tt的影響，對比并分析不同等待時(shí)間約束下的結(jié)果如表5所示。結(jié)果由UK20 系列中10 組算例的平均值給出。

表5 不同等待時(shí)間對各決策要素的求解結(jié)果Table 5 Decision factors under different waiting times

表5結(jié)果顯示，與不允許等待的情形相比，等待時(shí)間無限制的情形可節(jié)省5.2%的燃油消耗，總成本下降0.55%。由于總旅行時(shí)間中引入等待時(shí)間，總旅行時(shí)間增長了28.35%。由此可見，如果允許在客戶處等待，選擇合適時(shí)間出發(fā)以規(guī)避擁堵，可以在一定程度上降低燃油消耗和總成本。然而，在總成本降低并不明顯的情況下增加總運(yùn)營時(shí)間，從運(yùn)營角度分析可能并不是較好的方案，但卻能達(dá)到較客觀的節(jié)能環(huán)保效果。

5 結(jié)論

本文得到的主要結(jié)論如下：

(1)通過不同目標(biāo)的影響分析可知，與傳統(tǒng)VRP 問題相比，目標(biāo)函數(shù)中引入燃油消耗要素，可以有效降低決策方案的燃油消耗量。

(2)對擁堵時(shí)長參數(shù)的敏感度分析結(jié)果顯示，較長時(shí)間的擁堵將導(dǎo)致更長的旅行時(shí)間和更多的燃油消耗。

(3)通過等待時(shí)間影響分析可知，當(dāng)允許車輛在客戶處等待并選擇合適時(shí)間出發(fā)，最多可節(jié)省5.2%的燃油消耗和0.55%的總成本。