時變單車路徑問題建模及算法設計

彭 勇，謝祿江，劉 松

（1.重慶交通大學交通運輸學院，重慶 400074;2.永川供電局，重慶 402160）

時變單車路徑問題建模及算法設計

彭 勇1，謝祿江2，劉 松1

（1.重慶交通大學交通運輸學院，重慶 400074;2.永川供電局，重慶 402160）

討論了一類時變單車配送路徑優化問題。綜合考慮車輛行駛速度隨時間、路段不同而變化的特點，及車輛為多條路線上的客戶提供服務時對車輛路徑優化的影響，建立了以配送完成時間最早為優化目標的時變單車配送路徑優化模型。在行駛時間滿足FIFO規則下，設計了基于Inver-over操作的PSO啟發式算法及滿足貪婪配送策略下的動態規劃精確求解算法，并討論了增加貪婪補貨策略的單車配送路徑問題解與原問題解的關系。最后分別用兩種算法對算例進行求解，并通過對求解優化結果及計算時間的對比分析驗證了IOPSO算法的有效性。

路徑優化;動態規劃;粒子群算法;時變;FIFO規則

車輛路徑問題自1959年提出以來，一直是網絡優化問題中最基本的問題之一，由于其應用的廣泛性和經濟上的重大價值，一直受到國內外學者的廣泛關注［1］。從目前眾多研究文獻來看，兩個車輛路徑優化需要考慮的問題受到較少關注:①車輛行駛速度隨時間、路段不同而變化的特點（時變特性），及車輛為多條路線上的客戶提供服務的問題［2-7］;②考慮城市配送中配送企業對配送區域進行劃分，不同配送區域的客戶由一輛車配送，對該車輛不要求一次完成所有客戶（需求點）的配送，配送過程中可以回貨源點補貨，這就形成單車路徑優化問題［3-5］。在現實世界中，特別是城市地區，車輛行程時間同時依賴于兩客戶之間的距離和速度，交通擁堵等因素均會導致車輛不同時刻不同客戶間行駛速度發生變化，從而使得車輛在不同客戶點間的行程時間成為一變化值［5-6］。筆者綜合這兩個因素，研究有一個貨源點及多個需求點，且需求點由一輛運輸能力有限的車輛提供服務的具有時變特性的車輛路徑優化問題。

1 時變路網單車路徑模型

令圖G=（N，E），頂點集合N={0，1，…，n}，其中0為貨源點，{0}表示需求點集合;E={（i，j）;i≠j;i，j∈N}為頂點間的連接弧，頂點間距離D={dij;i，j∈N}，其中dii=0?？蛻鬷需求為qi，q0=0表示貨源點需求為0。i點服務時間為tsi，當i∈時，tsi表示在相應需求點卸貨等消耗的時間;當i=0時，ts0表示車輛在貨源點裝載貨物等消耗的時間。令tai為車輛到達點的時間，函數tij（tai+tsi）表示從需求點i離開到達需求點j消耗的時間，計算滿足FIFO規則［8］。R為配送路徑集合。Qmax為車輛最大裝載量。

定義決策變量（i，j∈N，i=j，r∈R），如果車輛在路徑r中為點i完成服務后下一服務點為j時，1，否則，0。則時變路網單車路徑優化問題數學描述如下:

式（1）給出模型優化目標為車輛從貨源點裝貨開始為客戶提供送貨服務到完成所有客戶送貨服務返回貨源點的時間最早;式（2）為車輛能力約束，即車輛服務的任意一條路徑上的客戶需求總量不能超過車輛最大裝載量;式（3）表示每個需求點僅由此車提供一次服務;式（4）為平衡條件，即車輛到達某點次數與車輛離開其點次數相同;式（5）確保配送回路通過貨源點;式（6）為配送路徑各點先后順序時間邏輯。

2 基于Inver-over操作的PSO啟發式算法

車輛路徑問題為NP難，筆者給出基于Inver-over操作［9］的 PSO 啟發式算法（IOPSO）。

粒子群優化算法（PSO）［10］有著速度快、解質量高、程序代碼簡潔等優點，在各類多維連續空間優化問題、神經網絡訓練等領域中均取得了很好的效果。由于粒子位置和速度不易表達，而限制了其在組合優化領域中的應用。高海兵，等［11］基于傳統算法的速度-位移搜索模型分析粒子群優化機理，提出廣義粒子群優化模型，使粒子群優化算法適用于離散及組合優化領域。筆者取粒子編碼為1～m（m＞n），其中，粒子編碼中1～n的順序為車輛為客戶提供配送服務的順序，n+1～m的數字用于路徑分割。比如，當n=6，m=10 時，粒子（1，2，7，9，5，3，8，4，6，10）表示的車輛配送路徑為0→1→2→0→5→3→0→4→6→0。尋優過程如下:

1）隨機初始化粒子種群，對每一個粒子，若滿足原問題約束，按式（1）計算粒子適應值，若不滿足約束，給出一個足夠大數作為該粒子適應值。

2）對選定粒子，粒子編碼中隨機選擇一個數i。

3）如果rand≤p，則從該粒子編碼中其它數中隨機選擇另一個數j;如果p＜rand≤pc，則選擇該粒子個體極值編碼中數i相鄰的數為j;否則，選擇全局極值編碼中數i相鄰的數為j。

4）如果該粒子編碼中，數i相鄰的數即為j，轉到步驟6）。

實現水利現代化是一個動態發展的長期過程，不可能一蹴而就、一勞永逸。我們要深入貫徹落實科學發展觀，努力踐行可持續發展治水思路，以高度負責的態度、開拓創新的精神和求真務實的作風，團結拼搏、積極進取，奮發努力、扎實工作，全面推進水利改革創新，著力加快水利現代化建設，在新的起點上譜寫江蘇水利事業發展新篇章。

5）對該粒子編碼中，數i與數j之間的部分進行Inver-over操作，令i=j，轉到步驟3）。

6）計算粒子適應值（若滿足原問題約束，按式（1）計算粒子適應值，若不滿足約束，給出一個足夠大數作為該粒子適應值），并與未進行任何操作前該粒子的適應值進行比較，如果改變后的粒子適應值優于改變前的粒子適應值，則對粒子進行改變，并更新個體極值;否則，不對粒子進行改變;轉到步驟2），直到遍歷種群中所有粒子。

7）更新全局極值。

8）轉到步驟2），直至終止條件滿足。

3 貪婪補貨策略動態規劃精確求解方法

由于所給問題尚未見同類研究，基于Inver-over操作的PSO啟發式算法有效性難以通過與同類研究比較驗證。

可以對以上模型增加補貨策略:在確定好一種車輛配送客戶順序后，車輛在貨源點總是裝滿貨物，對未完成配送的客戶按順序進行配送，并在車輛裝載貨物不能滿足下一配送客戶需求時才返回貨源點裝滿貨再進行配送（貪婪補貨策略），配送目標是找到一個客戶配送順序，使滿足貪婪補貨策略的配送時間最短。

當增加貪婪補貨策略后，可設計如下動態規劃算法（SGDP）給出問題精確解。

路網中客戶頂點集合{0}，N1?。令QN1為車輛N2服務完集合中所有點剩余裝載量。定義T（N2，i）為車輛從貨源點0出發經過集合N2中所有點（但不包括i點）到達i的最早時刻（若車輛剩余裝載量不能滿足i，則車輛將先到貨源點0裝滿貨物再到i點）。則所給問題優化目標可表達為:

對增加補貨策略的本文模型，可給出動態規劃優化方法如下。

2）?i∈，令N2={i}，計算

3）對每一N2，?j∈N2，計算

令N1=N1U{j}，如果N1=，轉到 4）;否則，轉到3）。

則最優車輛配送用時為（T0'-T0）。逆向追蹤計算得到最優車輛配送用時過程，可得車輛最優配送路徑。

在原問題模型中，沒有約束要求車輛在不能滿足下一送貨客戶需求時才返回貨源點裝滿貨再進行送貨服務，即車輛完全可以在車上剩下的貨物能滿足下一送貨客戶，甚至是下幾個客戶需求情況下提前回貨源點補貨（且補貨也不需要一定要裝滿）。通過增加此補貨策略，實際上限定了補貨的多種可能性，這一補貨策略也符合現實中的送貨實際。但增加貪婪補貨策略限定了原問題多種補貨可能性，因此，所給解對原問題僅為滿意解。

4 數值算例

假設裝載能力為Qmax的車輛在T0=0到達貨源點0開始裝貨為10個需求點提供配送服務，且需求點之間的距離、需求及服務時間已知，見表1、表2。

表1 需求點間距離Table 1 Distance between two customers

表2 客戶需求量Table 2 Customer demand

現實世界中，不同客戶間不同時刻不同行駛方向的行駛速度不一定相同，算法可以根據不同客戶間不同時刻不同行駛方向給出不同速度函數，為減少給出的數據量，且不影響分析，本算例假設不同客戶間不同行駛方向具有相同的速度函數，并成周期性變化。

速度周期變化函數離散化為如圖1中的函數，各客戶間沿不同方向的函數為圖1中的函數按表3所給位移量向左做相應位移。比如，從需求點2到需求點3不同時刻行駛速度函數即為圖1圖形向左位移4個時間單位，形成需求點2到需求點3不同時刻行駛速度函數（圖2），其它客戶間速度函數同理可得。

圖1 各路段速度周期變化基準Fig.1 Vehicle speed benchmark

表3 路段擁堵時間位移量Table 3 Time displacement compared with benchmark

圖2 需求點2到需求點3速度函數Fig.2 Vehicle speed function from customer 2 to customer 3

利用文中所給算法在CPU1.60 GHz的同一臺電腦上計算對比車輛在不同最大裝載能力情況下車輛總配送時間，見表4。其中，IOPSO算法中種群規模為100，最大迭代次數為 500，p=0.04-0.03 × 當前迭代次數/最大迭代次數，pc=0.3。p的取值方法使得IOPSO在開始時探索較大的區域，較快定位最優解的大致位置，隨著迭代次數增加，p逐漸減小，粒子速度減慢，開始精心的局部搜索（這里p類似于模擬退火中的溫度參數）。

表4 不同裝載能力SGDP與IOPSO算法計算對比Table 4 Compare between SGDP and IOPSO with different vehicle capacity

從SGDP算法計算結果來看，不同需求點數量的車輛配送路徑優化配送時間都有隨車輛裝載能力增加而減少的趨勢，并且在車輛裝載能力大于客戶總需求的時候達到最小。但在車輛裝載能力等于25箱時，配送時間為6.28 h，大于車輛裝載能力等于20箱時的配送時間6.10 h。分析原問題可知，車輛裝載能力大的車輛至少可以按照裝載能力小的車輛使用，因此車輛裝載能力大的車輛優化的配送時間至少能夠獲得不差于車輛裝載能力小的車輛優化的配送時間。出現該種情況的原因是SGDP算法求解的模型增加了貪婪補貨策略。由于該策略忽略了其它一些補貨行為（如在此案例中，車輛裝載能力為25箱時的貪婪補貨策略即忽略了車輛裝載能力為20箱時的優化配送策略）。因此，所給解為貪婪補貨策略問題的最優解，但對原問題僅為滿意解。

從表4數據來看，IOPSO算法計算結果總體略優于SGDP算法計算結果，差別不明顯。但IOPSO算法計算效率明顯優于SGDP算法。由于動態規劃算法并不是多項式時間算法，因此，隨著問題規模的增大，IOPSO算法的計算時間優勢將更加明顯。從表5及圖3來看，IOPSO算法具有滿意的尋優效率及計算結果穩定性。綜合以上分析驗證了IOPSO算法解決了本文給出數學模型的有效性。

表5 裝載能力25箱時IOPSO算法5次計算結果Table 5 Results calculated by IOPSO 5 times when capacity is 25

圖3 裝載能力為25箱時IOPSO算法粒子群最優值更新過程（優化配送時間6.04 h）Fig.3 Iteration process by IOPSO when capacity is 25（total dispatching time is 6.04 h）

5 結語

討論了時變單車配送路徑優化問題，建立了以配送完成時間最早為優化目標的時變單車配送路徑優化模型。由于車輛路徑問題為NP難，在行駛時間滿足FIFO規則下，設計了所給模型基于Inver-over操作的PSO啟發式算法（IOPSO）。為了驗證IOPSO算法的有效性，筆者設計了滿足貪婪配送策略下的動態規劃精確求解算法（SGDP），并討論了增加貪婪配送策略的單車配送路徑問題解與原問題解的關系。數值算例通過兩種算法優化結果及計算時間的對比分析驗證了IOPSO算法的有效性。

（References）:

［1］ Dantzig G，Ramser J.The truck dispatching problem［J］.Management Science，1959，6:80-91.

［2］ Taillard E D，Laporte G，Gendreau M.Vehicle routing with multiple use of vehicles［J］.Journal of the Operational Research Society，1996，47:1065-1070.

［3］ Azi N，Gendreau M，Potvin J Y.An exact algorithm for a single vehicle routing problem with time windows and multiple routes［J］.European Journal of Operational Research，2007，178:755-766.

［4］ 彭勇.變需求車輛路線問題建模及基于Inver-over操作的PSODP 算法［J］.系統工程理論與實踐，2008，28（10）:76-81.

Peng Yong.Research on vehicle routing problem with stochastic demand and PSO-DP algorithm with Inver-over operator［J］.Systems Engineering Theory＆ Practice，2008，28（10）:76-81.

［5］ Gribkovskaia I，Laporte G，Aliaksandr S.The single vehicle routing problem with deliveries and selective pickups［J］.Computers and Operations Research，2008，35:2908-2924.

［6］ Malandraki C，Daskin M S.Time dependent vehicle routing problems:formulations，properties and heuristic algorithms ［J］.Transportation Science，1992，26（3）:185-200.

［7］ Kok A L，Hans E W，Schutten J M J.Vehicle routing under timedependent travel times:the impact of congestion avoidance［J］.Computers＆ Operations Research，2012，39（5）:910-918.

［8］ 于青，趙輝.基于GA的時變路網中車輛動態派遣的研究［J］.計算機工程與應用，2008，44（22）:210-212.

Yu Qing，Zhao Hui.Research on time dependent vehicle routing problem based on GA ［J］.Computer Engineering and Applications，2008，44（22）:210-212.

［9］ Michalewicz Z，Fogel D B.How to Solve It:Modern Heuristics［M］.Berlin:Springer-Verlag，2000.

［10］ Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proceedings of IEEE International Conference on Neutral Networks.Australia:Perth Press，1995:1942-1948.

［11］高海兵，周馳，高亮.廣義粒子群優化模型［J］.計算機學報，2005，28（12）:1980-1987.

Gao Haibing，Zhou Chi，Gao Liang.General particle swarm optimization model［J］.Chinese Journal of Computers，2005，28（12）:1980-1987.

Route Modeling and Algorithm Designing of Time-Dependent Single Vehicle

Peng Yong1，Xie Lujiang2，Liu Song1
（1.School of Traffic＆ Transportation，Chongqing Jiaotong University，Chongqing 400074，China;
2.Yongchuan Power Supply Bureau，Chongqing 402160，China）

The route optimization problems of one kind of time-dependent single vehicle are discussed.With the comprehensive consideration that vehicle’s velocity is changing with time and different sections of road，as well as the influence of vehicle route optimization when the vehicle provides service for multiple routes customers，a route optimization model of timedependent single vehicle is established，which takes the earliest distribution completion time as the optimization target.A particle swarm optimization algorithm based on inver-over operator with FIFO rule is developed.Adding greed dispatching restriction，a dynamic programming algorithm with FIFO rule is provided.The numerical example verifies the validity of theoretical analysis results.

route optimization;dynamic program;particle swarm optimization（PSO）;time-dependent;FIFO rule

U492.3+1

A

1674-0696（2013）02-0263-04

10.3969/j.issn.1674-0696.2013.02.20

2012-06-08;

2012-11-26

國家自然科學基金項目（60974132）;重慶市教育委員會科學技術研究項目（KJ090415）

彭 勇（1973—），男，重慶人，副教授，博士，主要從事交通運輸規劃與管理方面的研究。E-mail:pengyong@cquc.edu.cn。