改進(jìn)混合遺傳算法在MTVRPTW中的建模與優(yōu)化

宋 強(qiáng)

(廣東理工學(xué)院 信息工程系，廣東 肇慶 526100)

0 引 言

眾所周知的車輛路徑問題(vehicle routing problem，VRP)是一個(gè)NP-Hard的組合優(yōu)化問題，在一些城市配送系統(tǒng)中，貨物被送到城市配送中心(city distribution center，CDC)，然后由帶有容量限制的車輛交付給最終客戶。這些車輛可能在工作日結(jié)束之前更早地返回倉庫，然后用于另一個(gè)送貨行程。這就引入了多行程車輛路徑問題的研究思路。

在多級(jí)配送系統(tǒng)中，尤其是在城市環(huán)境下，物流卡車不能直接給客戶送貨，而是先把貨物送到CDC，在CDC有現(xiàn)貨的時(shí)間段內(nèi)再進(jìn)行最終的配送。通常情況下，考慮到城市路況的限制，只有采用電動(dòng)三輪車或者小型貨車才能執(zhí)行送貨的要求，當(dāng)貨物在客戶點(diǎn)卸載后必須立即重新裝載。同時(shí)，貨物在工作日全天都可以被送到城市配送中心，這意味著在配送周期開始時(shí)這些貨物在CDC的倉庫是沒有現(xiàn)貨的。發(fā)貨時(shí)間的概念是與每個(gè)貨物相關(guān)聯(lián)的，這里假定貨物的發(fā)貨時(shí)間在工作日開始前是已知的。

在國內(nèi)，采用遺傳算法求解帶時(shí)間窗的VRP的研究并不少見。例如，葛顯龍等[1]基于第三方帶軟時(shí)間窗約束的車輛路徑模型，設(shè)計(jì)了一種改進(jìn)遺傳算法對(duì)模型進(jìn)行求解；王永鋒等[2]根據(jù)遺傳算法容易產(chǎn)生早熟、收斂速度慢、局部尋優(yōu)能力差等缺點(diǎn)，提出了將混沌搜索技術(shù)和遺傳算法相耦合的混沌遺傳算法來求解帶時(shí)間窗的物流配送車輛路徑問題；潘立軍等[3]設(shè)計(jì)了基于時(shí)差的插入法，提出了一種求解帶時(shí)間窗的取送貨問題的遺傳算法。

而針對(duì)帶時(shí)間窗的多行程VRP，國內(nèi)研究文獻(xiàn)數(shù)量較少。例如許爭(zhēng)爭(zhēng)等[4]以車輛容量和繞行時(shí)間限制為約束參數(shù)，以面向一個(gè)城市的集中式顧客接送服務(wù)為背景，設(shè)計(jì)了一種基于協(xié)作的3階段算法來求解多行程路徑問題；宋強(qiáng)[5]為了同時(shí)解決多行程車輛路徑問題和配送中心定位問題，采用模擬退火的算法來獲得最優(yōu)路線，并改善了當(dāng)前溫度控制的位置。

建立了車輛之間在時(shí)間上相互依賴的數(shù)學(xué)模型，引入混合遺傳算法求解該問題，介紹了與貨物有關(guān)的發(fā)貨時(shí)間的概念。在相關(guān)的國外文獻(xiàn)中較少有人采用改進(jìn)的混合遺傳算法對(duì)帶時(shí)間窗的多行程車輛路徑問題(multi-trip vehicle routing problem with time windows, MTVRPTW)進(jìn)行研究，已有的研究大都采用精確算法來求解問題。

例如，N. AZI等[6]提出了一個(gè)精確算法來解決單一車輛的MTVRPTW，該解決方法開發(fā)了一個(gè)帶資源限制的初級(jí)最短路徑算法；另外N. AZI[7]還采用了一個(gè)嵌入到分枝定價(jià)算法中的列生成方法來求解MTVRPTW，由于算法的局限性，該算法只能解決客戶數(shù)量50以內(nèi)的實(shí)例；F. HERNANDEZ等[8]使用和N. AZI類似的方法，為每個(gè)問題給出一個(gè)集合覆蓋公式，每一列表示一個(gè)行程而不是一個(gè)工作日；以上這3種精確方法都使用了F. DOMINIQUE等[9]提出的用于初級(jí)最短路徑問題的算法。

除此以外，M. BATTARRA等[10]研究了MTVRPTW的擴(kuò)展問題，不同的貨物群集在一起，并且不能用相同的車輛運(yùn)輸，他們提出的方法是一個(gè)兩級(jí)順序啟發(fā)式算法：獨(dú)立地考慮每個(gè)貨物并制定一組可行的路線，然后，再把路線分配給車輛；D. CATTARUZZA等[11]采用遺傳算法來解決多行程車輛路徑問題，并采用Adsplit算法來評(píng)估染色體，引入的局部搜索算子用于對(duì)車輛重新分配行程；M. DREXL[12]介紹了車輛路徑調(diào)度在同歩性方面的問題，并引入了多行程的送貨方法。

但是以上這些啟發(fā)式算法均未能同時(shí)把時(shí)間窗、發(fā)貨時(shí)間和多行程的因素全部納入約束條件，而這3個(gè)約束條件正是筆者研究的重點(diǎn)。討論了城市環(huán)境下帶時(shí)間窗的多行程車輛路徑問題(multi-trip vehicle routing problem with time windows，MTVRPTW)，結(jié)構(gòu)如下文如述：第2節(jié)對(duì)這個(gè)問題進(jìn)行了定義；第3節(jié)提出了一種基于局部搜索的混合遺傳算法(hybrid genetic algorithm, HGA)來求解提出的MTVRPTW；第4節(jié)給出了仿真實(shí)驗(yàn)的研究結(jié)果；第5節(jié)進(jìn)行了全文總結(jié)。

1 問題的定義和相關(guān)符號(hào)

MTVRPTW可以在一個(gè)完整的無向圖G=(V,E)上進(jìn)行定義，V={0,…,N}表示頂點(diǎn)的集合，E={(i,j)|i,j∈V,i

這里給定一個(gè)時(shí)間范圍TH來定義工作日的持續(xù)時(shí)間，它可以被看作是與倉庫相關(guān)的時(shí)間窗。因而假設(shè)[E0,L0]=[0,TH]，并且D0=0。MTVRPTW需要確定一組路線并把每條路線分配給每輛車，這樣總的行駛時(shí)間就會(huì)最小并滿足下列條件:

1)每條路線都從倉庫開始和結(jié)束;

2)每個(gè)路線的開始行駛時(shí)間不早于與客戶相關(guān)的每條路線本身的最大發(fā)貨時(shí)間Ri;

3)每個(gè)客戶只能被一個(gè)路線訪問;

4)客戶i的服務(wù)從相應(yīng)的時(shí)間窗TW[Ei,Li]開始;

5)客戶的需求總和在任何路線上都不超過車載容量Q;

6)每輛車行駛完最后的路線返回倉庫的時(shí)間不遲于TH。

假定每個(gè)客戶i可以被回程車輛服務(wù)，也就是說，Ri+T0i+Ti0≤TH和Di≤Q，否則不存在可行的解決方案。

符號(hào)σ表示一條路線。大寫字母∑表示分配給一輛車的路線集合，也被稱為旅程，旅程是由不同的路線(v1,…,vn)⊕(w1,…,wm)組成，符號(hào)⊕表示路徑的連接。例如(v1,…,vn)⊕(w1,…,wm)表示兩條路徑的連接，如果v1和wm都表示倉庫的話，就會(huì)產(chǎn)生一條閉合路線。σ1⊕σ2意味著同一輛車先執(zhí)行路線σ1后執(zhí)行σ2。在路線σi上，車輛訪問客戶的時(shí)間用τσi表示，車輛離開倉庫后在路線σi上的行駛時(shí)間由Tσi表示。

符號(hào)“∈”表示“屬于”。例如σ∈∑意味著路線σ屬于旅程∑，v∈σ意味著客戶v屬于路線σ。但值得注意的是，在不考慮發(fā)貨時(shí)間時(shí)，滿足條件Tσi+1=Tσi+τσi。另一方面，在考慮到發(fā)貨時(shí)間時(shí)，應(yīng)滿足條件Tσi+1=max{Tσi+τσi,maxvi∈σi(Rvi)}。

如果車輛在Li之前到達(dá)客戶vi的位置，該路徑規(guī)劃就是可行的。

2 方 法

提出了一種改進(jìn)的混合遺傳算法 (hybrid genetic algorithm, HGA)用于求解MTVRPTW。該解決方案的主要思路可以用算法1表示。該算法是針對(duì)D. CATTARUZZA等[13]提出的基因算法解決方案的一個(gè)改進(jìn)，主要改進(jìn)之處在于選擇雙親染色體產(chǎn)生子染色體后，基因算法對(duì)子染色體進(jìn)行訓(xùn)練以達(dá)到可行的效果。而本算法是采用了局部搜索的方法對(duì)子染色體進(jìn)行改進(jìn)以組成新的種群。

算法1：改進(jìn)的混合遺傳算法

1:初始化種群

2:while不滿足終端規(guī)則do

3:選擇雙親染色體Ψ=(Ψ1,…,ΨN)和Ψ=(Ψ1,…,ΨN)

4:產(chǎn)生一個(gè)子染色體Ψ=(Ψ1,…,ΨN)

5:用LS改進(jìn)Ψ=(Ψ1,…,ΨN)

6:IfΨ=(Ψ1,…,ΨN)是不可行 then

7:修復(fù)Ψ=(Ψ1,…,ΨN)

8:end if

9:把Ψ=(Ψ1,…,ΨN)插入到種群

10：if 種群大小Ψ=(Ψ1,…,ΨN) then

11:選擇幸存者

12:end if

13:end while

首先，π隨機(jī)染色體的生成是為了創(chuàng)建一個(gè)初始種群，這些個(gè)體采用局部搜索(local search，LS)進(jìn)行了改進(jìn)。采用傳統(tǒng)的二進(jìn)制錦標(biāo)賽過程進(jìn)行選擇，通過對(duì)雙親進(jìn)行交叉選擇產(chǎn)生了下一代，修復(fù)了不可行染色體。當(dāng)種群達(dá)到π+μ維度時(shí)，按照質(zhì)量和對(duì)種群的多樣化貢獻(xiàn)相應(yīng)地消除μ個(gè)體(正如T. VIDAL等[14]提出)。在后面的內(nèi)容中提供了關(guān)于LS方法的細(xì)節(jié)，并采用輔助分割過程從一個(gè)染色體獲得MTVRPTW的解決方案。

2.1 解決方案的表示和搜索空間

一個(gè)染色體是由N個(gè)客戶節(jié)點(diǎn)組成的一個(gè)不帶行程分隔符的有序排列Ψ=(Ψ1,…,ΨN)，Ψ可以視為一個(gè)旅行商問題(traveling salesman problem，TSP)的解決方案，通過分裂染色體(插入行程分隔符和分配行程給車輛)被轉(zhuǎn)化為一個(gè)可行的MTVRPTW解決方案。從這一點(diǎn)來看，Ψ通常被稱為一個(gè)巨網(wǎng)分割結(jié)構(gòu)，即由車輛行駛路線和客戶節(jié)點(diǎn)構(gòu)成一個(gè)巨網(wǎng)，根據(jù)Ψ的分割方法來構(gòu)建不同MTVRPTW的解決方案。

在搜索階段，在適應(yīng)度函數(shù)中過載和時(shí)間窗違規(guī)都是允許的，分別通過系數(shù)λ和θ進(jìn)行懲罰。輔助分割過程用于從Ψ中獲得一個(gè)MTVRPTW解決方案ξ。下面介紹兩個(gè)符號(hào):T∑(ξ)和TW∑(ξ)分別代表在方案ξ中旅程∑所需的行駛時(shí)間和可能產(chǎn)生的時(shí)間窗違規(guī)。Lσ(ξ)的是路線σ上的載貨量，這里σ∈∑ 表示σ是旅程∑的一條路線。染色體Ψ的適應(yīng)度函數(shù)F(Ψ)通過輔助分割可以找到求解最佳解決方案的成本ξ，定義如式(1)：

(1)

在以上表達(dá)式中，如果從Ψ中通過輔助分割獲得一個(gè)可行的解決方案ξ，染色體Ψ就稱為可行。

2.2 用于帶時(shí)間窗VRP的局部搜索

局部搜索在帶時(shí)間窗的VRP面前要比在經(jīng)典VRP中變得更加復(fù)雜，不能直接在固定時(shí)間內(nèi)檢查其可行性。在本研究中，采用了T. VIDALET等[15]提出的方案(即Y. NAGATA等[16]提出的擴(kuò)展計(jì)劃)用于求解一大類帶時(shí)間窗的問題。給定一個(gè)路線ρ，數(shù)值變量T(ρ)，TW(ρ)，E(ρ)，L(ρ)，D(ρ)分別表示最小持續(xù)時(shí)間、ρ的最小時(shí)間窗違規(guī)、從允許最小持續(xù)時(shí)間和時(shí)間窗違規(guī)的路線ρ上的第一個(gè)客戶開始的最早和最晚服務(wù)時(shí)間，以及被服務(wù)客戶的累積需求。給定兩條路徑ρ1和ρ2，持有的關(guān)系如式(2)～式(6)：

T(ρ1⊕ρ2)=T(ρ1)+T(ρ2)+Tv1,v2+ΔWT

(2)

TW(ρ1⊕ρ2)=TW(ρ1)+TW(ρ2)+ΔTW

(3)

E(ρ1⊕ρ2)=max{E(ρ2)-Δ,E(ρ1)}-ΔWT

(4)

L(ρ1⊕ρ2)=min{L(ρ2)-Δ,L(ρ1)}+ΔTW

(5)

D(ρ1⊕ρ2)=D(ρ1)+D(ρ2)

(6)

其中， Δ=T(ρ1)-TW(ρ1)+Tv1,v2

ΔWT=max{E(ρ2)-Δ-L(ρ1,0)}

ΔTW=max{E(ρ1)-Δ-L(ρ2,0)}

v1表示ρ1中的最后一個(gè)客戶，v2表示ρ2中的第一個(gè)客戶。

上面定義的這些數(shù)值變量可用于在連續(xù)時(shí)間內(nèi)對(duì)典型LS進(jìn)行評(píng)估，在預(yù)處理階段可用于計(jì)算所有行駛路徑及其返程路徑。

2.3 發(fā)貨時(shí)間的介紹和多行程實(shí)例的應(yīng)用

該問題比帶時(shí)間窗的VRP(vehicle routing problem with time windows, VRPTW)多出兩個(gè)特點(diǎn)：車輛可以行駛多個(gè)行程；在整個(gè)工作時(shí)間范圍內(nèi)車輛可以完成貨物的終端配送。由于車輛將完成的行程不止一個(gè)，或者由于車輛需要等待可以運(yùn)輸?shù)呢浳?，車輛在t>0時(shí)就可以開始一個(gè)行程。T. VIDAL等[15]證明了表達(dá)式(2)～式(6)的關(guān)系，并通過關(guān)聯(lián)運(yùn)算證明了式(7)、式(8)之間的關(guān)系：

T(ρ)(t)=T(ρ)+max{0,E(ρ)-t}

(7)

TW(ρ)(t)=TW(ρ)+max{0,t-L(ρ)}

(8)

表達(dá)式(8)用來計(jì)算由于離開倉庫時(shí)間較晚而造成的時(shí)間窗違規(guī)。這里引入R(ρ)作為客戶在路線ρ上的最大發(fā)貨時(shí)間。我們定義R(vi)=Rvi并且具有下列關(guān)系：

R(ρ1⊕ρ2)=max{R(ρ1),R(ρ2)}

(9)

因而，發(fā)貨時(shí)間不會(huì)給以后介紹的路徑規(guī)劃增加任何復(fù)雜性。

下一步需要考慮的仍然是多行程方面。針對(duì)每一條路線σi，行程都是從Tσi=0開始的，通過Tσi=max{R(σi),Tσi-1+τσi-1}，可以計(jì)算時(shí)間窗違規(guī)和完成時(shí)間的變化。給定一個(gè)旅程∑=(σ1⊕…⊕σn)，式(8)用于計(jì)算∑中所有的行程，而Tσi+1可以用式(10)～式(11)計(jì)算出來：

(10)

Tσi+1=max{t,R(σi+1)}

(11)

車輛在行程σi∈∑上行駛，可采用式(7)和式(8)，在連續(xù)的時(shí)間內(nèi)對(duì)完成時(shí)間和時(shí)間窗違規(guī)的變化進(jìn)行局部計(jì)算。而完整的計(jì)算需要O(∑max)，其中∑max表示在所有旅程中的最大行程數(shù)量。

2.4 修復(fù)過程

根據(jù)不可行性的特點(diǎn)，用懲罰因子乘以10，采用局部搜索可以修復(fù)不可行的染色體。如果由此產(chǎn)生的染色體仍不可行，λ和θ就會(huì)重新乘以10并重新應(yīng)用LS。

2.5 用輔助分割算法求解MTVRPTW

2.5.1 構(gòu)建輔助圖

事實(shí)上，不保證一定存在這樣一條可行的路徑，并允許存在關(guān)于時(shí)間和負(fù)載約束的不可行解。下面用一條弧(i,j)來表示對(duì)應(yīng)的路徑成本。

(12)

在這里，路徑成本不需考慮行程的具體路線，不考慮由于車輛延遲出發(fā)造成的時(shí)間窗違規(guī)。正如在文獻(xiàn)[17]中用于求解VRP的原始過程，考慮到在H上形成最短路徑的弧提供的解決方案的成本遠(yuǎn)高于最佳方案，下面通過一個(gè)標(biāo)記過程來獲得在染色體Ψ上構(gòu)建的用圖H表示的用于MTVRPTW的解決方案。

2.5.2 分配行程給車輛

在多行程VRP(multi-trip vehicle routing problem, MTVRP)的環(huán)境下，特別是在MTVRPTW環(huán)境中，一次可以分配多個(gè)行程給同一輛車。時(shí)間窗違規(guī)完全取決于離開倉庫的時(shí)間和路線，并且不需要考慮圖H上的和弧相關(guān)的固定成本。

標(biāo)記過程可以定義如下：列舉出所有在染色體Ψ中從節(jié)點(diǎn)0到節(jié)點(diǎn)N的可能路徑，并構(gòu)建在節(jié)點(diǎn)N上具有較低成本的標(biāo)簽的最佳解決方案。從節(jié)點(diǎn)0開始，標(biāo)簽沿著圖進(jìn)行逐步擴(kuò)展。每個(gè)標(biāo)簽L都有M+3個(gè)字段域：前面的M個(gè)字段以降序存儲(chǔ)車輛行駛次數(shù)，第(M+1)個(gè)字段記錄總負(fù)載的不可行解，第(M+2)個(gè)字段存放前任節(jié)點(diǎn)，最后一個(gè)字段保存著采用表達(dá)式(1)評(píng)估的局部解決方案的成本，并作為標(biāo)簽L的成本c(L)。擴(kuò)展一個(gè)標(biāo)簽時(shí)，需要構(gòu)造M個(gè)新的標(biāo)簽，每個(gè)標(biāo)簽都用于標(biāo)記每輛車的新行程的位置。當(dāng)達(dá)到節(jié)點(diǎn)N時(shí)，選擇和節(jié)點(diǎn)N相關(guān)的帶有最低成本c(L)的標(biāo)簽L，可以形成相關(guān)的解決方案。

為了加快這個(gè)標(biāo)記過程，按照下列規(guī)則淘汰支配標(biāo)簽: 讓L1和L2成為和同一個(gè)節(jié)點(diǎn)i∈V′相關(guān)的兩個(gè)標(biāo)簽。當(dāng)且僅當(dāng)滿足下列條件時(shí)，稱為L(zhǎng)1強(qiáng)勢(shì)支配L2：

(13)

在式(13)中，c(L)是和標(biāo)簽L相關(guān)的成本，δj(L1,L2)=max{0,Tj(L1)-Tj(L2)}，其中Tj(L)是和標(biāo)簽L相關(guān)的車輛j的行駛時(shí)間。這樣，對(duì)于給定兩個(gè)標(biāo)簽L1和L2，如果擴(kuò)展L1而不以同樣方式擴(kuò)展L2的話，就會(huì)受到更多時(shí)間窗違規(guī)引起的處罰。如果不等式(13)成立，L2就不能采用比L1更好的方法進(jìn)行擴(kuò)展，那么L2就會(huì)被淘汰。

后面初步的計(jì)算實(shí)驗(yàn)顯示這個(gè)過程的時(shí)間效率比較低。為此提出了一種啟發(fā)式版本的支配規(guī)則，并引入一個(gè)參數(shù)γ≥1。當(dāng)且僅當(dāng)下列條件滿足時(shí)，稱為L(zhǎng)1弱勢(shì)支配L2：

(14)

c(L1)≤c(L2)

(15)

值得注意的是當(dāng)γ=1時(shí)，弱勢(shì)支配規(guī)則等價(jià)于強(qiáng)勢(shì)的版本。γ>1時(shí)，不等式(14)很容易滿足，可以刪除大量的標(biāo)簽。添加條件(15) 是因?yàn)楫?dāng)γ>1時(shí)，即使在條件下c(L2)

γ的值是按照與每個(gè)節(jié)點(diǎn)相關(guān)的標(biāo)簽數(shù)量進(jìn)行動(dòng)態(tài)調(diào)整的，采用式(16)表示:

(16)

這里|Li|是與節(jié)點(diǎn)i相關(guān)聯(lián)的標(biāo)簽數(shù)量，Lt是一個(gè)閾值參數(shù)，表示應(yīng)該與每個(gè)節(jié)點(diǎn)關(guān)聯(lián)的標(biāo)簽數(shù)量。應(yīng)用關(guān)系表達(dá)式(16)后，如果γ小于1，就會(huì)被置回為1，這是由于γ<1的強(qiáng)勢(shì)標(biāo)簽被保留。Lt越低，標(biāo)記過程也就越快，獲得解決方案的質(zhì)量也就越差。

3 數(shù)值實(shí)驗(yàn)

3.1 自定義實(shí)例

Li計(jì)算如下:

1)如果si<240

_Li=240 概率為 0.7;

_Li=360 概率為0.2;

_Li=480概率為0.1.

2)如果240≤si<360

_Li=360概率為0.6;

_Li=480概率為0.4；

3)否則Li=480

發(fā)貨時(shí)間Ri由下面決定:

Ri=0概率為0.5；否則Ri隨機(jī)分布在 [0,Rσ]， 其中Rσ=minj∈σ{Tσ-sj,Lj-sj}和i∈σ。

最后Ei=Ri+S0+T0i，就可以創(chuàng)建帶有若干客戶和車輛數(shù)的多個(gè)樣例。

3.2 確定Lt

為了確定Lt的值，隨機(jī)生成一個(gè)帶有60個(gè)染色體的實(shí)例，其中客戶數(shù)N=20，車輛數(shù)M=8。然后，采用帶有不同Lt值的強(qiáng)勢(shì)支配規(guī)則和弱勢(shì)支配規(guī)則分別通過輔助分割過程進(jìn)行評(píng)估，結(jié)果如表1。

可以注意到，使用強(qiáng)勢(shì)支配規(guī)則分割一個(gè)染色體平均需要超過3分鐘，這證明了引入弱勢(shì)支配規(guī)則的合理性。從表1可以看到獲得解決方案的質(zhì)量在有所下降，成本增加，但是Lt遞減的過程下降更快。

表1 支配規(guī)則的比較Table 1 Comparison of dominated rules

注：對(duì)一個(gè)M=8和N=20的樣例的60條染色體進(jìn)行輔助分割(時(shí)間單位:秒)。

3.3 仿真結(jié)果

為了驗(yàn)證本算法的有效性，在MATLAB 2013a的環(huán)境下進(jìn)行編程，并進(jìn)行了相關(guān)測(cè)試和分析。其中實(shí)驗(yàn)電腦配置為Intel Core I7/8G/Win8.1操作系統(tǒng)。構(gòu)建數(shù)學(xué)模型的相關(guān)參數(shù)指定如下。

客戶數(shù)為20；配送中心坐標(biāo)值為(20,30)，客戶坐標(biāo)值為(0,50)之間的隨機(jī)值；配送車輛總數(shù)為8，車輛載貨量為10；車輛行駛速度為60；假定每輛車可能產(chǎn)生的行程數(shù)為3， 客戶需求采用均勻分布的隨機(jī)數(shù)，范圍為1～4；客戶服務(wù)時(shí)間采用均勻分布的隨機(jī)數(shù)，范圍為5～10 min，3個(gè)時(shí)間間隔[6,9]、[12,15]和[18,21]分別用于生成3個(gè)不同行程的時(shí)間窗[Ei,Li]以及Ri的值；車輛的配置成本為200，由于遲到產(chǎn)生的違反時(shí)間窗的成本為300，單位里程的運(yùn)輸成本為30。

分別采用人工蜂群算法(artificial bee colony，ABC)[19]，雜草優(yōu)化算法(invasive weed optimization，IWO)[20]，粒子群算法(particle swarm optimization，PSO)[21]，和筆者提出的改進(jìn)混合遺傳算法(hybrid genetic algorithm，HGA)進(jìn)行了對(duì)比。其中ABC參數(shù)設(shè)置為：算法最大迭代次數(shù)800次，雇傭蜂數(shù)量100只，觀察蜂數(shù)量100只，偵查蜂步數(shù)為50，加速度系數(shù)上限為1，慣性權(quán)重阻尼比為0.99。IWO參數(shù)設(shè)置為：算法最大迭代次數(shù)800次，初始種群數(shù)目為10，最大種群數(shù)目為30，最小種子數(shù)目為2，最大種子數(shù)目為10，方差縮減指數(shù)為2，標(biāo)準(zhǔn)差初始值為0.5，標(biāo)準(zhǔn)差最終值為0.001。PSO算法參數(shù)設(shè)置為：算法最大迭代次數(shù)為800次，種群數(shù)目為100，權(quán)重為1，慣性權(quán)重阻尼比為0.99，個(gè)人學(xué)習(xí)參數(shù)為1.5，全局學(xué)習(xí)參數(shù)為2。 HGA算法參數(shù)設(shè)置為：最大迭代次數(shù)800次，種群數(shù)目50，交叉概率0.8，變異概率0.2，減速系數(shù)為1，局部搜索概率為0.4，局部搜索歩長(zhǎng)為10。

圖1～圖4為采用不同算法進(jìn)行3個(gè)行程貨物配送的優(yōu)化路線圖。

圖1 HGA算法優(yōu)化多行程路線Fig. 1 The multi-trip roadmap of HGA algorithm optimization

圖2 ABC算法優(yōu)化多行程路線Fig. 2 The multi-trip roadmap of ABC algorithm optimization

圖3 IWO算法優(yōu)化多行程路線Fig. 3 The multi-trip roadmap of IWO algorithm optimization

圖4 PSO算法優(yōu)化多行程路線Fig. 4 The multi-trip roadmap of PSO algorithm optimization

圖5 算法收斂Fig. 5 The algorithm convergence graph

各個(gè)仿真程序運(yùn)行獲得的收斂曲線如圖5。在圖5的仿真結(jié)果中，在相同的數(shù)學(xué)模型條件下，采用HGA獲得的最優(yōu)成本為33 568；采用ABC獲得的最優(yōu)成本為37 450；采用PSO獲得的最優(yōu)成本為33 950；采用IWO獲得的最優(yōu)成本為35 065。通過比較證明，這四種算法中HGA獲得的成本最低。

4 結(jié) 語

介紹了一種帶時(shí)間窗和發(fā)貨時(shí)間的多行程車輛路徑問題。這個(gè)問題特別適用于城市物流環(huán)境，即物流卡車把貨物不斷地送到城市配送中心，再由配送中心倉庫中的有容量限制的電動(dòng)三輪車等小型車輛進(jìn)行多次地配送。提出了一個(gè)基于輔助分割過程的改進(jìn)混合遺傳算法來處理這個(gè)問題，結(jié)合時(shí)間窗、發(fā)貨時(shí)間和多行程等約束條件進(jìn)行數(shù)學(xué)建模，引入了一組實(shí)例，通過和文獻(xiàn)中提出的人工蜂群算法、雜草優(yōu)化算法、粒子群算法進(jìn)行對(duì)比，仿真實(shí)驗(yàn)結(jié)果證明，該改進(jìn)的混合遺傳算法具有較高的可行性和使用效率。

同時(shí)需要說明的是，遺傳算法是尋優(yōu)的一種計(jì)算方法，多行程的路徑尋優(yōu)問題的復(fù)雜性在于網(wǎng)絡(luò)路徑交通動(dòng)態(tài)的本身，雖然考慮了路徑時(shí)間問題，但路徑的實(shí)際時(shí)間是隨著交通流等多種因素的影響而變化的，比如交通阻塞、車輛故障、緊急狀況等，如果把這些因素納入約束條件，必將導(dǎo)致動(dòng)態(tài)尋優(yōu)的過程會(huì)更加復(fù)雜，這些可以作為以后的研究?jī)?nèi)容進(jìn)一步研究。