動態路網下帶時間窗車輛路徑規劃問題研究

盛 強，鄭鵬飛，孫軍艷

（1.陜西科技大學，陜西 西安 710021；2.鄭州風神物流有限公司，河南 鄭州 450000）

1 引言

車輛路徑問題（VRP）最早是由Dantzig和Ramser于1959年提出，經典的VRP假設已知客戶網絡中的客戶數量、客戶所在的位置、客戶需求和配送車輛的最大負荷，要求在滿足約束的前提下為給定的中心倉庫設計車輛路徑，使運輸成本最小。隨著研究的不斷深入，考慮客戶對配送時效性的要求衍生出帶時間窗約束的VRP（VRP with Time windows,VRPTW），其最優解是在VRP的基礎上通過增加車輛數或行駛距離以滿足顧客對時間的要求，VRPTW的提出體現了物流配送企業在關注成本的同時開始關注服務質量。但車輛配送過程是在動態路網中進行，靜態路網VRP最優線路會受交通堵塞、管制等路況信息的影響，車輛所消耗的時間并不一定最短，配送效率和服務質量也無法保障，特別是當顧客對訪問時間有限制時，影響更為嚴重。隨著市場競爭越來越激烈，企業對服務質量的要求越來越高，因此動態路網下路徑規劃問題的服務質量成為企業關注的熱點。

求解動態路網路徑規劃的方法主要分為兩類：一類是通過預測獲取路況信息作為已知條件在算法中體現，如袁二明等[1]通過預測交通網絡中發生擁堵的概率并結合圖論求解最短路線，何靚等[2]使用灰色理論預測各路段車流速度，以時間最短為目標求解最優路徑。另一類是定義反映路況信息的相關變量并引入到算法中進行求解，如杜業凡[3]在GM(1,1)模型的基礎上，定義路阻函數并與蟻群算法結合給出算法流程圖，于麗梅[4]定義車輛隨機減速影響因子，以耗時最短為目標應用模擬退火算法求解耗時最短線路，蔡延光等[5]認為不同時段、路段上車輛速度不同，將油耗率轉化為信息素揮發因子應用蟻群算法求解耗時最短線路，李培慶等[6]考慮道路等級、路面不平度等影響因素，建立VRPTW模型并應用遺傳算法求解滿足時間限制的最短路徑。但相關文獻多以行駛距離或行駛時間為指標進行評價，未對服務質量進行相關討論。

為提高物流配送企業服務質量和顧客滿意度，本文提出一種解決動態路網下VRPTW的方法，考慮動態路網下各路段分時段的道路通過能力（road capacity）差異，定義通過能力系數來反映實時路況信息，在VRPTW基礎上建立優化模型，結合遺傳算法進行求解，并與靜態路網VRPTW結果從服務滿意度、行駛距離等指標進行對比和分析，為企業協調配送成本與服務質量之間的矛盾提供借鑒。

2 問題描述

為研究動態路網下路況信息對車輛路徑的影響，參考相關文獻中有關表述，道路通過能力是指在通常的道路、交通和管制條件下，在一定時間段內車輛能夠通過道路某一點的最大數量。道路通過能力越大表明該路段車輛越少，車輛的自由度越高，行駛該路段的時間也就越短[7]。

考慮到路段在不同時段的通過能力不同，尤其是存在早高峰、晚高峰等情況，本文定義三維向量T（i，j，t）為通過系數，其中i和j表示客戶編號，t為時間變量。定義當T=0時兩客戶之間道路不聯通，T=1時客戶i和j之間道路t時刻車流量正常，車輛可以正常速度行駛，T＜1時該時刻該路段產生不同程度的擁堵，通過系數越小，擁堵程度越大。

本文結合參考文獻[7]把通過系數反映到車輛速度上，在進行線路規劃時車速Vi等于標準車速T與通過系數V的乘積。公式如下：

時間窗[e，l]是顧客期望的服務時間段，超出這個時間段服務效果必然下降，甚至顧客拒絕接收，配送中心因此會產生經濟上的損失。為了量化配送車輛超出客戶時間窗后所受到的“懲罰”，以及提前到達所產生的“機會成本”，本文定義懲罰函數Pi(Si)表示配送中心違反時間窗的成本支出。

其中ei為客戶i時間窗的起點；li為客戶i時間窗的終點；si為客戶i到達的時間；p為提前到達的單位懲罰成本；q為滯后到達的單位懲罰成本。

3 數學模型

動態路網下VRPTW是一個多約束優化問題，可描述為：1個配送中心最多可用m輛車訪問n個客戶，每個客戶必須訪問且只能訪問一次，車輛集合K={1,2,…,k}，客戶集合N={1,2,…,n}，客戶需求為qi，車輛容量限制為Q，兩點間的配送距離為dij，運輸時間為tij，每個客戶都有一個指定的時間窗[ei，li]，車輛早到或者晚到都要受到懲罰，各路段在不同時刻的通過系數T可通過交通管理部門獲取，所有車輛從配送中心出發，服務客戶后回到配送中心。決策變量分別為：

定義c1為單位距離運輸成本，c2為車輛啟用固定成本，α為距離成本權重，β為車輛成本權重，γ為懲罰成本權重，在此基礎上建立以總成本最小為目標函數的數學模型。如下：

其中，式（3）為目標函數，包括距離成本、車輛成本、懲罰成本（提前或延遲）三種；式（4）表示每輛車從配送中心出發后又回到配送中心；式（5）表示每個客戶僅能被一輛車服務；式（6）為車輛容量限制；式（7）表示車輛到達客戶后必須離開；式（8）為配送中心時間窗約束，fi為客戶i所需的裝卸時間（與需求量qi成正比），wi為車輛提前到達等待時間；式（9）為客戶時間窗約束；式（10）為懲罰函數。

4 算法設計

VRPTW問題是一個NP難問題，其求解主要集中在遺傳算法、蟻群算法等啟發式算法上。上世紀90年代Thangiah[8]和Joe[9]等就開始研究用遺傳算法求解VRPTW問題，隨后張麗萍等[10]、劉敏等[11]國內學者針對遺傳算法求解VRPTW的“早熟性收斂”等問題進行了研究，并分別從改進選擇規則、改進變異方式等方面進行相關研究，結果表明，改進后的遺傳算法求解VRPTW效果優于傳統遺傳算法。

車輛路徑是個順列問題，本文采用自然數編碼，用矢量（s1,s2,…,sn）表示染色體，其中sn為1到n的自然數，表示客戶。首先隨機產生一組染色體，解碼過程依次從染色體中提取基因，檢查是否滿足約束條件，如果滿足就插入到線路中，如果不滿足就開始新的路線，并在每條線路的起點和終點插入“0”表示配送中心。

為保證遺傳過程中優秀基因高概率保留，在輪盤賭選擇前采用精英保留策略并對新種群進行無序排列，將保留下來的優良個體與輪盤賭選擇的個體隨機放置，以避免后續交叉過程中優良個體相互交叉、隨機個體相互交叉的情況。

參考文獻[10]，本文采用類PMX重組方式，該方式能夠在父代染色體相同情況下達到一定的變異效果，對維持群體多樣性有較好的作用。選取兩個父代染色體A和B并隨機生成兩個交叉點，把兩個交叉點之間的基因片段添加到對方染色體的前端得到A′和B′，將交配區域后的重復基因刪除得到子代染色體A″和B″。具體過程如下所示：

變異策略是指個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。參考文獻[11]，本文采用基因片段反轉變異的變異策略，此策略在排序問題方面優于傳統的對換變異等策略。選取任意染色體C并隨機生成兩個交叉點，把兩個交叉點之間的基因片段進行翻轉得到編譯后的染色體C′。具體過程如下所示：

C=6 5|8 2 4|7 9 3 1；C′=6 5|4 2 8|7 9 3 1

5 實驗分析

對于車輛路徑問題的測試算例最常用的是Solomon提出Benchmark Problems數據庫[12]。該測試庫中包含56個實例，每個實例都由一個配送中心和若干個顧客構成，并給出了配送中心和客戶的位置坐標、客戶的需求量以及服務的時間窗、車輛的載重量。結合本文研究對象選用實例R101，并結合實際取車輛的裝載量Q=80kg。根據以上信息得出算例見表1。

基于上述分析，運行Matlab.2010b分別求解靜態路網和動態路網VRPTW各40次，將運行結果取均值進行統計，見表2。

分別取動態路網和靜態路網下40次求解中的最優解路線圖和收斂圖，如圖1所示。

為定量評價不同算法的顧客滿意度，參考文獻[13]引入客戶滿意度函數U(Si)，并將其與車輛行駛距離等指標進行綜合分析。

表1 實驗數據

表2 仿真結果統計

其中Si為第i個客戶的服務開始時間，LTi為第i個客戶可接受最晚服務時間，ELTi為第i個客戶容忍最晚服務時間，β為時間的敏感系數，參考文獻[13]并結合實際，本文取β=1，ELTi取最晚服務時間加兩倍的服務時間，即：

其中k為裝卸服務時間與需求量的比例系數，為便于計算本文取k=1。從服務滿意度、車輛行駛距離、車輛數等指標將上述兩問題所運行的40次最優解進行統計，結果見表3。

表3 實驗效果對比

通過對比可以看出，本文提出的基于動態路網的VRPTW模型獲得的最優解比靜態路網最優解提高了8.45%的服務滿意度，在車輛數不變的情況下增加了1.93%的車輛行駛距離，按照算例中的距離單位，實際增加行駛距離4.381km，相較于服務滿意度的提升，行駛距離增加量在可容忍范圍內。本文提出的算法能夠幫助企業在平衡配送成本與服務質量時提供一定的借鑒，尤其是對于追求高服務質量的物流配送企業更加有價值。

圖1 不同路網環境下最優路徑及收斂圖