馬 歡,張建偉,趙進(jìn)超,陳 明

(1.鄭州輕工業(yè)學(xué)院軟件學(xué)院,鄭州河南450002;2.鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院,鄭州河南450002)

求解VRPSDP的變鄰域混合遺傳算法

馬 歡1,張建偉1,趙進(jìn)超2,陳 明1

(1.鄭州輕工業(yè)學(xué)院軟件學(xué)院,鄭州河南450002;2.鄭州輕工業(yè)學(xué)院計(jì)算機(jī)與通信工程學(xué)院,鄭州河南450002)

針對(duì)卸裝一體化車(chē)輛路徑問(wèn)題，提出一種結(jié)合變鄰域下降搜索和遺傳算法的混合啟發(fā)式算法(GA_VND).利用隨機(jī)生成的初始種群，通過(guò)遺傳算法的交叉變異操作生成弱可行解種群，選擇其中的最優(yōu)值作為變鄰域深度搜索的初始解.在變鄰域深度搜索的過(guò)程中通過(guò)兩種不同的局部搜索算子對(duì)解進(jìn)行局部搜索和迭代優(yōu)化.通過(guò)對(duì)54個(gè)算例的求解，仿真結(jié)果表明GA_VND更新了54個(gè)已知最好解中的8個(gè)，表明了該算法是解決卸裝一體化車(chē)輛路徑問(wèn)題的一種有效方法.

卸裝一體化;車(chē)輛路徑問(wèn)題;變鄰域下降搜索;遺傳算法;組合優(yōu)化

0 引言

卸裝一體化車(chē)輛路徑問(wèn)題(Vehicle Routing Problem with Simultaneous Delivery and Pickup, VRPSDP)普遍存在于物流運(yùn)輸中,該問(wèn)題的解決對(duì)于減少物流成本,提高物流效率具有重要意義.由于VRPSDP同VRP問(wèn)題都屬于NP難題［1］,因此目前國(guó)內(nèi)外對(duì)于VRPSDP的研究主要集中在各種元啟發(fā)式算法和混合式的啟發(fā)算法上,在元啟發(fā)式算法方面:國(guó)內(nèi)外的專(zhuān)家學(xué)者多采用遺傳算法［2］、蟻群算法［3］、粒子群算法［4］、模擬退火算法［5］等來(lái)解決這一問(wèn)題.在混合啟發(fā)式算法上,蘇孟洛等［6］提出結(jié)合粒子群算法和變鄰域下降搜索的混合粒子群算法;Y.M等［7］提出結(jié)合禁忌搜索和蟻群搜索算法的混合算法;Zachariadis等［8］提出導(dǎo)引式局部搜索和禁忌搜索相結(jié)合的混合算法.這些算法雖然都取得了一定成果,但其求解質(zhì)量仍有一定的改進(jìn)空間.

將遺傳算法和變鄰域下降算法相結(jié)合,提出一種混合啟發(fā)式算法GA_VND用于求解VRPSDP問(wèn)題.利用54個(gè)基準(zhǔn)測(cè)試算例進(jìn)行實(shí)驗(yàn),并與文獻(xiàn)［8］以及文獻(xiàn)［9］中的算法求解結(jié)果比較,驗(yàn)證本文算法的有效性.

1 問(wèn)題描述

1.1 問(wèn)題描述

定義設(shè)有向帶權(quán)圖G=(V,A,C),其中V={i｜i=0,1,…,n}是節(jié)點(diǎn)集合,節(jié)點(diǎn)0為出發(fā)地節(jié)點(diǎn),(1～n)為客戶地節(jié)點(diǎn);A={i,j｜i,j∈V}表示弧集,C={cij｜(i,j)∈A}為權(quán)重矩陣,cij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離.每個(gè)客戶節(jié)點(diǎn)i都有卸貨需求di和裝貨需求pi,運(yùn)輸車(chē)輛的最大載貨量為Q. VRPSDP則可以描述為:①每輛車(chē)都從0點(diǎn)出發(fā),服務(wù)若干客戶后返回0點(diǎn),形成一個(gè)解S;②每個(gè)客戶都僅被服務(wù)一次,而且只能由某一車(chē)輛提供服務(wù);③每個(gè)車(chē)輛的載重量都不超過(guò)Q;④所有客戶的裝卸貨需求都不超過(guò)Q;⑤總的運(yùn)輸距離f(S)最小.

1.2 解的可行性定義

對(duì)于VRPSDP的解S={rj｜j=1,2,…,k},其中rj={i｜i∈［1,n］},表示車(chē)輛j的路徑,k為解中最大的車(chē)輛數(shù).S是強(qiáng)可行解的充要條件:車(chē)輛在訪問(wèn)過(guò)rj上所有客戶后載重都不超過(guò)Q.對(duì)于解S,?ri∈S不滿足約束條件,則解S是一個(gè)弱可行解;?ri∈S不滿足約束條件,則解S是一個(gè)不可行解.

2 GA_VND算法

2.1 遺傳算法搜索全局生成強(qiáng)可行解的步驟

STEP1:最近鄰法生成遺傳算法初始強(qiáng)可行解S0.步驟為:①?gòu)奈幢贿x擇的客戶節(jié)點(diǎn)集合中選擇距離出發(fā)節(jié)點(diǎn)最近的節(jié)點(diǎn),開(kāi)始一條新路徑;②從未被選擇的客戶節(jié)點(diǎn)集合選擇距離路徑上最后一個(gè)節(jié)點(diǎn)最近的節(jié)點(diǎn);③若加人節(jié)點(diǎn)后路徑滿足強(qiáng)可行解約束條件,則返回第2步,否則返回第1步.

STEP2:將STEP1生成的強(qiáng)可行解作為父代染色體,通過(guò)交叉生成多個(gè)子代染色體,即構(gòu)造了多個(gè)可行解.步驟如下:①將該強(qiáng)可行解存人子代種群中;②從父代染色體上隨機(jī)選取客戶節(jié)點(diǎn)作為交叉節(jié)點(diǎn);③進(jìn)行染色體交叉和變異運(yùn)算生成新的染色體.隨機(jī)選擇交換和插人兩種方式進(jìn)行交叉標(biāo)點(diǎn).

上述公式需滿足i≠j,i,j∈V和i,j≠0.α= f(S0)/n,S0為STEP1生成的強(qiáng)可行解.變異操作采用貪婪倒位變異的方式:隨機(jī)選擇變異點(diǎn)i,在不包含節(jié)點(diǎn)i以及節(jié)點(diǎn)i的左右兩個(gè)節(jié)點(diǎn)i_left和i_right的集合中選擇距離節(jié)點(diǎn)i最近的節(jié)點(diǎn)j,將i_right和j之間的節(jié)點(diǎn)逆向排列.例如:解為(1, 2,3,4,5,6,7,8,9),隨機(jī)選擇節(jié)點(diǎn)4,距離節(jié)點(diǎn)4最近的節(jié)點(diǎn)為8,倒位變異解后為(1,2,3,4,8,7, 6,5,9).通過(guò)交叉和變異生成的染色體不一定滿足強(qiáng)可行解的約束條件,因此需要將其進(jìn)行轉(zhuǎn)化為強(qiáng)可行解.④判斷當(dāng)前生成的染色體總數(shù)是否到達(dá)種群上限,是則判斷新種群中是否有優(yōu)于父代染色體的子代染色體,有則選擇其中所有優(yōu)于父代染色體的子代染色體進(jìn)人STEP3,否則返回STEP2,并擴(kuò)大距離參數(shù)α.

STEP3:利用Chen J.F.［10］的方法將解集中的弱可行解轉(zhuǎn)化為強(qiáng)可行解.方法如下:掃描解中的每一個(gè)客戶節(jié)點(diǎn),如果滿足強(qiáng)可行解的約束條件,則繼續(xù)掃描,否則記錄該節(jié)點(diǎn),直到節(jié)點(diǎn)全部掃描完.掃描完成后將上次掃描中被記錄的節(jié)點(diǎn)從路徑中刪除后再按照逆序重新加人路徑,即可得到一個(gè)強(qiáng)可行解.選擇轉(zhuǎn)換后的強(qiáng)可行解集中的最優(yōu)解作為變鄰域下降搜索的初始解.

2.2 變鄰域下降搜索局部最優(yōu)解

變鄰域下降搜索將從2.1中獲得的強(qiáng)可行解作為初始解,隨機(jī)選擇一種鄰域結(jié)構(gòu)進(jìn)行局部搜索,當(dāng)?shù)竭_(dá)迭代次數(shù)上限或者連續(xù)無(wú)改進(jìn)迭代次數(shù)到達(dá)上限時(shí)結(jié)束搜索.這里選擇兩種鄰域結(jié)構(gòu):插人(insert)和2-opt.插人是將解S中的客戶i從當(dāng)前位置li移動(dòng)到另一個(gè)位置lj,從而產(chǎn)生一個(gè)新解.位置li和lj上的節(jié)點(diǎn)屬于解S中的任意路徑.2-opt是對(duì)于解S中的同一路徑上位于li和lj(li＜上的兩個(gè)客戶,將li+1位置上的節(jié)點(diǎn)與位于lj上的節(jié)點(diǎn)交換位置,并將li+1到lj之間的節(jié)點(diǎn)按逆序排列.兩種結(jié)構(gòu)如圖1所示:

圖1 鄰域結(jié)構(gòu):插入和2-optFig.1 Neighborhood structure:insert and 2-op t

兩種鄰域結(jié)構(gòu)的隨機(jī)選擇可以結(jié)合兩種鄰域不同的尋優(yōu)能力,同時(shí)也可以在一定程度上擴(kuò)展算法的搜索空間.

2.3 GA_VND算法

首先需要定義相關(guān)參數(shù):遺傳算法染色體種群數(shù)max_chom,最大迭代次數(shù)max_i,交叉概率pc,變異概率pm,GA連續(xù)無(wú)改進(jìn)迭代次數(shù)nobetter _ga_i=max_i/4,VND連續(xù)無(wú)改進(jìn)迭代次數(shù)nobetter_vnd_k=n/2.GA_VND算法偽碼如下:

1.初始化參數(shù):max_chom,max_i,pc,pm, nobetter_ga_i,nobetter_vnd_k;

2.定義變量:迭代次數(shù)i=0;GA當(dāng)前無(wú)改進(jìn)迭代次數(shù)j=0;VND當(dāng)前無(wú)改進(jìn)迭代次數(shù)k=0;

3.WHILE(i＜max_i)DO

4.按照2.1節(jié)STEP1構(gòu)造初始強(qiáng)可行解Si;

5. Sbest=Si;α=f(S0)/n;

6. WH ILE(j＜nobetter_ga_i)DO

7. S0=Sbest;//S0為VND的初始解

8.以S0為父代染色體按照2.1中的STEP2和STEP3方法生成新種群;

10.WHILE(k＜nobetter_vnd_k)DO

12. IF(f(Sk)＜f()

13. S0new=Sk;

14. k=0;

15. ELSE

16. k++;

17. End IF

20. Sbest=;

21. j=0;

22. ELSE

23. j++;

24. α=α×1.1;

25. End IF

26. End WHILE

27. i++;

28.End WHILE

29.輸出Sbest,算法結(jié)束;

3 實(shí)驗(yàn)結(jié)果及分析

3.1 測(cè)試用例

為了測(cè)試GA_VND算法的性能,主要采用兩種類(lèi)型的測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn):隨機(jī)取數(shù)的Dethloff算例［11］、Salhi和Nagy算例［12］.Dethloff算例為隨機(jī)生成的40個(gè)問(wèn)題規(guī)模均為50的算例.根據(jù)客戶分布和車(chē)輛需求可以分為SCA3x,SCA8x, CON3x,CON8x.其中SCA算例為［0,100］間均勻分布,CON算例為［0,200］間非均勻分布.各客戶點(diǎn)的卸貨需求d為在［0,100］間取隨機(jī)值,裝貨需求p為(k+0.5)*d,其中k在［0,1］間取隨機(jī)值.Salhi和Nagy算例的問(wèn)題規(guī)模在［50,199］之間,每個(gè)問(wèn)題包含兩個(gè)算例,其中CMTxX為在原CMTx算例基礎(chǔ)上增加了裝卸貨需求的算例［10］, CMTxY為和CMTxX裝卸貨需求相反的算例.

GA_VND算法采用c#在.net平臺(tái)下實(shí)現(xiàn),運(yùn)行環(huán)境為WIN7 64x,CPU為Intel core i5-2520M 2.5 GHz,內(nèi)存為6G,參數(shù)設(shè)置為max_chom= 100;max_i=200;pc=0.5;pm=0.05;nobetter_ga _i=50;Dethloff算例中nobetter_vnd_k=25.Salhi和Nagy算例中nobetter_vnd_k=n/2,CMTxX和CMTxY的問(wèn)題規(guī)模相同,分別為(50,75,100, 120,150,199).

3.2 算法的可行性分析

以Dethloff算例中的SCA3-0算例為例,設(shè)定最大迭代次數(shù)為200,對(duì)GA_VND算法和VND算法每次迭代求得的當(dāng)前最優(yōu)解進(jìn)行比較,重復(fù)運(yùn)行10次取平均值,結(jié)果如圖2所示.

圖2 SCA 3-0算例上每次迭代最優(yōu)解的平均值比較Fig.2 Comparison of the optimal solution's average value by every iterated based on SCA3-0examples

可以看出GA_VND算法中由GA算法求得的初始可行解的存在,使得GA_VND算法可以從一個(gè)較優(yōu)的初始解開(kāi)始搜索.陷人局部最優(yōu)時(shí)擴(kuò)展GA交叉范圍的機(jī)制和VND僅變換鄰域相比, GA_VND算法可通過(guò)變化初始解來(lái)重新求解,跳出當(dāng)前局部最優(yōu),避免了VND算法隨機(jī)初始解求解的局限性.

3.3 Dethloff算例上的最優(yōu)解比較

為了驗(yàn)證GA_VND算法的有效性,這里將遺傳算法、Zachariadis提出的禁忌搜索和Guided Local Search的混合算法TS_GLS［8］、GA_VND算法應(yīng)用于Dethloff算例進(jìn)行計(jì)算.表1描述了在Dethloff算例上GA求得的最優(yōu)解、TS_GLS求得的最優(yōu)解和GA_VND運(yùn)行10次取平均值的比較,其中,L為最優(yōu)路徑長(zhǎng)度,t為計(jì)算消耗時(shí)間,單位為s.

表1 Dethloff算例上的結(jié)果比較Tab.1 Comparison of the solutions based on Dethloff

續(xù)表1

通過(guò)對(duì)表1的4組40個(gè)測(cè)試算例進(jìn)行計(jì)算,其中的已知最好解用粗體標(biāo)出.通過(guò)遺傳算法的和GA_VND算法的結(jié)果比較可以看出:混合算法GA_VND的求解質(zhì)量明顯高于遺傳算法的,通過(guò)TS_GLS算法和GA_VND算法的結(jié)果比較可以看出GA_VND算法更新了Dethloff算例中的SCA3 -0、SCA8-1和SCA8-7在TS_GLS中的已知最好解,說(shuō)明GA_VND算法是可行有效的.

3.4 Salhi和Nagy算例上的最優(yōu)解比較

為了進(jìn)一步驗(yàn)證GA_VND算法的有效性,采用在Salhi和Nagy算例上將GA_VND算法運(yùn)行10次取平均值和TS_GLS算法以及C.Yu提出的AIS算法［9］兩種算法求得的最優(yōu)解進(jìn)行對(duì)比,結(jié)果如表2所示.

通過(guò)TS_GLS算法和GA_VND算法以及AIS算法計(jì)算的最優(yōu)解結(jié)果相比較,可以看出:在平均路徑長(zhǎng)度方面,GA_VND算法較TS_GLS算法減少了0.46,較AIS算法減少了18.73;在最優(yōu)解的質(zhì)量上,GA_VND算法較TS_GLS算法最大提高了2.55%,最小提高了0.65%.較AIS算法最大提高了5.35%,最小提高了0.27%,進(jìn)一步說(shuō)明了GA_VND算法是可行有效的.

表2 Salhi和Nagy算例上的結(jié)果比較Tab.2 Comparison of the solutions based on Salhi and Nagy

4 結(jié)論

卸裝一體化車(chē)輛路徑問(wèn)題是一個(gè)有著實(shí)際應(yīng)用需要且廣泛存在的問(wèn)題,針對(duì)這一問(wèn)題設(shè)計(jì)了一種結(jié)合遺傳算法和變鄰域下降搜索的混合啟發(fā)式算法,將遺傳算法的全局搜索能力和變鄰域下降搜索算法的局部搜索能力相結(jié)合,有效地提高了求解質(zhì)量.通過(guò)對(duì)Dethloff算例和Salhi和Nagy算例共54個(gè)算例的求解,驗(yàn)證了GA_VND算法優(yōu)于單一的遺傳算法,且更新了54個(gè)算例中的8個(gè)當(dāng)前最優(yōu)解,表明了本文算法的有效性.

［1］ 葉春明,王科峰,李永林.同時(shí)送取貨車(chē)輛路徑問(wèn)題算法研究綜述［J］.計(jì)算機(jī)應(yīng)用研究,2013,30 (2):334-340.

［2］ 龍磊,陳秋雙,華彥寧,等.具有同時(shí)集送貨需求的車(chē)輛路徑問(wèn)題的粗粒度并行遺傳算法［J］.系統(tǒng)仿真學(xué)報(bào),2009,21(7):1962-1968.

［3］ GAJPAL Y,ABAD P.An ant colony system(ACS) for vehicle routing problem with simultaneous deliveryand pickup［J］.Computers&Operations Research, 2009,36(12):3215-3223.

［4］ 吳斌,蔡紅,樊樹(shù)海,等.雙倍體差分進(jìn)化粒子群算法在VRPSDP中的應(yīng)用研究［J］.系統(tǒng)工程理論與實(shí)踐,2010,30(3):520-526.

［5］ 王超,穆東.物料配送和廢舊產(chǎn)品回收的VRPSDP問(wèn)題的并行模擬退火算法［J］.北京交通大學(xué)學(xué)報(bào),2014,38(6):19-26.

［6］ 蘇孟洛,楊宏安,孫啟峰.求解卸裝一體化的車(chē)輛路徑問(wèn)題的混合粒子群算法［J］.中國(guó)制造業(yè)信息化:學(xué)術(shù)版,2012,41(9):52-56.

［7］ YOUSEFIKHOSHBAKHT M,DIDEHVAR F,RAHMATI F.A combination of modified tabu search and elite ant system to solve the vehicle routing problem with simultaneous pickup and delivery［J］.Journal of Industrial and Production Engineering,2014,31(2): 65-75.

［8］ ZACHARIADISE E,TARANTILIS C D,KIRANOUDIS C T.A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service［J］.Expert Systems with app lications, 2009,36(2):1070-1081.

［9］ YU C,LAU H Y K.AIS-based A lgorithm for Solving Vehicle Routing Problem with Simultaneous Pick-up and Delivery(VRP-SPD)［J］.Journal of Traffic and Logistics Engineering,2013,1(2):174-178

［10］CHEN JF,WU T H.Vehicle routing problem with simultaneous deliveries and pickups［J］.Journal of the Operational Research Society,2006,57(5):579-587.

［11］DETHLOFF J.Vehic le routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up［J］.OR-Spektrum,2001,23(1): 79-96.

［12］SALH IS,NAGY G.A cluster insertion heuristic for single and multip le depot vehicle routing problemswith backhauling［J］.Journal of the Operational Research Society,1999,50(10):1034-1042.

AHybrid Genetic and Variable Neighborhood Descent Algorithm for Vehicle Rou ting Problem with Simultaneous Delivery and Pickup

MA Huan1,ZHANG Jian-wei,ZHAO Jin-chao2,CHEN M ing1
(1.Software Engineering College,Zhengzhou University of Light Industry,Zhengzhou 450002,China;2.School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

This paper proposes a hybrid heuristic algorithm combing variable neighborhood descent search with genetic algorithm(GA_VND)to solve vehicle routing problem with simultaneous delivery and pickup.By the use of the initial populations generated random ly,the weak feasible solutions are produced by the crossover and mutation operators of genetic algorithm.And then,the best of them was selected as initial solution of variable neighborhood descent algorithm.Finally,in the process of the variable neighborhood descent search,two different neighborhood structures are used to search the locally optimal solution.The simulation results show that GA_VND can update 8 better solutions in the 54 best known solutions,which illustrates that GA_VND is an effective method for vehicle routing problem with simultaneous delivery and pickup.

vehicle routing problem;simultaneous delivery and pickup;variable neighborhood descent;genetic algorithm;NP-hard

TP301

A

10.3969/j.issn.1671-6833.2015.03.026

1671-6833(2015)03-0120-05

2015-01-19;

2015-03-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(61403349);國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201310462018)

馬歡(1981-),男,河南孟州人,鄭州輕工業(yè)學(xué)院講師,主要研究方向?yàn)樾畔⑻幚?智能與信息系統(tǒng),E-mail:mahuanresearch@126.com.