基于實際路網情境的配送車輛調度優化

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

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

0 引言

城市配送是現代物流業發展關注的熱點問題。作為供應鏈末端環節之一，其效率對保障各行業物資儲備，提高居民生活質量具有重要意義。作為物流系統優化的經典問題，車輛調度問題(Vehicle Routing Problem, VRP)的研究者不斷結合生產實際，充分考慮了不同配送類型間的作業特點、服務效率和社會價值。

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

近年來，隨著城市化進程的推進和機動車數量的增加，路網規模不斷擴大，結構日趨復雜。車輛因路網環境影響而提早或延遲執行配送任務甚至取消任務的概率大大增加，配送中心亟待尋找更加可靠的調度計劃制定方法。

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

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

1 問題描述

車輛在實際路網中的行駛往往面臨諸多因素的綜合影響。路網車流量、道路容量、路口車輛飽和程度、交通信號燈以及道路行駛規則均能導致車輛實際運行情況與配送效率與調度計劃存在較大偏差。因此，在制定準時、高效、低成本調度計劃的同時如何結合路網因素優化配送方案，降低計劃與實際存在的作業偏差，是提升城市配送服務水平的瓶頸之一。

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

圖1 路網因素影響下的車輛路徑選擇

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

2 數學建模

基于兩層連通圖，先構造基于實際路網的客戶時間距離矩陣，再以該矩陣為基礎，建立車輛調度模型。由于城市配送具有短程高頻特點，相鄰客戶通行時段內路網時空特征變化不大，因此以車輛出發時刻更新路網信息，降低計算規模。

2.1 客戶時間距離矩陣

在路網信息圖N中，尋找兩兩匹配的客戶間具有最短通行時間的路徑，構建客戶時間距離矩陣。區別于傳統網絡，實際路網情境中的各類因素均能對路徑選擇產生影響，因此分類歸納其物理特點，引入交通阻抗測度方法描述相應特征。

假設時間距離矩陣求解時，路網路段車道數、車道寬度和單向限行規則等物理特點短期內不發生改變；路口平均車流量可通過所有鄰接路段的車流量進行估計。

描述路網因素的符號如下。

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方向的車道數量，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|；

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

Step1分析實際路網的物理特點并進行數學表達

根據實際行車經驗，車道寬度一定時，路段單向車道數越多，其自由流速度越大；路段單向車道數一定時，車道寬度越大，其自由流速度也越大。通過國內城市路網浮動車數據收集分析[15]，設置單向三車道且每車道寬3m的城市道路為標準道路，以限速的85%位速推導自由流速度[16]。各路段自由流速度vmn的計算公式如下：

2.27(LWmn-3)

(1)

Step2測度路口等待時間

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

(2)

Step3測度路段通行時間

引入BRP函數，測度與自由流速度、路段容量和平均交通流量相關的路段通行時間tmn：

(3)

Step4計算路段綜合阻抗

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

(4)

由此，客戶時間距離矩陣RT可通過尋找客戶i至客戶j間具有最短通行時間的路徑構造，數學表達如下。

2.2 車輛調度模型

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

模型的假設條件如下。

(1)每個客戶點僅由一輛車服務一次；

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

(3)卸貨作業準備時間不計，即車輛到達客戶后立即開始作業。

模型中的符號如下。

L：配送中心當前擁有的車輛數量；

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

vd：卸貨速率；

α：車輛行駛過程中的單位時間價值系數；

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

cE：提前服務單位時間費用；

cL：延遲服務單位時間費用；

Ci：車輛l的違約費用，l=1,2,…,L；

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

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

ET0：車輛從配送中心出發時刻；

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

決策變量有：

根據決策變量，可推導得如下變量：

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

(5)

目標函數與約束條件為

(6)

(7)

(8)

(9)

(10)

(11)

(12)

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

3 兩階段求解策略

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

圖2 算法整體思路

3.1 改進A-star算法

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

為降低節點搜索規模，提高求解效率，路網最短路徑問題可通過基于啟發式規則的A-star算法[18]求解。它能夠通過估價函數的計算對未擴展的節點進行前景評估，選擇最有前景的節點進一步擴展，直到擴展至路徑終點。A-star算法是一類能夠合理引導優化解搜索方向的深度優先搜索算法，其估價函數為：

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

(13)

式中，G(z)為路口z處從起點到終點距離的估價；D(z)為起點到路口z的實際距離；H(z)為路口z到終點估計距離的啟發式函數。H(z)的估計距離越接近于路口z到終點的實際距離，A-star算法效率越高[18]。

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

(14)

(15)

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

(16)

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

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

算法步驟如下：

Step1數據預處理。尋找全路網最大通行速度，最長路段和路口最短延誤時間。

Step2初始化路徑。將服務網絡的客戶集V的所有元素分別存入備選起點集S和備選終點集E中。確定客戶i為路徑起點，i∈S，S=S-{i}。當前節點z=i，將i存入路徑集合A，當前標號Tz=0。確定客戶j為路徑終點，j∈E，E=E-{j}。

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

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

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

3.2 混合模擬退火算法

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

圖3 HSA算法流程圖

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

圖4 編碼方式

以“最小服務時間優先”規則構筑初始解，步驟如下：

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

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

圖5 初始解生成方式

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

規則一三點隨機排序。隨機選中除編碼首末端0位外的任意連續三個編碼構成的子鏈，隨機排列組合成新的子鏈后插入選中位置；

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

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

圖6 雙鄰域搜索

圖7 實際路網算例

4 仿真分析

以大連市某配送中心運營實例為背景，調研各客戶周邊交通環境后，拓撲出圖7所示的實際路網進行調度仿真，所有試驗均在中央處理器為Inter Core i7-6700，內存為4GB，系統為Windows 7的計算機上完成。

4.1 仿真參數設置

圖6給出的實際路網算例包含223個路口和379條路段。城區主干道限速以40km/h小時計，輔助道限速以30km/h小時計。各路段車道數、車道寬度和單行限制等路網物理性質參考實地交通規劃，各類型路口日均流量、平均飽和率和各路段日均車流量飽和率以2017年3月調研數據為準。各類路口阻抗計算參數的實測均值見表1。

表1 路口阻抗實測均值

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

表2 車輛信息

表3 任務信息

4.2 算法性能分析

選擇10對距離逐漸增大的客戶對作為路徑選擇算例，IAS算法和DSI算法的計算時間如圖8所示。當客戶距離較近時，IAS算法對路網信息的預處理消耗了部分時間，DSI算法求解更快；當求解結果逐漸增大即算例客戶間路網復雜性逐步增加時，IAS算法搜索規模較DSI更小，計算時間具有一定改善。

圖8 IAS算法與DSI算法的時間比較

圖9 HSA算法收斂圖

測度指標運營實例HSA優化率平均載重量利用率0.670.81+20.9%準時服務的客戶數1113+18.2%客戶服務違約費用/元165.2158.7+3.9%固定成本/元640500-行程時間轉化的運營成本/元1166.41054.1+9.4%綜合成本/元1971.61712.8+13.1%

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

4.3 不同路網情境下的決策對比

模擬實際路網事件，考慮路段禁行、路段車流量和可由路段車流量遞推得到的路口車流量三項因素的變化能快速改變路網環境的特點，設計不同情境進行仿真，分析其對車輛調度計劃的影響。詳細情境設置見表5。

表5 仿真情境設置

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

4.3.1 路網增流的影響

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

表6 主干道車流量遞增結果

①標準算例，即表4中HSA算法的計算結果；②主干道流量。

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

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

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

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

算例變化比例配送路徑車輛編號作業時間/min違約費用綜合成本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的車流量為基準緩慢增大主干道車流量，同時快速增大輔助道車流量，大部分MA算例均啟用大型車2、3完成配送任務，客戶集中分配的趨勢更加明顯。MA-4由于采用了小型車5單獨為客戶3服務，增加了綜合成本，但卻在主干道和輔助道車流量均處于較高水平時保持了較低的違約費用。圖10為MA算例求解路徑中的不同道路類型分布情況。

圖11分布結果顯示，主干道高車流量環境下，輔助道流量的快速增加限制了繞行路徑的選擇，調度計劃包含的路段數量持續下降，客戶間的路徑選擇更趨向于空間距離最短。路徑結構方面，主輔道路的數量比逐漸回歸，于MA-4和MA-5時達到平衡。

綜上，調度計劃應在出行高峰初中期規避車流量較大的主干道，并有效調整客戶服務次序，降低綜合成本。此外，需要協調固定成本和違約費用間的悖反關系。

4.3.2 區域擁堵的影響

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

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

圖12 區域擁堵分布算例

表8區域擁堵仿真參數

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

表9區域擁堵仿真結果

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

表9的仿真結果顯示，MA-C算例調度計劃制定時一定程度上規避了擁堵區域。增加的路段總數顯示，對于最為擁堵的活動中心鄰近區，新計劃以繞行方式規避了原計劃中近半數的一級路段和36.4%的二級路段；而對于活動輻射的外圍三級路段，新計劃不進行刻意規避，其對路徑選擇的影響意義不大。違約費用的增大顯示新計劃規避擁堵區域時仍需進一步優化客戶服務次序，保證客戶服務的準時率。

4.3.3 路段禁行的影響

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

表10 隨機禁行仿真結果

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

5 結論與展望

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