林 鑫， 邵乾虔， 楊珍花， 徐 奇， 靳志宏

(1.浙江大學(xué) 管理學(xué)院，浙江 杭州 市0058； 1.大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026； 3.沈陽建筑大學(xué) 交通工程學(xué)院，遼寧 沈陽 110168)

0 引言

城市配送是現(xiàn)代物流業(yè)發(fā)展關(guān)注的熱點(diǎn)問題。作為供應(yīng)鏈末端環(huán)節(jié)之一，其效率對保障各行業(yè)物資儲備，提高居民生活質(zhì)量具有重要意義。作為物流系統(tǒng)優(yōu)化的經(jīng)典問題，車輛調(diào)度問題(Vehicle Routing Problem, VRP)的研究者不斷結(jié)合生產(chǎn)實(shí)際，充分考慮了不同配送類型間的作業(yè)特點(diǎn)、服務(wù)效率和社會價(jià)值。

Lee等[1]研究了以多輛相同類型車輛對多個(gè)供應(yīng)商和多個(gè)需求客戶同時(shí)取送的VRP問題，設(shè)計(jì)了基于動態(tài)規(guī)劃的精確解算法求解；于濱等[2]探討了具有多個(gè)配送中心的帶時(shí)間窗VRP問題并提出了適應(yīng)該類問題的兩階段啟發(fā)式算法；蔡婉君等[3]針對多周期的循環(huán)配送問題，以基于多維信息素搜索和局部掃描思想的改進(jìn)蟻群算法進(jìn)行優(yōu)化；Gromicho等[4]提出了具有駕駛時(shí)長限制等現(xiàn)實(shí)約束的大規(guī)模VRP問題的求解框架。Bektas和Laporte[5]從碳排放測度的角度，提出了以燃油消耗量最小為目標(biāo)函數(shù)的VRP節(jié)能問題。上述VRP問題的擴(kuò)展研究工作更關(guān)注于車輛任務(wù)分配和排序，對行駛路徑也僅以客戶間的直線距離或恒定通行時(shí)間簡化描述。

近年來，隨著城市化進(jìn)程的推進(jìn)和機(jī)動車數(shù)量的增加，路網(wǎng)規(guī)模不斷擴(kuò)大，結(jié)構(gòu)日趨復(fù)雜。車輛因路網(wǎng)環(huán)境影響而提早或延遲執(zhí)行配送任務(wù)甚至取消任務(wù)的概率大大增加，配送中心亟待尋找更加可靠的調(diào)度計(jì)劃制定方法。

目前，結(jié)合實(shí)際路網(wǎng)因素的VRP研究并不多見，部分學(xué)者僅從路網(wǎng)交通狀況變化情境出發(fā)，對路網(wǎng)分層刻畫、路段擁堵規(guī)避和調(diào)度計(jì)劃調(diào)整等環(huán)節(jié)進(jìn)行嘗試性探索。 Fleischmann等[6]認(rèn)為客戶間通行時(shí)間以歐式距離或恒定車輛速度遞推為脫離現(xiàn)實(shí)的假設(shè)條件，VRP問題應(yīng)考慮實(shí)際路網(wǎng)路段的潛在通行價(jià)值。Yiu等[7]依據(jù)路段車輛密度變化對路網(wǎng)進(jìn)行分區(qū)分層，設(shè)計(jì)規(guī)避擁堵區(qū)域的路徑選擇算法。Okude和Taniguchi[8]按照道路使用頻率將復(fù)雜路網(wǎng)分層后，采用禁忌搜索算法求解經(jīng)典VRP問題。Figliozzi[9]將城市路網(wǎng)各路段按通行速度劃分為若干等級，通過設(shè)置不同級別路段的優(yōu)先通行規(guī)則優(yōu)化構(gòu)筑算法，求解最短路徑。王征等[10]考慮了路段行駛時(shí)間的延遲，從干擾管理的視角出發(fā)，設(shè)計(jì)包含“救援路線列舉→救援路線選擇”兩階段思維方式的求解算法調(diào)整車輛調(diào)度計(jì)劃。李妍峰等[11]考慮路網(wǎng)的常發(fā)性擁堵和偶發(fā)性擁堵，提出了一類將初始路徑安排與實(shí)時(shí)路線調(diào)整相結(jié)合的動態(tài)求解策略。Kok等[12]借鑒Dijkstra算法設(shè)計(jì)啟發(fā)式動態(tài)規(guī)則，通過尋找替代路徑規(guī)避擁堵路段、改變客戶訪問順序和車輛任務(wù)分配調(diào)整調(diào)度計(jì)劃，降低了車輛作業(yè)時(shí)間。Güner等[13]通過對路網(wǎng)歷史數(shù)據(jù)分析，以馬爾科夫鏈預(yù)測車輛行駛當(dāng)前路段的擁堵狀態(tài)，并運(yùn)用動態(tài)規(guī)劃方法規(guī)避后續(xù)路徑中的擁堵路段，求解帶時(shí)間窗約束的車輛調(diào)度問題。楊忠振等[14]引入交通流分配理論，建立車輛作業(yè)時(shí)間和路段車流量相互影響的雙層規(guī)劃模型，設(shè)計(jì)混合遺傳算法求解。上述研究工作多以路段車流量及其相關(guān)因素作為變量初步刻畫了實(shí)際路網(wǎng)，在近一步結(jié)合路網(wǎng)物理特點(diǎn)描述交通狀況方面，存在一定的改進(jìn)空間。

本文在考慮了路段車道數(shù)、車道寬度等路網(wǎng)物理特點(diǎn)和路段擁堵、路口等待、限行繞行等實(shí)際影響因素的基礎(chǔ)上構(gòu)建了數(shù)學(xué)規(guī)劃模型，設(shè)計(jì)了兩階段算法進(jìn)行求解，即首先運(yùn)用改進(jìn)A-Star精確解法(Improving A-star Search, IAS)生成客戶時(shí)間距離矩陣，再由基于“最小服務(wù)時(shí)間優(yōu)先”初始解生成方式和“三點(diǎn)隨機(jī)排序，兩點(diǎn)互換插入”鄰域搜索規(guī)則的混合模擬退火算法(Hybrid SA, HSA)求解調(diào)度方案。比較IAS算法和Dijkstra算法的求解效率后，以配送中心實(shí)際運(yùn)營數(shù)據(jù)驗(yàn)證HSA算法求解結(jié)果的有效性。通過配送中心服務(wù)范圍內(nèi)路段的車流量時(shí)空變化情況進(jìn)行仿真分析，探尋配送成本變化規(guī)律。

1 問題描述

車輛在實(shí)際路網(wǎng)中的行駛往往面臨諸多因素的綜合影響。路網(wǎng)車流量、道路容量、路口車輛飽和程度、交通信號燈以及道路行駛規(guī)則均能導(dǎo)致車輛實(shí)際運(yùn)行情況與配送效率與調(diào)度計(jì)劃存在較大偏差。因此，在制定準(zhǔn)時(shí)、高效、低成本調(diào)度計(jì)劃的同時(shí)如何結(jié)合路網(wǎng)因素優(yōu)化配送方案，降低計(jì)劃與實(shí)際存在的作業(yè)偏差，是提升城市配送服務(wù)水平的瓶頸之一。

圖1具體描述了本文考慮的實(shí)際路網(wǎng)各類因素。假設(shè)某車僅服務(wù)客戶1，在從配送中心出發(fā)后，由于AB路段維修禁行，車輛選擇從車道數(shù)多且車道較寬、車速較快的主干道CD繞行，C、D路口屬車流量較大的擁堵路口，車輛等待一定時(shí)間后進(jìn)入不可逆行的單行道BE行駛，再經(jīng)輔助道EF到達(dá)目的地。返程途中，車輛經(jīng)過單行道FG后回到配送中心。在此過程中，根據(jù)車輛在客戶處的到達(dá)時(shí)間是否滿足客戶預(yù)約時(shí)段計(jì)算配送服務(wù)違約費(fèi)用，協(xié)調(diào)相關(guān)運(yùn)營成本，制定調(diào)度計(jì)劃。

圖1 路網(wǎng)因素影響下的車輛路徑選擇

相比于傳統(tǒng)VRP問題，路網(wǎng)信息的數(shù)學(xué)表達(dá)及時(shí)間距離矩陣的結(jié)合轉(zhuǎn)換是研究的關(guān)鍵。本文用兩層連通圖N(W,F)和G(V,E)對實(shí)際路網(wǎng)進(jìn)行描述。第一層為路網(wǎng)信息圖N，W為路網(wǎng)中各路口點(diǎn)集，F(xiàn)為包含各類路況的弧集；第二層為客戶分布圖G，V為由配送中心和需要服務(wù)的客戶構(gòu)成的點(diǎn)集，E為連接中各點(diǎn)的弧集。配送中心具有載重量不同的多種車型。車輛出發(fā)后需盡可能滿足客戶服務(wù)的時(shí)間窗并在完成任務(wù)后返回配送中心。

2 數(shù)學(xué)建模

基于兩層連通圖，先構(gòu)造基于實(shí)際路網(wǎng)的客戶時(shí)間距離矩陣，再以該矩陣為基礎(chǔ)，建立車輛調(diào)度模型。由于城市配送具有短程高頻特點(diǎn)，相鄰客戶通行時(shí)段內(nèi)路網(wǎng)時(shí)空特征變化不大，因此以車輛出發(fā)時(shí)刻更新路網(wǎng)信息，降低計(jì)算規(guī)模。

2.1 客戶時(shí)間距離矩陣

在路網(wǎng)信息圖N中，尋找兩兩匹配的客戶間具有最短通行時(shí)間的路徑，構(gòu)建客戶時(shí)間距離矩陣。區(qū)別于傳統(tǒng)網(wǎng)絡(luò)，實(shí)際路網(wǎng)情境中的各類因素均能對路徑選擇產(chǎn)生影響，因此分類歸納其物理特點(diǎn)，引入交通阻抗測度方法描述相應(yīng)特征。

假設(shè)時(shí)間距離矩陣求解時(shí)，路網(wǎng)路段車道數(shù)、車道寬度和單向限行規(guī)則等物理特點(diǎn)短期內(nèi)不發(fā)生改變；路口平均車流量可通過所有鄰接路段的車流量進(jìn)行估計(jì)。

描述路網(wǎng)因素的符號如下。

i,j：客戶編號，配送中心為0，i=0,1,…，|V|-1，i=0,1,…，|V|-1；

m,n：路口編號m=1,2，…，|W|,n=1,2，…，|W|；

LNmn：路段m至n方向的車道數(shù)量，m=1,2，…，|W|,n=1,2，…，|W|；LWmn：路段mn的車道寬度，m=1,2，…，|W|,n=1,2，…，|W|；

λm：路口m的綠信比，m=1,2，…，|W|；

χm：路口m車流量飽和率，m=1,2，…，|W|；

Emn：路段mn上的平均車流量，m=1,2，…，|W|，n=1,2，…，|W|；

emn：路段mn上的交通容量，m=1,2，…，|W|，n=1,2，…，|W|；

dmn：路段mn的長度，m=1,2，…，|W|，n=1,2，…，|W|；

按步驟推導(dǎo)圖N中相鄰路口組成路段的綜合阻抗，作為路網(wǎng)信息圖的弧流量：

Step1分析實(shí)際路網(wǎng)的物理特點(diǎn)并進(jìn)行數(shù)學(xué)表達(dá)

根據(jù)實(shí)際行車經(jīng)驗(yàn)，車道寬度一定時(shí)，路段單向車道數(shù)越多，其自由流速度越大；路段單向車道數(shù)一定時(shí)，車道寬度越大，其自由流速度也越大。通過國內(nèi)城市路網(wǎng)浮動車數(shù)據(jù)收集分析[15]，設(shè)置單向三車道且每車道寬3m的城市道路為標(biāo)準(zhǔn)道路，以限速的85%位速推導(dǎo)自由流速度[16]。各路段自由流速度vmn的計(jì)算公式如下：

2.27(LWmn-3)

(1)

Step2測度路口等待時(shí)間

引入Webster函數(shù)，測度與路口流量飽和率、信號燈周期、綠信比和平均交通流量有關(guān)的路口等待時(shí)間tm：

(2)

Step3測度路段通行時(shí)間

引入BRP函數(shù)，測度與自由流速度、路段容量和平均交通流量相關(guān)的路段通行時(shí)間tmn：

(3)

Step4計(jì)算路段綜合阻抗

結(jié)合Step 2和Step 3中的測度值，推導(dǎo)得路口至路口的綜合交通阻抗為Dmn為gmn(tmn+tm)，作為路網(wǎng)信息圖的弧流量。此外，客戶至路口、路口至客戶的綜合交通阻抗Din和Dmj分別為gin(tin+tn)和gmjtmj。

(4)

由此，客戶時(shí)間距離矩陣RT可通過尋找客戶i至客戶j間具有最短通行時(shí)間的路徑構(gòu)造，數(shù)學(xué)表達(dá)如下。

2.2 車輛調(diào)度模型

調(diào)度計(jì)劃的制定需要結(jié)合配送中心各車輛載重量限制，將客戶服務(wù)任務(wù)分配給各車輛，合理安排每輛車的客戶服務(wù)順序，并盡可能滿足客戶預(yù)約時(shí)間窗。結(jié)合上述要求，以調(diào)度計(jì)劃綜合成本最小為目標(biāo)，建立車輛調(diào)度模型。

模型的假設(shè)條件如下。

(1)每個(gè)客戶點(diǎn)僅由一輛車服務(wù)一次；

(2)車輛均從配送中心出發(fā)，完成計(jì)劃任務(wù)后返回配送中心；

(3)卸貨作業(yè)準(zhǔn)備時(shí)間不計(jì)，即車輛到達(dá)客戶后立即開始作業(yè)。

模型中的符號如下。

L：配送中心當(dāng)前擁有的車輛數(shù)量；

Ql：車輛l的核定載重量，l=1,2,…,L；

vd：卸貨速率；

α：車輛行駛過程中的單位時(shí)間價(jià)值系數(shù)；

cl：車輛啟用的固定成本，l=1,2,…,L；

cE：提前服務(wù)單位時(shí)間費(fèi)用；

cL：延遲服務(wù)單位時(shí)間費(fèi)用；

Ci：車輛l的違約費(fèi)用，l=1,2,…,L；

qi：客戶i的貨物需求量，i=1,2,…,|V|-1；

SC：客戶集合的任一子集合，SC?{0}V；

ET0：車輛從配送中心出發(fā)時(shí)刻；

(ET1,LT1)：客戶預(yù)約服務(wù)時(shí)間窗，i=1,2,…,|V|=-1；

決策變量有：

根據(jù)決策變量，可推導(dǎo)得如下變量：

為評價(jià)配送計(jì)劃在作業(yè)時(shí)間、不同車型車輛利用率和客戶服務(wù)準(zhǔn)時(shí)性三方面的合理性，引入廣義費(fèi)用概念，以單位時(shí)間價(jià)值系數(shù)α將行程總時(shí)間轉(zhuǎn)化為運(yùn)營成本；以提前懲罰費(fèi)用c2和延遲懲罰費(fèi)用c3計(jì)算單位時(shí)間違約費(fèi)用，一般情況下c2

(5)

目標(biāo)函數(shù)與約束條件為

(6)

(7)

(8)

(9)

(10)

(11)

(12)

目標(biāo)函數(shù)(6)優(yōu)化包含配送總時(shí)間、不同車型的車輛啟用固定成本和不準(zhǔn)時(shí)違約費(fèi)用的配送計(jì)劃廣義費(fèi)用；約束(7)保證配送路徑需求量總和小于車輛核定載重量；約束(8)表示每個(gè)客戶都能被一輛車服務(wù)；約束(9)表示每個(gè)客戶僅能被服務(wù)一次；約束(10)為車輛到訪客戶的流量平衡，即到達(dá)某客戶的配送車輛一定會從該客戶駛離；約束(11)表示出發(fā)車輛數(shù)和返回車輛數(shù)守恒，即車輛從配送中心出發(fā)，完成任務(wù)后必須返回配送中心；約束(12)規(guī)避了路徑中的子回路。

3 兩階段求解策略

根據(jù)實(shí)際路網(wǎng)車輛調(diào)度特點(diǎn)，本文設(shè)計(jì)改進(jìn)A-star算法(Improving A-star search，IAS)和混合模擬退火算法(Hybrid SA，HSA)分階段求解優(yōu)化模型。IAS算法以通行時(shí)間和路口延時(shí)相結(jié)合的啟發(fā)式函數(shù)替代傳統(tǒng)A-star評價(jià)函數(shù)進(jìn)行路口估價(jià)，使其能在實(shí)際路網(wǎng)條件下求得精確解并減少路口搜索次數(shù)。HSA算法中“最小服務(wù)時(shí)間優(yōu)先”初始解構(gòu)筑規(guī)則指按照各客戶服務(wù)時(shí)間窗下限與配送中心開始作業(yè)時(shí)間差升序排列待服務(wù)客戶，并順序插入各配送車輛任務(wù)序列中，保證初始可行解的快速搜索；“三點(diǎn)隨機(jī)排序，兩點(diǎn)互換插入”鄰域搜索規(guī)則既能有效避免不可行解的產(chǎn)生，也能在留有足夠的搜索空間下快速找到各鄰域優(yōu)化解。算法整體思路見圖2。

圖2 算法整體思路

3.1 改進(jìn)A-star算法

區(qū)別于傳統(tǒng)最短路徑問題，客戶時(shí)間距離矩陣的求解需要協(xié)調(diào)路段通行時(shí)間和路口等待時(shí)間，標(biāo)號擴(kuò)展的Dijkstra算法[17](Dijkstra Signature Improving, DSI)在規(guī)模不大的區(qū)域路網(wǎng)中能對其進(jìn)行有效求解。DSI算法采取“先路段后路口”的評價(jià)策略，首先以路段通行時(shí)間替代Dijkstra算法中的弧的權(quán)值，在無法找到起點(diǎn)至當(dāng)前節(jié)點(diǎn)更短的路徑時(shí)，以鄰接節(jié)點(diǎn)至當(dāng)前節(jié)點(diǎn)推得的最小權(quán)和當(dāng)前節(jié)點(diǎn)所示路口的等待時(shí)間之和作為節(jié)點(diǎn)標(biāo)號，直到搜索至路徑終點(diǎn)。作為一類廣度優(yōu)先搜索算法，DSI算法將遍歷路網(wǎng)中的所有路口，時(shí)間復(fù)雜性較高，難以適用于路口數(shù)量多、密度大的城市路網(wǎng)最短路徑搜索。

為降低節(jié)點(diǎn)搜索規(guī)模，提高求解效率，路網(wǎng)最短路徑問題可通過基于啟發(fā)式規(guī)則的A-star算法[18]求解。它能夠通過估價(jià)函數(shù)的計(jì)算對未擴(kuò)展的節(jié)點(diǎn)進(jìn)行前景評估，選擇最有前景的節(jié)點(diǎn)進(jìn)一步擴(kuò)展，直到擴(kuò)展至路徑終點(diǎn)。A-star算法是一類能夠合理引導(dǎo)優(yōu)化解搜索方向的深度優(yōu)先搜索算法，其估價(jià)函數(shù)為：

G(z)=D(z)+H(z)

(13)

式中，G(z)為路口z處從起點(diǎn)到終點(diǎn)距離的估價(jià)；D(z)為起點(diǎn)到路口z的實(shí)際距離；H(z)為路口z到終點(diǎn)估計(jì)距離的啟發(fā)式函數(shù)。H(z)的估計(jì)距離越接近于路口z到終點(diǎn)的實(shí)際距離，A-star算法效率越高[18]。

結(jié)合A-star算法快速搜索最短路徑的優(yōu)勢設(shè)計(jì)IAS算法，使備選鄰接路口至路徑終點(diǎn)的估計(jì)值盡可能接近實(shí)際情境下的綜合交通阻抗，從而改善DSI算法的求解效率。IAS算法的啟發(fā)式函數(shù)H(z)將以通行時(shí)間預(yù)估函數(shù)HW(z)和路口延時(shí)預(yù)估函數(shù)HB(z)分別構(gòu)造：

(14)

(15)

G(z)=Diz+HW(z)+HB(z)

(16)

命題實(shí)際路網(wǎng)環(huán)境下，任意一對路口兩項(xiàng)預(yù)估函數(shù)的差值和不超過其相互間的實(shí)際交通阻抗，即算法相容性條件HW(z1)+HB(z2)-HW(z2)-HB(z2)≤Dz1z2成立。

由于A-Star算法相容性條件是其能夠找到最短路徑的充要條件[18]，可知IAS算法為實(shí)際路網(wǎng)環(huán)境下兩位置點(diǎn)間最短行程時(shí)間搜索的精確解法。

算法步驟如下：

Step1數(shù)據(jù)預(yù)處理。尋找全路網(wǎng)最大通行速度，最長路段和路口最短延誤時(shí)間。

Step2初始化路徑。將服務(wù)網(wǎng)絡(luò)的客戶集V的所有元素分別存入備選起點(diǎn)集S和備選終點(diǎn)集E中。確定客戶i為路徑起點(diǎn)，i∈S，S=S-{i}。當(dāng)前節(jié)點(diǎn)z=i，將i存入路徑集合A，當(dāng)前標(biāo)號Tz=0。確定客戶j為路徑終點(diǎn)，j∈E，E=E-{j}。

Step3鄰域搜索。將z的所有鄰接路口m存入備選路口集B，若j∈E則Tij=Tz+Dzj，pz=j，回溯所有pz得到ij間的最短路徑，執(zhí)行Step6；否則Tm=∞，前序路口pm=0。

Step4更新路口標(biāo)號。遍歷B中所有路口，將Dim=Tz+Dzm代入評價(jià)函數(shù)，若H(m)

Step6終止條件。若S=?且E=?，存儲Tij為時(shí)間距離矩陣，算法結(jié)束；否則執(zhí)行Step2。

3.2 混合模擬退火算法

配送車輛調(diào)度為典型的NP-hard問題，難以找到有效的多項(xiàng)式時(shí)間精確解法，因此需設(shè)計(jì)智能優(yōu)化算法進(jìn)行求解[2,3,11]。針對實(shí)際路網(wǎng)車輛調(diào)度模型的特點(diǎn)，以局部搜索能力強(qiáng)、計(jì)算時(shí)間較短、尋優(yōu)操作簡單的模擬退火算法為框架，設(shè)計(jì)了結(jié)合初始解構(gòu)筑規(guī)則和雙鄰域搜索規(guī)則的HSA算法，提升了最優(yōu)調(diào)度計(jì)劃的全局搜索能力。HSA算法的基本參數(shù)為：初始溫度1000、終止溫度1、降溫速率0.9。Metropolis準(zhǔn)則接受惡化解概率需滿足，圖3是算法流程圖。

圖3 HSA算法流程圖

本文采用整數(shù)編碼，0表示配送中心，正整數(shù)表示客戶。每兩個(gè)0間的編碼表示分配給對應(yīng)車輛的客戶服務(wù)順序，任務(wù)序列共有|L|+1個(gè)0。若兩個(gè)相鄰0間沒有其他數(shù)字，則表示該車輛未被啟用。圖4為一組解編碼，車輛1的路徑為0-5-1-0；車輛2的路徑為0-2-3-6-0；車輛3的路徑為0-4-0；車輛4未啟用。

圖4 編碼方式

以“最小服務(wù)時(shí)間優(yōu)先”規(guī)則構(gòu)筑初始解，步驟如下：

Step1差值計(jì)算。計(jì)算客戶時(shí)間窗上界與配送中心開始作業(yè)時(shí)刻的差值Δt(i)=ETi-t0。

Step2客戶排序。按Δt(i)的大小對所有客戶升序排列p1，p2,…pi,i=|V|。

圖5 初始解生成方式

HSA算法的鄰域搜索策略是基于n-opt思想的局部較優(yōu)解搜索策略。對于任意小車型的車輛，其任務(wù)序列可全部或部分替換插入大車型的任務(wù)序列中，但逆向操作將造成不可行解[19]。為快速搜尋優(yōu)化解，充分考慮多車型調(diào)度決策特點(diǎn)后，本文采用隨機(jī)排序和互換插入同時(shí)存在的雙鄰域搜索方式，規(guī)則如下：

規(guī)則一三點(diǎn)隨機(jī)排序。隨機(jī)選中除編碼首末端0位外的任意連續(xù)三個(gè)編碼構(gòu)成的子鏈，隨機(jī)排列組合成新的子鏈后插入選中位置；

規(guī)則一兩點(diǎn)互換插入。隨機(jī)選中不同車輛間的兩個(gè)非0編碼，判斷交換后車輛載重約束的滿足性，若滿足則交換，否則將需求量小的客戶編碼插入到大車的選中編碼之后。

圖6是HSA算法的雙鄰域搜索流程圖。

圖6 雙鄰域搜索

圖7 實(shí)際路網(wǎng)算例

4 仿真分析

以大連市某配送中心運(yùn)營實(shí)例為背景，調(diào)研各客戶周邊交通環(huán)境后，拓?fù)涑鰣D7所示的實(shí)際路網(wǎng)進(jìn)行調(diào)度仿真，所有試驗(yàn)均在中央處理器為Inter Core i7-6700，內(nèi)存為4GB，系統(tǒng)為Windows 7的計(jì)算機(jī)上完成。

4.1 仿真參數(shù)設(shè)置

圖6給出的實(shí)際路網(wǎng)算例包含223個(gè)路口和379條路段。城區(qū)主干道限速以40km/h小時(shí)計(jì)，輔助道限速以30km/h小時(shí)計(jì)。各路段車道數(shù)、車道寬度和單行限制等路網(wǎng)物理性質(zhì)參考實(shí)地交通規(guī)劃，各類型路口日均流量、平均飽和率和各路段日均車流量飽和率以2017年3月調(diào)研數(shù)據(jù)為準(zhǔn)。各類路口阻抗計(jì)算參數(shù)的實(shí)測均值見表1。

表1 路口阻抗實(shí)測均值

配送中心擁有3種型號的6輛車，其核定載重量和車輛啟用的固定成本見表2，日服務(wù)客戶規(guī)模為15，地理位置見圖5，客戶需求量和預(yù)約服務(wù)時(shí)間窗見表3。配送中心起始作業(yè)時(shí)刻為480s，車輛以0.5kg/s的卸貨速率為客戶提供服務(wù)。廣義費(fèi)用均以分鐘為單位取整測度，提前服務(wù)費(fèi)用為0.95元/min，延遲服務(wù)費(fèi)用為1.50元/min，單位時(shí)間價(jià)值系數(shù)為2.7元/min，據(jù)此進(jìn)行行程時(shí)間遞推，可轉(zhuǎn)化得到調(diào)度計(jì)劃的綜合成本。

表2 車輛信息

表3 任務(wù)信息

4.2 算法性能分析

選擇10對距離逐漸增大的客戶對作為路徑選擇算例，IAS算法和DSI算法的計(jì)算時(shí)間如圖8所示。當(dāng)客戶距離較近時(shí)，IAS算法對路網(wǎng)信息的預(yù)處理消耗了部分時(shí)間，DSI算法求解更快；當(dāng)求解結(jié)果逐漸增大即算例客戶間路網(wǎng)復(fù)雜性逐步增加時(shí)，IAS算法搜索規(guī)模較DSI更小，計(jì)算時(shí)間具有一定改善。

圖8 IAS算法與DSI算法的時(shí)間比較

圖9 HSA算法收斂圖

測度指標(biāo)運(yùn)營實(shí)例HSA優(yōu)化率平均載重量利用率0.670.81+20.9%準(zhǔn)時(shí)服務(wù)的客戶數(shù)1113+18.2%客戶服務(wù)違約費(fèi)用/元165.2158.7+3.9%固定成本/元640500-行程時(shí)間轉(zhuǎn)化的運(yùn)營成本/元1166.41054.1+9.4%綜合成本/元1971.61712.8+13.1%

以配送中心實(shí)際配送需求和平峰時(shí)段路網(wǎng)情境設(shè)置標(biāo)準(zhǔn)算例進(jìn)行仿真計(jì)算。圖9的數(shù)值結(jié)果表明HSA算法在求解實(shí)際路網(wǎng)車輛調(diào)度計(jì)劃中具有較好的收斂能力，收斂過程驗(yàn)證了算法的有效性。表4中的實(shí)例對比說明，車輛資源利用方面，HSA算法優(yōu)化了每輛車的客戶服務(wù)序列，減少了相同客戶規(guī)模下的車輛啟用數(shù)量，提升了車輛平均載重量利用率；運(yùn)營成本方面，HSA算法通過規(guī)劃合理的車輛路徑，降低了車輛行程時(shí)間，提升了9.4%的運(yùn)營成本；服務(wù)準(zhǔn)時(shí)性方面，HSA算法在增大了18.2%的準(zhǔn)時(shí)服務(wù)客戶數(shù)的前提下降低了3.9%的違約費(fèi)用。綜上所述，綜合成本同比降低13.1%，驗(yàn)證了HSA算法良好的優(yōu)化能力。

4.3 不同路網(wǎng)情境下的決策對比

模擬實(shí)際路網(wǎng)事件，考慮路段禁行、路段車流量和可由路段車流量遞推得到的路口車流量三項(xiàng)因素的變化能快速改變路網(wǎng)環(huán)境的特點(diǎn)，設(shè)計(jì)不同情境進(jìn)行仿真，分析其對車輛調(diào)度計(jì)劃的影響。詳細(xì)情境設(shè)置見表5。

表5 仿真情境設(shè)置

①主干道增流；②主干道與輔助道混合增流。

4.3.1 路網(wǎng)增流的影響

模擬出行高峰初期過程，保持輔助道車流量不變，以10%至50%的比例遞增路網(wǎng)中主干道的車流量，得到表6所示的仿真結(jié)果。

表6 主干道車流量遞增結(jié)果

①標(biāo)準(zhǔn)算例，即表4中HSA算法的計(jì)算結(jié)果；②主干道流量。

車輛配置和客戶服務(wù)次序的選擇隨主干道車流量的增大不斷優(yōu)化，作業(yè)時(shí)間不斷增大。M-3和M-4顯示主干道車流量增加比例在20%至40%時(shí)，調(diào)度計(jì)劃通過將待服務(wù)客戶更加集中分配給大型車2、3服務(wù)，有效限制了綜合成本的增加。但同時(shí)也降低了計(jì)劃路徑的柔性，增加了客戶違約費(fèi)用； M-4和M-5顯示主干道車流量增加比例超過40%時(shí)，通過增加車輛配置，調(diào)度計(jì)劃雖增大了綜合成本，但行程總用時(shí)和客戶違約費(fèi)用均有所下降。圖9為M算例求解路徑中的不同道路類型分布情況。

圖10分布結(jié)果顯示，MA-0環(huán)境下調(diào)度計(jì)劃選擇的路段類型較為均衡。隨著主干道流量的增加，調(diào)度計(jì)劃包含的路段數(shù)逐漸增加。路徑選擇過程中，為規(guī)避部分通行能力上限較低，受增流沖擊影響較大的主干道，路徑選擇更多借助了附近車流量不變的輔助道繞行。當(dāng)主干道流量增加比例超過30%時(shí)，輔助道在道路總數(shù)中占的比例快速上升，繞行特點(diǎn)顯著。

模擬出行高峰中后期過程，以5%和10%的比例混合增加路網(wǎng)中主干道和輔助道的車流量，得到表7所示的仿真結(jié)果。

圖10 主干道流量遞增后的路段類型選擇

算例變化比例配送路徑車輛編號作業(yè)時(shí)間/min違約費(fèi)用綜合成本MA-0-0-7-2-13-1-9-6-12-14-5-00-15-10-3-8-4-00-11-0245390.4-158.7-1712.8-MA-1ME+40%AE①+10%0-1-7-9-13-5-4-11-14-12-00-8-15-2-10-3-6-023456.2+16.85%195.5+23.19%1835.5+6.68%MA-2ME+45%AE+20%0-15-2-8-6-10-3-00-7-1-12-9-11-13-4-5-14-023458.8+17.52%199.5+25.71%1806.3+7.33%MA-3ME+50%AE+30%0-15-4-8-5-9-6-14-1-00-7-3-10-2-13-11-12-023480.5+23.08%206.5+30.12%1759.2+11.16%MA-4ME+50%AE+40%0-7-8-2-10-5-13-9-11-14-00-4-1-6-3-12-00-15-0265475.3+21.75%177.4+11.78%1798.8+14.48%MA-5ME+60%AE+50%0-15-13-4-12-14-5-2-00-7-1-11-8-3-6-10-9-023488.5+25.13%208.8+31.57%1886.2+12.55%

①輔助道流量。

以M-4的車流量為基準(zhǔn)緩慢增大主干道車流量，同時(shí)快速增大輔助道車流量，大部分MA算例均啟用大型車2、3完成配送任務(wù)，客戶集中分配的趨勢更加明顯。MA-4由于采用了小型車5單獨(dú)為客戶3服務(wù)，增加了綜合成本，但卻在主干道和輔助道車流量均處于較高水平時(shí)保持了較低的違約費(fèi)用。圖10為MA算例求解路徑中的不同道路類型分布情況。

圖11分布結(jié)果顯示，主干道高車流量環(huán)境下，輔助道流量的快速增加限制了繞行路徑的選擇，調(diào)度計(jì)劃包含的路段數(shù)量持續(xù)下降，客戶間的路徑選擇更趨向于空間距離最短。路徑結(jié)構(gòu)方面，主輔道路的數(shù)量比逐漸回歸，于MA-4和MA-5時(shí)達(dá)到平衡。

綜上，調(diào)度計(jì)劃應(yīng)在出行高峰初中期規(guī)避車流量較大的主干道，并有效調(diào)整客戶服務(wù)次序，降低綜合成本。此外，需要協(xié)調(diào)固定成本和違約費(fèi)用間的悖反關(guān)系。

4.3.2 區(qū)域擁堵的影響

模擬區(qū)域群體性社會活動過程，按Solomon-CR規(guī)則確定活動位置，并按照與活動中心的距離將通行時(shí)間受影響的路段劃分為三個(gè)等級。圖12為隨機(jī)群數(shù)4聚集數(shù)量2.5的10個(gè)活動分布算例，參數(shù)設(shè)置見表8，仿真結(jié)果見表9。

圖11 混合流量遞增后的路段類型選擇

圖12 區(qū)域擁堵分布算例

表8區(qū)域擁堵仿真參數(shù)

擁堵級別路段數(shù)量ME變化AE變化一級37+30%+45%二級54+20%+30%三級93+10%+15%

表9區(qū)域擁堵仿真結(jié)果

算例通過的不同級別路段數(shù)量一級二級三級路段總數(shù)違約費(fèi)用MA-01322204204158.7MAC61446237195.5變化率-53.8%-36.4%-9.8%+16.2%+23.2%

表9的仿真結(jié)果顯示，MA-C算例調(diào)度計(jì)劃制定時(shí)一定程度上規(guī)避了擁堵區(qū)域。增加的路段總數(shù)顯示，對于最為擁堵的活動中心鄰近區(qū)，新計(jì)劃以繞行方式規(guī)避了原計(jì)劃中近半數(shù)的一級路段和36.4%的二級路段；而對于活動輻射的外圍三級路段，新計(jì)劃不進(jìn)行刻意規(guī)避，其對路徑選擇的影響意義不大。違約費(fèi)用的增大顯示新計(jì)劃規(guī)避擁堵區(qū)域時(shí)仍需進(jìn)一步優(yōu)化客戶服務(wù)次序，保證客戶服務(wù)的準(zhǔn)時(shí)率。

4.3.3 路段禁行的影響

模擬突發(fā)事件或道路施工過程，按隨機(jī)搜索的方式尋找一定比例的路段禁行處理。設(shè)置BF算例4組，以2.5%的禁行路段選取比例遞增，得到表10所示的仿真結(jié)果。

表10 隨機(jī)禁行仿真結(jié)果

表9的仿真結(jié)果顯示，路網(wǎng)各路段禁行比例小于5%時(shí)，路段禁行對于作業(yè)時(shí)間和客戶違約費(fèi)用不造成明顯影響。當(dāng)禁行比例超過并逐步增大時(shí)，為控制違約費(fèi)用的增長，調(diào)度計(jì)劃將啟用更多的小型車輛。MF-3和MF-4中各有車輛1和車輛5僅服務(wù)一個(gè)客戶，即是對具有較大違約費(fèi)用客戶的單獨(dú)服務(wù)，其綜合成本明顯增大。因此，調(diào)度計(jì)劃制定時(shí)需充分考慮路網(wǎng)中的道路施工與突發(fā)事件情況。

5 結(jié)論與展望

實(shí)際路網(wǎng)車輛調(diào)度是時(shí)間距離路徑選擇和車輛調(diào)度的二階段決策問題，相比于VRP及其延伸問題更為復(fù)雜，求解過程也更繁瑣。結(jié)合路網(wǎng)物理特點(diǎn)測度路段綜合交通阻抗，構(gòu)造客戶時(shí)間距離矩陣，建立多車型車輛調(diào)度數(shù)學(xué)模型。仿真實(shí)驗(yàn)結(jié)果表明，本文設(shè)計(jì)的IAS精確解算法相比于DSI算法在客戶時(shí)間距離矩陣求解中具有更小的搜索規(guī)模，HSA算法能有效優(yōu)化車輛調(diào)度方案。模擬路網(wǎng)情境發(fā)現(xiàn)，高峰出行、群體性社會活動、道路施工和突發(fā)事件均能對調(diào)度計(jì)劃制定產(chǎn)生一定程度的影響。未來研究將細(xì)分上述因素，將更多路網(wǎng)結(jié)構(gòu)特性納入數(shù)學(xué)模型考慮，并實(shí)現(xiàn)實(shí)際路網(wǎng)的動態(tài)應(yīng)急調(diào)度。