珠蘭，馬瀟，劉卓凡

（西安郵電大學，現代郵政學院，西安 710061）

0 引言

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

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

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

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

1 問題描述

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

1.1 旅行時間模型

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

圖1 旅行時間計算示意Fig.1 Calculation of travelling time

1.2 燃油消耗模型

本文采用綜合模式排放模型(CMEM)計算運輸車輛的燃油消耗量。經簡化，車輛以恒定速度v(m·s-1)和載重l(kg)運行距離d(m)時的總燃油消耗量F為

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

2 TD-GVRP模型構建

2.1 符號說明

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

表1 符號說明Table 1 Notations description

2.2 模型表達

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

3 基于RSM參數調整的嵌套遺傳算法

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

3.1 算法概述

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

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

圖3 內部GA算法流程Fig.3 Flowchart of interior GA

(1)外部GA算法

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

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

(2)內部GA算法

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

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

3.2 RSM概述

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

4 應用與分析

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

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

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

4.1 算法參數調試

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

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

本文選取的中心復合設計方案包含8 個分式因子試驗點、8個坐標軸試驗點和4個中心試驗點，共運行20 組試驗。試驗算例選取UK25 系列的10組算例，求得各組試驗方案的平均響應值。然后，由Design Expert 軟件在5%的置信水平下進行試驗，得到二階回歸擬合模型為

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

4.2 算法性能比較

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

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

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

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

4.3 不同目標的影響分析

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

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

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

表4 不同目標對各決策要素的求解結果Table 4 Decision factors under different objectives

4.4 擁堵時長影響分析

為研究擁堵時長對決策要素的影響，本文通過求解UK20 系列算例，進行總燃油消耗和總旅行時間對于擁堵時長參數的敏感度分析。以0.25 h 為步長，當擁堵分別持續(xù)0～2 h，10個算例的平均燃油消耗量和平均旅行時間的變化如圖7所示。

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

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

4.5 等待時間影響分析

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

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

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

5 結論

本文得到的主要結論如下：

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

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

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