時變單車路徑問題建模及算法設(shè)計

彭 勇，謝祿江，劉 松

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

時變單車路徑問題建模及算法設(shè)計

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

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

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

路徑優(yōu)化;動態(tài)規(guī)劃;粒子群算法;時變;FIFO規(guī)則

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

1 時變路網(wǎng)單車路徑模型

令圖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點服務(wù)時間為tsi，當(dāng)i∈時，tsi表示在相應(yīng)需求點卸貨等消耗的時間;當(dāng)i=0時，ts0表示車輛在貨源點裝載貨物等消耗的時間。令tai為車輛到達點的時間，函數(shù)tij（tai+tsi）表示從需求點i離開到達需求點j消耗的時間，計算滿足FIFO規(guī)則［8］。R為配送路徑集合。Qmax為車輛最大裝載量。

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

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

2 基于Inver-over操作的PSO啟發(fā)式算法

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

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

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

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

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

4）如果該粒子編碼中，數(shù)i相鄰的數(shù)即為j，轉(zhuǎn)到步驟6）。

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

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

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

7）更新全局極值。

8）轉(zhuǎn)到步驟2），直至終止條件滿足。

3 貪婪補貨策略動態(tài)規(guī)劃精確求解方法

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

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

當(dāng)增加貪婪補貨策略后，可設(shè)計如下動態(tài)規(guī)劃算法（SGDP）給出問題精確解。

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

對增加補貨策略的本文模型，可給出動態(tài)規(guī)劃優(yōu)化方法如下。

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

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

令N1=N1U{j}，如果N1=，轉(zhuǎn)到 4）;否則，轉(zhuǎn)到3）。

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

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

4 數(shù)值算例

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

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

表2 客戶需求量Table 2 Customer demand

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

討論了時變單車配送路徑優(yōu)化問題，建立了以配送完成時間最早為優(yōu)化目標(biāo)的時變單車配送路徑優(yōu)化模型。由于車輛路徑問題為NP難，在行駛時間滿足FIFO規(guī)則下，設(shè)計了所給模型基于Inver-over操作的PSO啟發(fā)式算法（IOPSO）。為了驗證IOPSO算法的有效性，筆者設(shè)計了滿足貪婪配送策略下的動態(tài)規(guī)劃精確求解算法（SGDP），并討論了增加貪婪配送策略的單車配送路徑問題解與原問題解的關(guān)系。數(shù)值算例通過兩種算法優(yōu)化結(jié)果及計算時間的對比分析驗證了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］.系統(tǒng)工程理論與實踐，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的時變路網(wǎng)中車輛動態(tài)派遣的研究［J］.計算機工程與應(yīng)用，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，F(xiàn)ogel 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］高海兵，周馳，高亮.廣義粒子群優(yōu)化模型［J］.計算機學(xué)報，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

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

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