實(shí)時(shí)路網(wǎng)單車多任務(wù)物流配送路徑優(yōu)化

彭 勇，何俊生

(重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)

末端物流是貨物送達(dá)消費(fèi)者的物流活動(dòng)。電子商務(wù)的繁榮帶動(dòng)諸如快遞公司這樣的末端物流企業(yè)業(yè)務(wù)的快速增長(zhǎng)，末端物流效率越來越受到重視。

末端物流配送路徑問題實(shí)際上是一類車輛路徑問題[1]。對(duì)于末端物流配送路徑問題，真實(shí)路網(wǎng)結(jié)構(gòu)、車輛時(shí)變及多任務(wù)特性應(yīng)該在路徑計(jì)劃中受到關(guān)注[2-10]。考慮劃區(qū)運(yùn)營(yíng)的城市快遞服務(wù)，每個(gè)劃定區(qū)域的客戶由一輛車送貨，這就形成單車路徑優(yōu)化問題[3-5,10]。文獻(xiàn)[10]討論了一類時(shí)變無能力約束車輛路徑優(yōu)化問題，建立了以配送總耗時(shí)最短為優(yōu)化目標(biāo)的無能力約束車輛路徑優(yōu)化模型。但對(duì)問題求解使用的是枚舉法，難以應(yīng)用于大規(guī)模問題的求解。筆者考慮城市末端物流配送實(shí)際，在真實(shí)路網(wǎng)結(jié)構(gòu)下，研究有一個(gè)配送中心及多個(gè)客戶，且客戶需求由一輛裝載能力有限的車輛提供送貨服務(wù)的，具有時(shí)變特性的單車多任務(wù)末端物流配送路徑優(yōu)化問題。

1 單車多任務(wù)物流配送路徑模型

令dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的直達(dá)距離。若從i到j(luò)無直達(dá)路徑，則用dij= ∞ 表示。變量yij(Ti)表示Ti時(shí)刻車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j的行駛速度。當(dāng)車輛到達(dá)節(jié)點(diǎn)i的時(shí)刻為Ti，則此時(shí)從節(jié)點(diǎn)i直達(dá)節(jié)點(diǎn)j所用時(shí)間為dij/yij(Ti)；若從i到j(luò)無直達(dá)路徑則所用時(shí)間用∞表示。

則，數(shù)學(xué)模型如下：

目標(biāo)函數(shù)，最小化配送時(shí)間如式(1)：

(1)

平衡條件，即在某次任務(wù)中車輛到達(dá)與離開某點(diǎn)次數(shù)相同，見式(2)：

(2)

對(duì)每個(gè)節(jié)點(diǎn)的配送為一次且僅為一次，見式(3)：

(3)

到達(dá)節(jié)點(diǎn)j的時(shí)刻與從節(jié)點(diǎn)i出發(fā)時(shí)刻的關(guān)系如式(4)：

Tj=Ti+tij(Ti)，ifXijr=1

(4)

確保配送回路通過配送中心，如式(5)：

(5)

每條線路上的節(jié)點(diǎn)貨物需求總量小于車輛的最大載運(yùn)量，如式(6)：

(6)

2 單車多任務(wù)物流配送路徑模型Dijkstra-GA優(yōu)化算法

VRP屬于NP-Hard問題，解決此類問題多用啟發(fā)式算法。由Holland教授提出的遺傳算法(GA)具有較強(qiáng)的魯棒性，廣泛應(yīng)用于VRP的尋優(yōu)計(jì)算中。筆者將遺傳算法與實(shí)時(shí)Dijkstra算法相結(jié)合(Dijkstra-GA)求解文中模型，遺傳算法用于路徑尋優(yōu)，實(shí)時(shí)Dijkstra算法求解兩點(diǎn)間路網(wǎng)時(shí)間最短路徑[10]。

2.1 編 碼

采用自然編碼。如有6個(gè)客戶，用1～6對(duì)其編號(hào)。首先將需要配送的客戶隨機(jī)排列，如[ 1，5，6，3，4，2，0 ]，其中0為配送中心。假設(shè)最大允許配送路徑數(shù)為4，即在形成的排列中隨機(jī)插入2個(gè)節(jié)點(diǎn)0，假設(shè)變?yōu)閇 1，5，0，6，0，3，4，2，0 ]，因?yàn)槊總€(gè)回路車輛最終要回到出發(fā)點(diǎn)，這里可在染色體兩邊添加0，形成染色體[ 0，1，5，0，6，0，3，4，2，0，0]。該染色體解碼為車輛依次配送的3項(xiàng)任務(wù)：0→1→5→0； 0→6→0； 0→3→4→2→0。

2.2 適應(yīng)值函數(shù)

以模型目標(biāo)函數(shù)倒數(shù)作為適應(yīng)值函數(shù)。

2.3 選擇操作

取種群各個(gè)體適應(yīng)值除以種群所有個(gè)體適應(yīng)值之和，作為各個(gè)體選擇概率；采用輪盤賭的方式選擇個(gè)體。

2.4 交叉變異操作

以交叉概率Pc進(jìn)行交叉操作，隨機(jī)選取兩個(gè)個(gè)體某段基因互換。對(duì)于互換后形成的新個(gè)體若有沖突基因(下劃線表示)， 新個(gè)體段的沖突基因?qū)?yīng)交換，交叉操作結(jié)束。如：

個(gè)體1：[ 0 1 |3 4 0 6 5| 2 0 ]

個(gè)體2：[ 0 5 |3 2 6 0 4| 1 0 ]

↓↓

個(gè)體1′：[ 0 1 3 2 0 6 4 2 0 ]

個(gè)體2′：[ 0 5 3 4 6 0 5 1 0 ]

↓↓

個(gè)體1″：[ 0 1 3 5 0 6 4 2 0 ]

個(gè)體2″：[ 0 2 3 4 6 0 5 1 0 ]

以變異概率Pm進(jìn)行變異操作，隨機(jī)取個(gè)體兩個(gè)基因位置互換，形成新個(gè)體。

2.5 終止條件

采用最大迭代次數(shù)為算法終止條件，算法流程見圖1。

圖1 算法流程Fig.1 The algorithm flowchart

3 算例分析

3.1 小規(guī)模運(yùn)算分析

利用本文算法對(duì)文獻(xiàn)[10]中的算例進(jìn)行分析。設(shè)置初始群體規(guī)模為40，遺傳迭代gen_max次數(shù)為100，交叉概率pc= 0.6，變異概率pm= 0.05，在CPU2.0 GHz，內(nèi)存2 GB的計(jì)算機(jī)上連續(xù)進(jìn)行10次運(yùn)算。10次運(yùn)算的最優(yōu)結(jié)果皆為1 h 33 min，路徑為6→ 4→7→3→11→12→6，與用枚舉法求得的結(jié)果[10]相同。本文算法連續(xù)10次運(yùn)算用時(shí)如圖2。

圖2 連續(xù)10次運(yùn)算用時(shí)Fig.2 Comparsion of consuming time of 10 consecutive computations

由圖2可見，筆者提出的算法對(duì)于解決小規(guī)模運(yùn)算問題可以給出滿意的優(yōu)化解，并且運(yùn)算用時(shí)較短。

3.2 大規(guī)模運(yùn)算分析

某市某片區(qū)路網(wǎng)中共有139個(gè)節(jié)點(diǎn)，配送中心與配送節(jié)點(diǎn)信息如表1，各配送點(diǎn)需求量如表2。

表1 路網(wǎng)部分節(jié)點(diǎn)坐標(biāo)

表2 各配送點(diǎn)需求量

圖3 路網(wǎng)Fig.3 Road-net

假設(shè)車輛最大載運(yùn)量取8，若不考慮路網(wǎng)時(shí)變性，每條路網(wǎng)上的行駛時(shí)間為常數(shù)，路段平均行駛速度為40 km/h，用文中算法求得的最短時(shí)間為1 h 44 min。其中1條配送虛擬路徑如圖4。圖中實(shí)線表示第1次配送路徑，虛線表示第2次配送路徑。即從配送中心出發(fā)，按照?qǐng)D中3條回路標(biāo)號(hào)依次完成配送。

圖4 不考慮時(shí)變路網(wǎng)其中1條配送虛擬路徑Fig.4 One of distribution virtual paths when time-varying of road-net is ignored

若考慮路網(wǎng)時(shí)變特性，即考慮每天早高峰與晚高峰時(shí)段，某些路段的行車速度會(huì)因擁堵而減慢。為簡(jiǎn)化計(jì)算，設(shè)路段非高峰期車速均為40 km/h，某些路段高峰期(7:30—09:00，17:00—19:00)擁堵平均車速如圖5。圖中數(shù)字表示各路段平均車速，沒有標(biāo)注的路段為40 km/h。

圖5 道路擁堵及平均速度Fig.5 Road congestion and average speed

采用遺傳算法連續(xù)計(jì)算10次，求出的行駛最短時(shí)間都為1 h 50 min。其中1條配送虛擬路徑如圖6，圖中實(shí)線表示第1次配送路徑，虛線表示第2次配送路徑。即從配送中心出發(fā)，按照?qǐng)D中兩條回路標(biāo)號(hào)依次完成配送。

圖6 考慮時(shí)變路網(wǎng)其中1條配送虛擬路徑Fig.6 One of distribution virtual paths when time-varying road-net is considered

10次運(yùn)算中的一次種群最優(yōu)適應(yīng)值變化過程如圖7。連續(xù)運(yùn)行10次遺傳算法，用時(shí)如圖8。

圖7 種群最優(yōu)適應(yīng)值變化過程Fig.7 The evolutionary process of the optimal value

圖8 連續(xù)10次計(jì)算用時(shí)對(duì)比Fig.8 Comparsion of consuming time of 10 consecutive computations

從圖8可以看出，利用遺傳算法計(jì)算用時(shí)在79～80 s之間，計(jì)算時(shí)間是可以讓人接受的，而圖7也表明配送時(shí)間隨算法尋優(yōu)過程得到了很好的縮短。

若車輛按圖4路徑行駛，考慮高峰期擁堵對(duì)其影響，08：15發(fā)車，則配送完回到配送中心全程耗時(shí)3 h 12 min，比考慮路網(wǎng)時(shí)變特性優(yōu)化路徑配送多耗時(shí)1 h 22 min。

4 結(jié) 語(yǔ)

討論了實(shí)時(shí)路網(wǎng)下末端物流配送問題，建立了基于實(shí)時(shí)路網(wǎng)的單車多任務(wù)路徑優(yōu)化模型。設(shè)計(jì)了Dijkstra-GA優(yōu)化求解算法。通過對(duì)比研究及更大規(guī)模算例分析，驗(yàn)證了筆者所給出算法的有效性，并表明了考慮路網(wǎng)時(shí)變特性對(duì)末端物流配送路徑計(jì)劃的重要性。

[1] Dantzig G,Ramser J.The truck dispatching problem [J].Management Science,1959,6(1):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] 彭勇,謝祿江,劉松.時(shí)變單車路徑問題建模及算法設(shè)計(jì)[J].重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版,2013,32(2):263-266.

Peng Yong,Xie Lujiang,Liu Song.Route modeling and algorithm designing of time-dependent single vehicle [J].Journal of Chongqing Jiaotong University:Natural Science,2013,32(2):263-266.

[4] 彭勇.變需求車輛路線問題建模及基于Inver-over操作的PSO-DP算法[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(9):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 time- dependent travel times:the impact of congestion avoidance [J].Computers & Operations Research,2012,39(5):910-918.

[8] 王祥生,馬壽峰.實(shí)時(shí)路況信息下配送路徑的優(yōu)化[J].工業(yè)工程,2008,11(1):113-116.

Wang Xiangsheng,Ma Shoufeng.Optimization of delivery routes based upon real-time traffic information [J].Industrial Engineering Journal,2008,11(1):113-116.

[9] 孫國(guó)華.基于真實(shí)路網(wǎng)的車輛路徑問題研究[J].物流技術(shù),2011,30 (1):43-45.

Sun Guohua.Solution to the real road network based vehicle routing problem [J].Logistics Technology,2011,30(1):43-45.

[10] 彭勇,劉洋.時(shí)變路網(wǎng)無能力約束車輛路徑優(yōu)化[J].價(jià)值工程,2012,31(9):114-116.

Peng Yong,Liu Yang.Uncapacitated vehicle route optimization based on time-dependent road network [J].Value Engineering,2012,31(9):114-116.