馬 歡,張建偉,趙進超,陳 明

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

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

馬 歡1,張建偉1,趙進超2,陳 明1

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

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

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

0 引言

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

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

1 問題描述

1.1 問題描述

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

1.2 解的可行性定義

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

2 GA_VND算法

2.1 遺傳算法搜索全局生成強可行解的步驟

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

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

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

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

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

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

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

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

2.3 GA_VND算法

首先需要定義相關參數(shù):遺傳算法染色體種群數(shù)max_chom,最大迭代次數(shù)max_i,交叉概率pc,變異概率pm,GA連續(xù)無改進迭代次數(shù)nobetter _ga_i=max_i/4,VND連續(xù)無改進迭代次數(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當前無改進迭代次數(shù)j=0;VND當前無改進迭代次數(shù)k=0;

3.WHILE(i＜max_i)DO

4.按照2.1節(jié)STEP1構(gòu)造初始強可行解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 實驗結(jié)果及分析

3.1 測試用例

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

GA_VND算法采用c#在.net平臺下實現(xiàn),運行環(huán)境為WIN7 64x,CPU為Intel core i5-2520M 2.5 GHz,內(nèi)存為6G,參數(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的問題規(guī)模相同,分別為(50,75,100, 120,150,199).

3.2 算法的可行性分析

以Dethloff算例中的SCA3-0算例為例,設定最大迭代次數(shù)為200,對GA_VND算法和VND算法每次迭代求得的當前最優(yōu)解進行比較,重復運行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算法可以從一個較優(yōu)的初始解開始搜索.陷人局部最優(yōu)時擴展GA交叉范圍的機制和VND僅變換鄰域相比, GA_VND算法可通過變化初始解來重新求解,跳出當前局部最優(yōu),避免了VND算法隨機初始解求解的局限性.

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

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

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

續(xù)表1

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

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

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

通過TS_GLS算法和GA_VND算法以及AIS算法計算的最優(yōu)解結(jié)果相比較,可以看出:在平均路徑長度方面,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%,進一步說明了GA_VND算法是可行有效的.

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

4 結(jié)論

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

［1］ 葉春明,王科峰,李永林.同時送取貨車輛路徑問題算法研究綜述［J］.計算機應用研究,2013,30 (2):334-340.

［2］ 龍磊,陳秋雙,華彥寧,等.具有同時集送貨需求的車輛路徑問題的粗粒度并行遺傳算法［J］.系統(tǒng)仿真學報,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］ 吳斌,蔡紅,樊樹海,等.雙倍體差分進化粒子群算法在VRPSDP中的應用研究［J］.系統(tǒng)工程理論與實踐,2010,30(3):520-526.

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

［6］ 蘇孟洛,楊宏安,孫啟峰.求解卸裝一體化的車輛路徑問題的混合粒子群算法［J］.中國制造業(yè)信息化:學術版,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

國家自然科學基金資助項目(61403349);國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(201310462018)

馬歡(1981-),男,河南孟州人,鄭州輕工業(yè)學院講師,主要研究方向為信息處理,智能與信息系統(tǒng),E-mail:mahuanresearch@126.com.