基于改進(jìn)遺傳算法的帶時(shí)間窗車(chē)輛路徑問(wèn)題研究*

黃務(wù)蘭，張　濤

(1.上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院,上海 200433； 2.常州大學(xué) 商學(xué)院, 江蘇 常州 213164；3.上海財(cái)經(jīng)大學(xué) 上海市金融信息技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，上海 200433)

?

基于改進(jìn)遺傳算法的帶時(shí)間窗車(chē)輛路徑問(wèn)題研究*

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

(1.上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院,上海 200433； 2.常州大學(xué) 商學(xué)院, 江蘇 常州 213164；3.上海財(cái)經(jīng)大學(xué) 上海市金融信息技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，上海 200433)

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

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

引用格式：黃務(wù)蘭，張濤. 基于改進(jìn)遺傳算法的帶時(shí)間窗車(chē)輛路徑問(wèn)題研究[J].微型機(jī)與應(yīng)用，2016,35(13)：21-24.

0引言

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

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

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

定義如下決策變量：

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

(1)

(2)

因此，總目標(biāo)函數(shù)為:

Z=min(f1+f2)

(3)

并且滿足:

(4)

(5)

(6)

(7)

(8)

AT0=S0=ST0=0

(9)

0

(10)

STi>0，i=1,2,...,N

(11)

(Si+STi+tij).xijk≤ATj，i=1,2,...,N,j=1,2,...,N,i≠j

(12)

ETi≤Si≤LTii=1,2,...N

(13)

(14)

xijk∈{0,1}i,j=0,1,2,...,N;k=1,2,...,M

(15)

yik∈{0,1}i=1,2,...,N;k=1,2,...,M

(16)

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

2求解算法設(shè)計(jì)

2.1改進(jìn)的交叉算子

遺傳算法是由美國(guó)的HLLAND J H教授[5]最早提出的，是一類(lèi)借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。本文結(jié)合實(shí)際問(wèn)題，提出一種改進(jìn)的遺傳算法，稱(chēng)之為IGALS (Improved Genetic Algorithm with Local Search)。

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

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

圖1　交叉種子示例

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

圖2　交叉過(guò)程1

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

圖3　交叉過(guò)程2

圖4　交叉結(jié)果

2.2局部搜索策略

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

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

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

表1　GA與IGALS的計(jì)算性能比較

Vei和Vli的計(jì)算方法如下：

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

(17)

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

(18)

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

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

DTij=Vlj-Vei

(19)

(1)移除策略

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

(2)重插策略

①將違反時(shí)間窗和載重量的位置排除，這些位置不能插入；②設(shè)有可行線路(v0,v1,…,vi-1,vi,vi+1,…，vn,v0)，將vj點(diǎn)插入vi-1到vi之間的充要條件是:

DTi-1,i≥ti-1,j+tji-ti-1,i+STj

(20)

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

3仿真實(shí)驗(yàn)和數(shù)據(jù)分析

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

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

圖5　R101算例最優(yōu)解收斂曲線

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

4結(jié)論

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

參考文獻(xiàn)

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

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

[3] 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.

[4] 王君.帶時(shí)間窗車(chē)輛路徑問(wèn)題的差分進(jìn)化混合算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013，49(2):24-28.

[5] 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.

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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金(71171126)；教育部高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金(20130078110001)

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.19358/j.issn.1674- 7720.2016.13.007

(收稿日期：2016-03-01)

作者簡(jiǎn)介：

黃務(wù)蘭(1979-)，通信作者,女，博士生，講師，主要研究方向：智能優(yōu)化算法,物流優(yōu)化。E-mail:huangwulan@163.com。

張濤(1970-)，男，博士，教授，博導(dǎo)，主要研究方向：物流優(yōu)化，金融大數(shù)據(jù)。

Vehicle routing problem with time windows based on improved genetic algorithm

Huang Wulan1,2，Zhang Tao1,3

(1.School of Information Management and Engineering, Shanghai University of Finance and Economics,Shanghai 200433,China；2. Business School of Changzhou University, Changzhou 213164,China； 3. Key Laboratory of Financial Information Technology,Shanghai University of Finance and Economics, Shanghai 200433, China)

Abstract:This paper studied the VRPTW (Vehicle Routing Problem with Time Windows). An integer programming model is constructed, its objective is to minimize the delivery time. To further improve the convergence speed and optimization capability of the genetic algorithm, an improved genetic algorithm with local search (IGALS) is proposed, which is based on a hybrid crossover operation with elitist strategy and a local search using the thought of allowed delay time. Testing by Solomon Benchmarks instances, the results show that the proposed hybrid genetic algorithm has better performance and faster convergence speed than simple genetic algorithm.

Key words:vehicle routing problem with time windows (VRPTW); genetic algorithm; crossover operator; local search; integer programming