彭 勇，謝祿江，劉 松

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2）對(duì)選定粒子，粒子編碼中隨機(jī)選擇一個(gè)數(shù)i。

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

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

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

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

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

7）更新全局極值。

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

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

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

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

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

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

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

2）?i∈，令N2={i}，計(jì)算

3）對(duì)每一N2，?j∈N2，計(jì)算

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

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

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

4 數(shù)值算例

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

表1 需求點(diǎn)間距離Table 1 Distance between two customers

表2 客戶需求量Table 2 Customer demand

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

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

圖1 各路段速度周期變化基準(zhǔn)Fig.1 Vehicle speed benchmark

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

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

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

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

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

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

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

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

5 結(jié)語

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

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

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