求解軟硬時(shí)間窗共存配送路徑問題的改進(jìn)遺傳算法

史 昊，何俊生，馬 暢

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

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

1 模型

1.1 問題描述

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

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

1.2 建模

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

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

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

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

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

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

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

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

2 算法設(shè)計(jì)

2.1 編碼

采用自然編碼方式，若客戶數(shù)為6個(gè)，則隨機(jī)生成的一個(gè)染色體編碼如[ 1，4，6，3，5，2，0 ]，其中0為配送中心，其它代表客戶點(diǎn)，表示一種線路分配方案[7]。因?yàn)槊總€(gè)回路車輛最終要回到配送中心，路線首尾可添加配送中心0(下劃線表示)，編碼進(jìn)一步調(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又不能成為一條路線，則該染色體實(shí)際的解碼意義為安排1輛車和1條配送路線。

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

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

這里以目標(biāo)函數(shù)作為適應(yīng)函數(shù)，個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值即為此個(gè)體的適應(yīng)值。

2.3 選擇操作

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

2.4 改進(jìn)的交叉操作

從種群第一個(gè)染色體開始，兩兩成組，對(duì)每組染色體，在交叉概率Pc影響下，則取相鄰染色體兩端0不動(dòng)，取中間隨機(jī)一段進(jìn)行交叉互換。

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

2.5 改進(jìn)的變異操作

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

(9)

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

式(9)表明，當(dāng)ffi

3 算例分析

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

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

表2 客戶節(jié)點(diǎn)各項(xiàng)參數(shù)

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

a)遺傳算法

b)改進(jìn)的遺傳算法

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

由圖1可知，改進(jìn)算法得到的最優(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 結(jié)論

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

參考文獻(xiàn)：

[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]喬均儉，王愛茹，周靜. 帶時(shí)間窗車輛路徑問題的最優(yōu)解[J].商場(chǎng)現(xiàn)代化，2007(2)：128-129.