求解軟硬時間窗共存配送路徑問題的改進遺傳算法

史 昊，何俊生，馬 暢

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

現(xiàn)實中的配送客戶往往會提出期望的收貨時間區(qū)間，要求配送車輛在這期間到達。按對送達時間要求的嚴格程度不同，時間窗分為軟時間窗和硬時間窗。近年來，有關軟時間窗或帶硬時間窗的軟時間窗車輛路徑問題的研究較多[1]，但對節(jié)點時間窗軟硬不同且同時存在的情況的車輛路徑問題的研究還比較少，而這種情況在現(xiàn)實的配送問題中時常出現(xiàn)。本文給出一種改進的遺傳算法，對軟硬時間窗共存配送路徑問題進行求解，并與基本的遺傳算法計算效果進行對比。

1 模型

1.1 問題描述

車輛從某固定的配送中心出發(fā)，給已知的配送服務節(jié)點進行配送。每個節(jié)點都要求一個已知固定配送服務時間窗。假設每個客戶節(jié)點只由一輛車進行服務，且足以滿足該節(jié)點對進貨量的需求。所有節(jié)點(包括配送中心和客戶節(jié)點)間距、每個配送點的需求量和服務時間、車輛的載重量及最大允許的行駛距離都為已知。在車輛配送過程中還要受到以下基本約束〔2-3〕：①車輛不允許超載；②車輛有最大行程限制；③時間窗限制。

本文研究在所有約束條件都滿足的情況下，如何確定配送的路線方案，使目標成本最小。

1.2 建模

根據(jù)上述對問題的描述，做如下假設〔4-6〕：設配送中心共有n個服務節(jié)點，i,j表示節(jié)點的編號(i,j=1,2,3,…，n)，配送中心編號為0；每個節(jié)點的需求量為Pi，單車的最大裝載量為p； 節(jié)點之間的距離dij，節(jié)點的服務時間為Ti；單車的單位行駛距離成本為c1，單車出車成本為c0；所用車輛數(shù)(路徑數(shù))為K，單車最大行駛距離為D；i節(jié)點時間窗為(ETi,ELi)，且ELi-ETi>Ti，若為軟時間窗，懲罰函數(shù)為

cfi=eimax{ETi-tik,0,tik-(ELi-Ti)}，

式中cfi為軟時間窗的懲罰函數(shù)在i點的值；tik為k車到達i節(jié)點的時間；ei為懲罰系數(shù)。

若為硬時間窗，懲罰函數(shù)則為

cfi′=max{ei′(ETi-tik),0,M[tik-(ELi-Ti)]}，

式中cfi′為硬時間窗的懲罰函數(shù)在i點的值；ei′為等待期間的懲罰系數(shù)；M為晚于硬時間窗的懲罰系數(shù)，為一個很大的正數(shù)。

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

ei≥0,ei′≥0,,i=1,2,3,…，n.

(8)

目標函數(shù)(1)分為3部分，分別為：①車輛未在時間窗要求時間段到達的懲罰值；②車輛行駛成本；③車輛的出車成本。約束條件中，式(2)表示每條線路上的節(jié)點貨物需求總量小于車輛的最大載貨量；式(3)表示車輛的運行距離不能超過允許的最大行駛距離；式(4)、(5)表示每輛車出發(fā)到各節(jié)點服務后，離開并最終回到起始的配送中心；式(6)、(7)表示每個配送節(jié)點有且只有一輛車通過；式(8)表示遲到或早到懲罰系數(shù)為一個非負數(shù)。

2 算法設計

2.1 編碼

采用自然編碼方式，若客戶數(shù)為6個，則隨機生成的一個染色體編碼如[ 1，4，6，3，5，2，0 ]，其中0為配送中心，其它代表客戶點，表示一種線路分配方案[7]。因為每個回路車輛最終要回到配送中心，路線首尾可添加配送中心0(下劃線表示)，編碼進一步調(diào)整為：[ 0，1，4，6，3，5，2，0，0 ]。所以這種方案的配送需要2輛車，2條配送回路為：0→1→4→6→3→5→2→0；0→0。但0→0又不能成為一條路線，則該染色體實際的解碼意義為安排1輛車和1條配送路線。

根據(jù)上述解釋，假設問題中可用最多車輛數(shù)K=4，即最多使用4輛車分4條線路進行配送。則可以在形成的排列中隨機插K-2入個配送中心點0，比如：[0，1，4，0，6，0，3，5，2，0，0 ]。該染色體的解碼后實際含義就為：僅派發(fā)3輛車， 3條配送回路分別為：0→1→4→0； 0→6→0； 0→3→5→2→0。

2.2 適應函數(shù)

這里以目標函數(shù)作為適應函數(shù)，個體對應的目標函數(shù)值即為此個體的適應值。

2.3 選擇操作

采用輪盤賭的方式選擇染色體復制到新種群，直到新種群規(guī)模與父代相同為止。

2.4 改進的交叉操作

從種群第一個染色體開始，兩兩成組，對每組染色體，在交叉概率Pc影響下，則取相鄰染色體兩端0不動，取中間隨機一段進行交叉互換。

式中k1，k2，k3分別為0～1的小數(shù)。

2.5 改進的變異操作

變異操作是對種群每一個染色體，在變異概率pm，隨機取染色體2個數(shù)字并交換位置，形成新染色體。變異概率pm為

(9)

式中k4,k5為0～1的小數(shù)。

式(9)表明，當ffi

3 算例分析

C市某醫(yī)藥物流配送中心，擔任所轄區(qū)域內(nèi)14個客戶的配送業(yè)務，各個客戶的間距見表1，時間窗、懲罰系數(shù)等參數(shù)見表2。其中需要的配送車輛數(shù)待求，車輛的最大載荷為25，單車最大行駛距離為300，固定單車發(fā)車成本為150，單位運輸成本為1。其它已知參數(shù)見表1、表2。

表1 各配送節(jié)點的間距(0為配送中心)

表2 客戶節(jié)點各項參數(shù)

在CPU主頻為2.0 GHz，內(nèi)存2 GB的計算機上，分別采用基本遺傳算法、改進遺傳算法計算10次。算法中設置初始群體規(guī)模為40，M取10 000，遺傳迭代次數(shù)genmax=1 000，基本遺傳算法中交叉概率pc=0.6，變異概率pm=0.05；改進算法中k1，k2，k3，k4分別取0.01，0.05，0.1，0.1，0.01。兩種方法計算最優(yōu)成本分別為1 322.2和1 301.4，最優(yōu)迭代過程見圖1。

a)遺傳算法

b)改進的遺傳算法

圖1 兩種算法最優(yōu)解的迭代變化過程對比

由圖1可知，改進算法得到的最優(yōu)解更優(yōu)，迭代效率也更高。最終得到最優(yōu)解為：[0 3 2 0 1 8 7 0 6 11 10 14 0 4 5 13 12 9 0 ]。即最優(yōu)方案為：配送中心安排4輛車，配送線路分別為：0→3→2→0； 0→1→8→7→0； 0→6→11→10→14→0； 0→4→5→13→12→9→0。

4 結論

探討了一種求解軟硬時間窗共存下配送路徑問題的改進遺傳算法，建立了配送路徑優(yōu)化模型，設計了改進的交叉、變異準則，并用數(shù)值算例計算結果與基本遺傳算法比較，結果證明本設計改進遺傳算法的有效性，且比基本遺傳算法更容易避免陷入局部最優(yōu)解，迭代次數(shù)更少。

參考文獻：

[1] éric Taillard, Philippe Badeau, Michel Gendreau, et al. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows[J]. Transportation Science, 1997, 31:170-186.

[2]George Ioannou, Manolis Kritikos, Gregory Prastacos. A Problem Generator-Solver Heuristic for Vehicle Routing with Soft-Time Windows[J]. Omega，2003, 31(1): 41-53.

[3]Sun Guohua.Research on Open Vehicle Routing Problem with Full Load and Soft-Time Windows[J].Computer Engineering and Applications, 2011, 47(17):13-17.

[4]Jixian Xiao, Bing Lu.Vehicle Routing Problem with Soft Time Windows[J].Advances in Intelligent and Soft Computing, 2012, 168: 317-322.

[5]Z Fu, R Eglese , Y O Li. A Unified Tabu Search Algorithm for Vehicle Routing Problems with Soft Time Windows[J].Journal of the Operational Research Society, 2008 (59): 663-673.

[6]Brian Kallehauge. Formulations and Exact Algorithms for the Vehicle Routing Problem with Time Windows[J].Computers & Operations Research,2008, 35(7): 2307-2330.

[7]Tsung-sheng Chang, Yat-wah Wan, Wei Tsang OOI. A Stochastic Dynamic Traveling Salesman Problem with Hard Time Windows[J].European Journal of Operational Research, 2009, 198(3): 748-759.

[8]Hongtao Lei, Gilbert Laporte, Bo Guo. The Capacitated Vehicle Routing Problem with Stochastic Demands and Time Windows[J].Computers & Operations Research, 2011, 38(12): 1775-1783.

[9]J C Bean. Genetic Algorithms and Random Keys for Sequencing and Optimization[J].ORSA Journal on Computing, 1994, 6 (2): 154-160.

[10]喬均儉，王愛茹，周靜. 帶時間窗車輛路徑問題的最優(yōu)解[J].商場現(xiàn)代化，2007(2)：128-129.