車(chē)輛數(shù)目未知的帶時(shí)間窗口的車(chē)輛路徑混合遺傳算法＊

曹二保 湯春華

(湖南大學(xué)經(jīng)濟(jì)與貿(mào)易學(xué)院1) 長(zhǎng)沙 410079) (湖南涉外經(jīng)濟(jì)與貿(mào)易學(xué)院商學(xué)部2) 長(zhǎng)沙 410205)

車(chē)輛路徑問(wèn)題(vehicle routing problem, VRP)由Dantzing[1]于1959年提出,屬于經(jīng)典的復(fù)雜組合優(yōu)化問(wèn)題.而VRPTW問(wèn)題是在VRP問(wèn)題的基礎(chǔ)上加上時(shí)間窗口約束,它是強(qiáng)NP難題[2],對(duì)它的求解主要集中在啟發(fā)式算法上.本文提出了一種求解VRPT W問(wèn)題的混合優(yōu)化算法,遺傳算法(genetic algorithm)[3]和鄰域搜索算法(neighborhood search)[4]是求解VRP問(wèn)題的常用方法.鄰域搜索算法求解速度快,但容易陷入局部最優(yōu)解,因而解的質(zhì)量不高;而遺傳算法具有較好的全局搜索能力,可以用極快的速度達(dá)到最優(yōu)解的90%左右,要真正達(dá)到最優(yōu)解則需要花費(fèi)很長(zhǎng)時(shí)間,同時(shí)遺傳算法的設(shè)計(jì)有時(shí)比較復(fù)雜;基于鄰域搜索的混合遺傳算法是綜合了遺傳算法和鄰域搜索算法各自優(yōu)勢(shì)的全局搜索算法,它既具有遺傳算法的全局搜索能力,又有高效的局部搜索能力,使兩種算法的優(yōu)勢(shì)得到互補(bǔ).

1 問(wèn)題描述及數(shù)學(xué)模型

帶時(shí)間窗口的車(chē)輛路徑問(wèn)題(VRPTW)的一般表述為：配送中心擁有相同容量的K輛車(chē),車(chē)的最大負(fù)荷為q,現(xiàn)有n個(gè)顧客的運(yùn)輸任務(wù)需要完成,設(shè)V={1,2,…,k},C={1,2,…,n},N= {0,1,2,…,n+1},0和n+1表示配送中心,第i個(gè)顧客的需求量為di(i=1,2,…,n)且有max di≤q,完成顧客i的任務(wù)需要的時(shí)間為T(mén),且任務(wù)i必須在時(shí)間窗口[ai,bi]內(nèi)完成.ai為任務(wù)i的最早開(kāi)始時(shí)間,bi為允許最遲開(kāi)始時(shí)間.若車(chē)輛到達(dá)顧客i的時(shí)間早于ai,則車(chē)輛需在i處等待,如果到達(dá)時(shí)間晚于bi,則任務(wù)將被延遲,每個(gè)顧客能且只能由一輛車(chē)一次完成運(yùn)送任務(wù),每輛車(chē)從配送中心出發(fā)完成運(yùn)送任務(wù)后最終都回到配送中心,最終目標(biāo)有兩個(gè)：(1)所使用的汽車(chē)數(shù)目最少;(2)所使用的汽車(chē)總的運(yùn)輸距離最短.其中：第一目標(biāo)高于第二目標(biāo),也就是說(shuō),需要更少數(shù)目車(chē)的解總比需要更多車(chē)的解要好,而不管第二目標(biāo)的值如何.這主要是由于多派一輛汽車(chē)的成本較大的緣故.tij為汽車(chē)從客戶i到客戶j的行駛時(shí)間(正比于i和j之間的歐幾里得距離dij);sik為汽車(chē)k開(kāi)始為客戶i服務(wù)的時(shí)間,令s0k=0,如果汽車(chē)k沒(méi)有為客戶i服務(wù),則sik沒(méi)有任何意義.變量 xijk=

則VRPTW的數(shù)學(xué)模型可以表示為

在上述表達(dá)式中：式(1)為使需要的汽車(chē)數(shù)目最少;式(2)為使所有的汽車(chē)走過(guò)的路程(時(shí)間)最短;式(3)為每個(gè)客戶僅能被訪問(wèn)一次;式(4)為被調(diào)用的汽車(chē)都滿足負(fù)載要求;式(5)～(7)保證每輛汽車(chē)從出發(fā)點(diǎn)出發(fā),訪問(wèn)客戶后,最終回到出發(fā)點(diǎn);式(8)為汽車(chē)k在從客戶i向客戶j行駛的過(guò)程中,在時(shí)間sik+Ti+tij之前不能到達(dá)客戶j,其中M是一個(gè)較大的標(biāo)量;式(9)為汽車(chē)為客戶i服務(wù)的開(kāi)始時(shí)間必須在其時(shí)間窗口內(nèi);式(10)為最大距離約束,dij為顧客i到顧客j的距離,L為每輛車(chē)行駛的距離上限;式(11)為整數(shù)化的約束.該模型通用性很強(qiáng),經(jīng)過(guò)參數(shù)的不同設(shè)定,可以將其轉(zhuǎn)換為其他組合優(yōu)化問(wèn)題的數(shù)學(xué)模型.例如,設(shè)定ai=0,bi=M(是一個(gè)很大的數(shù)),則可以把約束式(8)和(9)去掉,這樣VRPTW模型就變成了普通的VRP模型;如果只提供一輛汽車(chē),則該問(wèn)題就是TSP;如果有多輛汽車(chē)可利用,且附加條件t0,j=1,?j∈C和tij=0,就得到了裝箱問(wèn)題的數(shù)學(xué)模型.

2 編碼

采用比較直觀的自然數(shù)編碼,用矢量(l1,l2,…,ln)表示染色體G.其中,元素(基因)l1為[l,n]之間的一個(gè)互不重復(fù)的自然數(shù),隨機(jī)產(chǎn)生一組染色體Gh(h=1,2,…,k).其中：k為每一代種群中的個(gè)體數(shù)目,即為種群規(guī)模,Gh各不相同,它為第一代種群.首先根據(jù)經(jīng)驗(yàn)對(duì)完成配送任務(wù)可能需要的車(chē)輛數(shù)目進(jìn)行設(shè)定,設(shè)為m,對(duì)于某個(gè)個(gè)體,設(shè)其對(duì)應(yīng)的配送路徑方案的配送路徑條數(shù)與m之差為J,若配送路徑條數(shù)不超過(guò)m,則取J=0,表示該個(gè)體對(duì)應(yīng)一個(gè)可行解;然后將m的取值逐一減小,直到減小m后不能得到滿足所有約束的可行解;此時(shí)m即為最小的車(chē)輛數(shù)目;若配送路徑條數(shù)大于m,則J＞0,表示該個(gè)體對(duì)應(yīng)一個(gè)不可行解).若設(shè)定的m只有不可行解,將m的取值逐一增大,直到增大m后能得到滿足所有約束的可行解.設(shè)個(gè)體的目標(biāo)函數(shù)值為Zh,將J看成該個(gè)體對(duì)應(yīng)的配送路徑方案的不可行路徑條數(shù),并設(shè)對(duì)每條不可行路徑的懲罰權(quán)重為pw(該權(quán)重可根據(jù)目標(biāo)函數(shù)的取值范圍取一個(gè)相對(duì)較大的正數(shù)),根據(jù)式(2)可以得到該個(gè)體的目標(biāo)函數(shù)值Zh,若染色體對(duì)應(yīng)不可行解,則其適應(yīng)值函數(shù)為越大,表明Gh的性能越好,對(duì)應(yīng)的解越接近最優(yōu)解.

3 VRPTW的混合遺傳算法

3.1 遺傳操作

采用比例選擇和精華模型相結(jié)合的選擇策略.將每代種群k個(gè)染色體按 fh值排序 ,將 fh值最大的染色體復(fù)制一個(gè)直接進(jìn)入下一代.下一代種群中剩下的k-1個(gè)染色體用輪盤(pán)選擇法產(chǎn)生.這樣,可以保證最優(yōu)個(gè)體可以生存到下一代 ,既給了適應(yīng)度較大的個(gè)體較大的機(jī)會(huì)進(jìn)入下一代,又避免了個(gè)體間因適應(yīng)值不同而被選入下一代的機(jī)會(huì)懸殊.本文設(shè)計(jì)了一種新的前置交叉算子.用9個(gè)頂點(diǎn)為例說(shuō)明交叉原理：設(shè)P1={1 2 3 |4 5 6 7|8 9};P2={4 5 2|1 8 7 6 |9 3}.其中：|表示交叉點(diǎn),子個(gè)體按以下方式確定——取P2中的2個(gè)交叉點(diǎn)中間的點(diǎn)放在子代C1的開(kāi)始處,其狀態(tài)暫時(shí)為C1={1 8 7 6 X X X X X}.對(duì)未確定的位置X,在P1中找到暫時(shí)沒(méi)有在C1中出現(xiàn)的離6最近的點(diǎn)3,將3放在6的后面,從左到右將P1中未出現(xiàn)的點(diǎn)移到C1中,最后C1為{1 8 7 6 3 4 5 9

2}.前置交叉操作過(guò)程如圖1所示.

圖1 交叉操作

給定2個(gè)相同的染色體,經(jīng)過(guò)新的交叉算子仍然可以產(chǎn)生不同于父體的新個(gè)體 ,這就是說(shuō) ,由于新穎交叉算子的引入 ,當(dāng)個(gè)體都相同時(shí) ,仍然能夠進(jìn)行迭代進(jìn)化 ,繼續(xù)尋找問(wèn)題的優(yōu)化解 ,跳出了局部最優(yōu)解 ,克服了“早熟收斂”的缺點(diǎn).而以往的交叉算子 ,當(dāng)個(gè)體都相同時(shí)無(wú)法繼續(xù)迭代進(jìn)化 ,只能尋找到問(wèn)題的局部最優(yōu)解.如則經(jīng)過(guò)新的交叉算子后兩個(gè)子代為{1 8 7 6 3 4 5 2 9}.

3.2 鄰域搜索算法

本文主要考慮的鄰域結(jié)構(gòu)有 NS={Nswap,},經(jīng)過(guò)交叉操作后用作為變異操作, Nswap是隨機(jī)互換染色體中的2個(gè)基因,Ninversion隨機(jī)逆轉(zhuǎn)染色體中的基因.具體操作過(guò)程如圖2、圖3所示.

圖2 互換操作

圖3 逆轉(zhuǎn)操作

4 基于鄰域搜索的混合遺傳算法

按照前文所述的方法產(chǎn)生初始種群S,種群規(guī)模視客戶數(shù)量來(lái)確定,在進(jìn)行遺傳操作過(guò)程中,結(jié)合了約束檢驗(yàn)機(jī)制,即無(wú)論是交叉還是變異操作,每當(dāng)新的個(gè)體產(chǎn)生的時(shí)候都要檢驗(yàn)是否滿足相關(guān)約束,如最大行使時(shí)間、容量、時(shí)窗等,若滿足則保留,否則棄之.選擇操作執(zhí)行的是比例選擇和精華模型相結(jié)合的選擇策略,具體算法步驟如下.

步驟1 i=0,pi為空集.pi用來(lái)保存每代中的最好解.

步驟2 產(chǎn)生某代初始群體si.

步驟3 計(jì)算適應(yīng)度,若滿足最優(yōu)準(zhǔn)則,則轉(zhuǎn)步驟8.

步驟4 執(zhí)行選擇操作,i=i+1.

步驟5 以一定的概率進(jìn)行交叉操作和變異操作.

步驟6 產(chǎn)生當(dāng)前最好解.

步驟7 對(duì)當(dāng)前最好解進(jìn)行鄰域搜索中的逆轉(zhuǎn)操作,將改善的當(dāng)前解保存于pi中,轉(zhuǎn)步驟3.

步驟8 pi中的最優(yōu)個(gè)體即為問(wèn)題的解或近似解.

5 算例分析

有8個(gè)分店和1個(gè)配送中心,各分店的需求量為di(單位：t).服務(wù)時(shí)間Ti(單位：h)以及分店要求的服務(wù)時(shí)間范圍[ai,bi],由表 2給出.這些分店由容量為8 t的車(chē)輛完成配送 ,汽車(chē)的行駛速度設(shè)為50 km/h,配送中心與各分店間的距離(單位：km),由表1給出.要求合理安排車(chē)輛的行駛路線,使總的車(chē)輛數(shù)目和總的行使距離最短[5-7].

表1 分店間及分店與配送中心的距離

表2 任務(wù)的特征及需求

表3 運(yùn)行500次的平均計(jì)算結(jié)果

運(yùn)用Matlab語(yǔ)言對(duì)上述混合遺傳算法進(jìn)行編碼,設(shè)置遺傳算法的種群規(guī)模為40,交叉概率為0.9,變異概率為0.1,使用Pentium 4,3.06 GHz微機(jī)運(yùn)行程序,分10次實(shí)驗(yàn)得到迭代500次的算法的平均結(jié)果如表3(其中標(biāo)準(zhǔn)差為計(jì)算10次的結(jié)果),得到的最好結(jié)果如圖4所示.

運(yùn)行500次后得到的40條染色體表現(xiàn)為相同的配送方案,達(dá)到最優(yōu)解的概率為100%,最終結(jié)果為：總的路徑長(zhǎng)度為910 km,使用3輛車(chē)完成配送任務(wù),其中第一輛車(chē)的配送線路為：0-8-5-7-0,離開(kāi)配送中心時(shí)的實(shí)際裝載量為7 t,滿載率為87.5%,路徑長(zhǎng)度為405 km..第二輛車(chē)的配送線路為：0-6-4-0,離開(kāi)配送中心時(shí)的實(shí)際裝載量為7 t,滿載率為87.5%,路徑長(zhǎng)度為265 km.第三輛車(chē)的配送線路為：0-3-1-2-0,離開(kāi)配送中心時(shí)的實(shí)際裝載量為8 t,實(shí)現(xiàn)滿載,路徑長(zhǎng)度為240 km.本文的算法與其他優(yōu)化算法找到的最好結(jié)果比較如表5.

圖4 經(jīng)過(guò)500次迭代后的運(yùn)行結(jié)果

表5 本文算法與其他優(yōu)化算法的最好結(jié)果比較

此外,用本文的算法來(lái)優(yōu)化[8]中的算例,在種群規(guī)模為40,進(jìn)化300代后,無(wú)時(shí)間窗時(shí)需要的車(chē)輛數(shù)目為2,最優(yōu)路徑長(zhǎng)度為655 km,最優(yōu)行駛方案為：0-1-3-5-8-0;0-2-6-7-4-0;運(yùn)行時(shí)間為1.625 0 s,且達(dá)到最優(yōu)解的概率為100%.帶時(shí)間窗口時(shí),在種群規(guī)模為40,進(jìn)化500代后,需要的車(chē)輛數(shù)目為3,最優(yōu)路徑長(zhǎng)度為910 km,最優(yōu)行駛方案為：0-8-5-7-0;0-6-4 -0;0-3-1-2-0;且運(yùn)行時(shí)間為5.781 0 s.

由上述比較分析可知,本文的基于鄰域搜索的混合遺傳算法在求解質(zhì)量、求解速度、解的穩(wěn)定性等方面明顯優(yōu)于其他算法.

6 結(jié)束語(yǔ)

運(yùn)用本文提出的基于鄰域搜索的混合遺傳算法求解帶時(shí)間窗口的車(chē)輛路徑問(wèn)題,能使完成配送任務(wù)所需的車(chē)輛數(shù)目和總路徑長(zhǎng)度得到同時(shí)優(yōu)化,該算法既具有遺傳算法的全局搜索能力,又具有鄰域搜索算法的局部搜索能力,實(shí)驗(yàn)結(jié)果表明該算法具有很強(qiáng)的尋優(yōu)能力,具有較強(qiáng)的克服陷入局部最優(yōu)的能力,算法的求解質(zhì)量高,具有較快的收斂速度,減少問(wèn)題的約束后,該算法同樣能有效求解它們.

[1]Dantzing G,Ramser J.The truck dispatching problem[J].Management Science,1959,10(6)：80-91.

[2] Savelsbergh M.Local search for routing problem with time windows[J].Annals of Operations Research,1985,16(4)：285-305.

[3] Potvin J Y,Bengio S.The vehicle routing problem with time windows——part II：genetic search[J]. INFORMS Journal on Computing,1996,8(2)：165-172.

[4] Liu Fuhhwa,Shen Shengyuan.A route-neighborhood-based metaheuristic for vehicle routing problem with time windows[J].European Journal of Operational Research,1999,118(3)：485-504.

[5]李 軍.車(chē)輛調(diào)度問(wèn)題的分派啟發(fā)式算法[J].系統(tǒng)工程理論與實(shí)踐,1999,117(1)：27-33.

[6]李 寧,鄒 彤,孫德寶.帶時(shí)間窗車(chē)輛路徑問(wèn)題的粒子群算法[J].系統(tǒng)工程理論與實(shí)踐,2004,24(4)： 130-135.

[7]李 軍.有時(shí)間窗車(chē)輛路線安排問(wèn)題的啟發(fā)式算法[J].系統(tǒng)工程,1996,14(5)：45-50.

[8]鄒 彤,李 寧,孫德寶.不確定車(chē)輛數(shù)的有時(shí)間窗車(chē)輛路徑問(wèn)題的遺傳算法[J].系統(tǒng)工程理論與實(shí)踐, 2004,24(6)：134-138.