實時路網單車多任務物流配送路徑優化

彭 勇，何俊生

(重慶交通大學 交通運輸學院，重慶 400074)

末端物流是貨物送達消費者的物流活動。電子商務的繁榮帶動諸如快遞公司這樣的末端物流企業業務的快速增長，末端物流效率越來越受到重視。

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

1 單車多任務物流配送路徑模型

令dij表示節點i到節點j的直達距離。若從i到j無直達路徑，則用dij= ∞ 表示。變量yij(Ti)表示Ti時刻車輛從節點i到節點j的行駛速度。當車輛到達節點i的時刻為Ti，則此時從節點i直達節點j所用時間為dij/yij(Ti)；若從i到j無直達路徑則所用時間用∞表示。

則，數學模型如下：

目標函數，最小化配送時間如式(1)：

(1)

平衡條件，即在某次任務中車輛到達與離開某點次數相同，見式(2)：

(2)

對每個節點的配送為一次且僅為一次，見式(3)：

(3)

到達節點j的時刻與從節點i出發時刻的關系如式(4)：

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

(4)

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

(5)

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

(6)

2 單車多任務物流配送路徑模型Dijkstra-GA優化算法

VRP屬于NP-Hard問題，解決此類問題多用啟發式算法。由Holland教授提出的遺傳算法(GA)具有較強的魯棒性，廣泛應用于VRP的尋優計算中。筆者將遺傳算法與實時Dijkstra算法相結合(Dijkstra-GA)求解文中模型，遺傳算法用于路徑尋優，實時Dijkstra算法求解兩點間路網時間最短路徑[10]。

2.1 編 碼

采用自然編碼。如有6個客戶，用1～6對其編號。首先將需要配送的客戶隨機排列，如[ 1，5，6，3，4，2，0 ]，其中0為配送中心。假設最大允許配送路徑數為4，即在形成的排列中隨機插入2個節點0，假設變為[ 1，5，0，6，0，3，4，2，0 ]，因為每個回路車輛最終要回到出發點，這里可在染色體兩邊添加0，形成染色體[ 0，1，5，0，6，0，3，4，2，0，0]。該染色體解碼為車輛依次配送的3項任務：0→1→5→0； 0→6→0； 0→3→4→2→0。

2.2 適應值函數

以模型目標函數倒數作為適應值函數。

2.3 選擇操作

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

2.4 交叉變異操作

以交叉概率Pc進行交叉操作，隨機選取兩個個體某段基因互換。對于互換后形成的新個體若有沖突基因(下劃線表示)， 新個體段的沖突基因對應交換，交叉操作結束。如：

個體1：[ 0 1 |3 4 0 6 5| 2 0 ]

個體2：[ 0 5 |3 2 6 0 4| 1 0 ]

↓↓

個體1′：[ 0 1 3 2 0 6 4 2 0 ]

個體2′：[ 0 5 3 4 6 0 5 1 0 ]

↓↓

個體1″：[ 0 1 3 5 0 6 4 2 0 ]

個體2″：[ 0 2 3 4 6 0 5 1 0 ]

以變異概率Pm進行變異操作，隨機取個體兩個基因位置互換，形成新個體。

2.5 終止條件

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

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

3 算例分析

3.1 小規模運算分析

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

圖2 連續10次運算用時Fig.2 Comparsion of consuming time of 10 consecutive computations

由圖2可見，筆者提出的算法對于解決小規模運算問題可以給出滿意的優化解，并且運算用時較短。

3.2 大規模運算分析

某市某片區路網中共有139個節點，配送中心與配送節點信息如表1，各配送點需求量如表2。

表1 路網部分節點坐標

表2 各配送點需求量

圖3 路網Fig.3 Road-net

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

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

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

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

采用遺傳算法連續計算10次，求出的行駛最短時間都為1 h 50 min。其中1條配送虛擬路徑如圖6，圖中實線表示第1次配送路徑，虛線表示第2次配送路徑。即從配送中心出發，按照圖中兩條回路標號依次完成配送。

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

10次運算中的一次種群最優適應值變化過程如圖7。連續運行10次遺傳算法，用時如圖8。

圖7 種群最優適應值變化過程Fig.7 The evolutionary process of the optimal value

圖8 連續10次計算用時對比Fig.8 Comparsion of consuming time of 10 consecutive computations

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

若車輛按圖4路徑行駛，考慮高峰期擁堵對其影響，08：15發車，則配送完回到配送中心全程耗時3 h 12 min，比考慮路網時變特性優化路徑配送多耗時1 h 22 min。

4 結 語

討論了實時路網下末端物流配送問題，建立了基于實時路網的單車多任務路徑優化模型。設計了Dijkstra-GA優化求解算法。通過對比研究及更大規模算例分析，驗證了筆者所給出算法的有效性，并表明了考慮路網時變特性對末端物流配送路徑計劃的重要性。

[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] 彭勇,謝祿江,劉松.時變單車路徑問題建模及算法設計[J].重慶交通大學學報:自然科學版,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].系統工程理論與實踐,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] 王祥生,馬壽峰.實時路況信息下配送路徑的優化[J].工業工程,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] 孫國華.基于真實路網的車輛路徑問題研究[J].物流技術,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] 彭勇,劉洋.時變路網無能力約束車輛路徑優化[J].價值工程,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.