《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 業(yè)界動態(tài) > 基于改進遺傳算法的帶時間窗車輛路徑問題研究

基于改進遺傳算法的帶時間窗車輛路徑問題研究

2016-08-11
作者:黃務(wù)蘭1,2,,張濤1,3
來源:2016年微型機與應(yīng)用第13期

  黃務(wù)蘭1,2,,張濤1,3

 ?。?.上海財經(jīng)大學(xué) 信息管理與工程學(xué)院,上海 200433,; 2.常州大學(xué) 商學(xué)院, 江蘇 常州 213164;3.上海財經(jīng)大學(xué) 上海市金融信息技術(shù)研究重點實驗室,,上海 200433)

      摘要:該文以最小化配送時間為目標(biāo),,研究帶時間窗的車輛路徑問題,,建立整數(shù)規(guī)劃模型,。為了加快遺傳算法的收斂速度和尋優(yōu)能力,,提出一種改進遺法算法IGALS (Improved Genetic Algorithm with Local Search)。改進算法借用精英保留策略,,采用點交叉和段交叉算子結(jié)合的交叉算子,;提出路段允許延遲時間概念,并以此為依據(jù)使用局部搜索策略進一步提高解的質(zhì)量,。通過Solomon標(biāo)準(zhǔn)算例測試,,驗證了改進算法(IGALS)較簡單遺傳算法(GA)具有更好的全局尋優(yōu)能力和更快的收斂速度。

  關(guān)鍵詞帶時間窗車輛路徑問題,;遺傳算法,;交叉算子;局部搜索,;整數(shù)規(guī)劃

0引言

  車輛路徑問題(Vehicle Route Problem,VRP)的研究最早由DANTZIG G和RAMSER J于1959年提出[1],,近60年來始終是運籌學(xué)與組合優(yōu)化領(lǐng)域的研究熱點,,受到了國內(nèi)外研究者的廣泛關(guān)注。為了滿足實際需求,,學(xué)者對VRP問題逐步進行了擴展和變形,。其中帶時間窗車輛路徑問題(Vehicle Route Problem with Time Windows,VRPTW)是在車輛路徑問題的基礎(chǔ)上加入了時間窗約束,。加入時間窗后,,極大地增加了VRP問題計算難度和復(fù)雜度,除了考慮VRP問題空間方面的路徑之外,還必須考慮時間上的排程,,因此吸引了許多國內(nèi)外學(xué)者對其進行研究,,成為VRP問題研究領(lǐng)域最熱門的研究方向之一[24]。本文研究帶時間窗路徑優(yōu)化問題,,以最小化配送時間為目標(biāo)建立路徑優(yōu)化數(shù)學(xué)模型,,借用精英策略思想設(shè)計交叉算子提高遺傳算法的尋優(yōu)性能,并使用基于延遲時間的局部搜索策略進一步提高解的質(zhì)量,。

1問題描述和數(shù)學(xué)建模

  帶時間窗車輛路徑優(yōu)化問題描述為:某快遞配送中心擁有M輛型號相同且載重量為Q的配送車輛,,為N個已知客戶做派發(fā)快件服務(wù)。每個顧客服務(wù)位置和需求量已知,,客戶具有服務(wù)時間窗[ETi,LTi],,即最早和最遲開始服務(wù)時間,以及持續(xù)服務(wù)時間STi,,如果車輛到達客戶i的時間早于ETi,,車輛需要在客戶i處等待。現(xiàn)要求對該問題進行路徑規(guī)劃,,要求在最小化成本的前提下配送完所有客戶所花費的總時間最少,。為了能更準(zhǔn)確地表述模型,引入如下符號體系:M表示可供使用的最大車輛數(shù),;N表示客戶數(shù)目,;Q表示車輛的最大載重量;tij表示顧客i到顧客j的路由時間,; [ETi,LTi]表示節(jié)點i的時間窗,;ATi表示車輛到達節(jié)點i的時間;Si表示車輛k開始服務(wù)節(jié)點i的時間,;WTi表示車輛在客戶i處的閑置等待時間,;STi表示顧客i持續(xù)服務(wù)時間,為已知量,。

  定義如下決策變量:

  xijk=1,車輛k由客戶i駛向客戶j

  0,其他

  yik=1,客戶i的配送任務(wù)由車輛k完成

  0,,其他

  本文目標(biāo)是合理安排配送路徑,力求配送完所有客戶所花費的總時間最少,。其中,,配送時間分為三部分:車輛的路由時間,可由式(1)表述,;車輛因時間窗未開在客戶處的等待時間,,可由式(2)表述;服務(wù)客戶的時間,,因該時間是一已知量,,與決策安排無關(guān),因此不列入目標(biāo)函數(shù)中。

  JTPSN`M(_XYO2X1`X2TPGWF.png  

  式(4)表示客戶i只能由一輛車為其配送服務(wù),;式(5)表示配送中心最多發(fā)出M輛車,;式(6)和式(7)表示兩個變量之間的關(guān)系;式(8)確保每輛車承載的貨物總量不超過其最大容量,,且不為負(fù),;式(9)初始化到達配送中心時間、開始服務(wù)時間與持續(xù)服務(wù)時間都為0,;式(10)表示車輛到達客戶i的時間先于或等于開始服務(wù)時間,,且為非負(fù)時間;式(11)表示顧客i的持續(xù)服務(wù)時間為正數(shù),;式(12)表示車輛由客戶i到達客戶j的時間計算公式,,即前驅(qū)點與后繼點的時間關(guān)系;式(13)表示服務(wù)客戶i的時間應(yīng)滿足時間窗約束,;式(14)表示實際開始服務(wù)客戶i的時間計算方法,; 式(15)和式(16)分別表示變量xijk和yik的取值范圍為0或1。

2求解算法設(shè)計

  2.1改進的交叉算子

  遺傳算法是由美國的HLLAND J H教授[5]最早提出的,,是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法,。本文結(jié)合實際問題,提出一種改進的遺傳算法,,稱之為IGALS (Improved Genetic Algorithm with Local Search),。

  本文采用點交叉和段交叉結(jié)合的方式,保證遺傳算法種群的多樣性,。其中點交叉采用循環(huán)交叉方法,,段交叉方法借用精英策略的思想。它將每輛車的行駛線路劃分為一段,,對每一段線路計算目標(biāo)值,。將單個種子某趟車目標(biāo)值優(yōu)的路線保留不變,同時借鑒參與交叉的另一種子中目標(biāo)值優(yōu)的某趟車路線來替換目標(biāo)種子中目標(biāo)值劣的某車輛路段,,交換之后去掉重復(fù)節(jié)點,,這樣可以有目的地進一步優(yōu)化目標(biāo)種子的解。

  設(shè)有15個節(jié)點,,參與交叉的父代種子Pr1和Pr2,,其中每個種子按單趟車輛線路劃分為4段,種子內(nèi)部適應(yīng)值最優(yōu)車輛線路標(biāo)識為Elite1和Elite2,,最壞適應(yīng)值車輛路段分別標(biāo)識為Worse1和Worse2,,如圖1所示,。

 

001.jpg

  交叉過程中種子內(nèi)部次序調(diào)整如下,,即將最壞路段置為第一段,精英路段置為第二段,如圖2所示,。

002.jpg

  最后,,將交叉種子精英路段替換掉目標(biāo)種子最壞路段,并去掉后面重復(fù)節(jié)點,。交叉后的兩種子如圖3所示,,其中“*”號表示去掉重復(fù)種子留下的空位。去掉目標(biāo)種子的最壞路段節(jié)點,,Pr2中的11,、13節(jié)點是有待進行重新插入的節(jié)點,必要時進行重新排序的操作,,交叉后的兩種子如圖4所示,。

  

003.jpg

  2.2局部搜索策略

  局部搜索算法也稱大規(guī)模鄰域搜索(Large Neighborhood Search,LNS),,是一類改正型算法,,它是1998年由SHAW P[6]提出的,算法的每一步迭代都是通過搜索當(dāng)前解的鄰域得到一個改進的解,。因時間窗約束,,種子在迭代過程中解的質(zhì)量并不十分理想?;诖?,本文設(shè)計一種局部搜索(Local Search)策略,提出路段允許延遲時間概念,,依據(jù)該指標(biāo),,在可行線路中進行局部搜索,最大限度地減少節(jié)點等待時間,,進一步優(yōu)化遺傳算法的求解性能,,找到使目標(biāo)值更優(yōu)的解。

  設(shè)有一條可行線路Routek(v0,v1,…,vi-1,vi,vi+1,…,vn,v0),,其中v0為配送中心,, vi(i=1,2,3…n)為車輛要配送貨物的客戶點,已知客戶i的時間窗[ETi,,LTi]和配送中心時間窗[0,H],,車輛在vi點的持續(xù)服務(wù)時間STi,tij為車輛從i到j(luò)的時間,,WTi為車輛在vi點的等待時間,。

  定義每個節(jié)點的最早完成時間Vei和最遲開始時間Vli,最早完成時間Vei表示車輛完成從v0到vi配送任務(wù)的最早時間,,而最遲開始時間Vli表示車輛順利完成vi到vn各點的配送任務(wù),,應(yīng)在vi點開始作業(yè)的最晚開始時間,。

005.jpg

  Vei和Vli的計算方法如下:

  Vei=max(ETi+STi,Vei-1+ti-1,i+STi)(17)

  Vli=min(LTi,Vli+1-ti,i+1-STi)(18)

  因車輛在配送中心無配送任務(wù),ST0=0,,故Ve0=ET0=0,,Vl0=LT0=H,從Ve0=0開始依次計算Ve1,、Ve2,、…、Ven的值,。從Vl0=H開始依次計算Vln,,Vln-1,…,,Vl1的值,。

  定義:相鄰節(jié)點(vi,vj)即某一路段的允許延遲時間用DTij表示:

  DTij=Vlj-Vei(19)

  (1)移除策略

  ①移除路由時間tij比較大的客戶節(jié)點j將其從原始路線中移出,;②移除等待時間WTj較大的客戶節(jié)點j,;③移除tij+WTj值較大的客戶節(jié)點。

 ?。?)重插策略

 ?、賹⑦`反時間窗和載重量的位置排除,這些位置不能插入,;②設(shè)有可行線路(v0,v1,…,vi-1,vi,vi+1,…,,vn,v0),將vj點插入vi-1到vi之間的充要條件是:

  DTi-1,i≥ti-1,j+tji-ti-1,i+STj (20)

  很明顯,,采用該局部搜索策略會明顯降低目標(biāo)值中的等待時間,,充分發(fā)揮尋優(yōu)作用。

3仿真實驗和數(shù)據(jù)分析

  本文采用Solomon標(biāo)準(zhǔn)測試算例C1,、R1,、RC1型數(shù)據(jù)進行測試,它們具有時間范圍較短,,車輛容量較小的特點,,適合模擬本文描述問題。

  實驗采用C++語言,,在Visual Studio 2010集成開發(fā)環(huán)境中編寫,,程序運行在Win 7系統(tǒng)中的Intel Corei5,2.5 GHz主頻(6 GB內(nèi)存),,64位的Laptop機上,。車輛路由速度為單位速度,交叉概率pc=0.75,,變異概率pm=0.10,,種群規(guī)模設(shè)為100,,表1是兩種算法每個算例運行10次的結(jié)果,平均目標(biāo)值為10次取平均的結(jié)果,。可見,,29組測試數(shù)據(jù)中,,改進的混合遺法算法平均目標(biāo)值全部優(yōu)于簡單遺傳算法,最大改進率高達35.54%,。改進的混合遺傳算法使用局部搜索策略和精英交叉策略,,加快了尋優(yōu)速度,并能有效地避免算法陷入局部最優(yōu),。

 

004.jpg

  算例R101最優(yōu)結(jié)果的迭代過程如圖5所示,,橫軸代表算法迭代次數(shù),縱軸代表最優(yōu)解的值,。簡單遺傳算法在迭代20 000次左右陷入了局部最優(yōu)解,,最優(yōu)值為2 724.61,可以看出算法的最大缺陷是“早熟”,。改進的混合遺傳算法前段收斂速度較快,,其中迭代到16 000次左右遇到一個局部較優(yōu)解,目標(biāo)值為2 704.58,,但是算法很快就跳出該解,,最后求得一個更優(yōu)解,目標(biāo)值降到2 568.44,。改進的混合遺傳算法在后段能夠跳出局部最優(yōu)解,,主要是局部搜索算法進一步尋優(yōu)的結(jié)果。說明改進的混合遺傳算法能夠較好地避免“早熟”并有較快的收斂速度,。

4結(jié)論

  當(dāng)前電子商務(wù)的快速發(fā)展帶動了快遞物流業(yè)的發(fā)展,,影響快遞服務(wù)質(zhì)量的關(guān)鍵因素之一為快遞配送時效。本文以最小化快遞配送時間為目標(biāo),,研究帶時間窗的車輛路徑問題,,建立數(shù)學(xué)模型;為克服遺傳算法收斂速度慢和早熟的缺陷,,設(shè)計并采用了一種段交叉算子和基于延遲時間的局部搜索策略,。通過Solomon標(biāo)準(zhǔn)算例測試表明,改進的混合遺傳算法較簡單遺傳算法有較好的全局尋優(yōu)能力,,驗證了本文算法的有效性,。

參考文獻

  [1] DANTZIG G, RAMSER J. The truck dispatching problem[J].Management Science,1959, 6 (1): 8091.

 ?。?] SOLOMON M, DESROSIERS J.Time window constrained routing and scheduling problems: a survey[J].Transportation Science,1988,22(1):113.

 ?。?] NAZIF H, LEE L S. Optimized crossover genetic algorithm for vehicle routing problem with time windows[J].American Journal of Applied Sciences,2010,7(1):95101.

 ?。?] 王君.帶時間窗車輛路徑問題的差分進化混合算法[J]. 計算機工程與應(yīng)用, 2013,49(2):2428.

 ?。?] HOLLAND J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificialintelligence[M].Cambridge: University of Michigan Press,1975.

 ?。?] SHAW P. Using constraint programming and local search methods to solve vehicle routing problem[M]. Springer Berlin Heidelberg, 1998, 1520:417431.


本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,,并不代表本網(wǎng)站贊同其觀點,。轉(zhuǎn)載的所有的文章、圖片,、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容,、版權(quán)和其它問題,,請及時通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,,避免給雙方造成不必要的經(jīng)濟損失,。聯(lián)系電話:010-82306118;郵箱:[email protected],。