黃務(wù)蘭，張　濤

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

?

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

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

(1.上海財經(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ī)劃

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

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處等待?，F(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ù)時間，為已知量。

定義如下決策變量：

本文目標(biāo)是合理安排配送路徑，力求配送完所有客戶所花費的總時間最少。其中，配送時間分為三部分：車輛的路由時間，可由式(1)表述；車輛因時間窗未開在客戶處的等待時間，可由式(2)表述；服務(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只能由一輛車為其配送服務(wù)；式(5)表示配送中心最多發(fā)出M輛車；式(6)和式(7)表示兩個變量之間的關(guān)系；式(8)確保每輛車承載的貨物總量不超過其最大容量，且不為負；式(9)初始化到達配送中心時間、開始服務(wù)時間與持續(xù)服務(wù)時間都為0；式(10)表示車輛到達客戶i的時間先于或等于開始服務(wù)時間，且為非負時間；式(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所示。

圖1　交叉種子示例

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

圖2　交叉過程1

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

圖3　交叉過程2

圖4　交叉結(jié)果

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è)的最晚開始時間。

表1　GA與IGALS的計算性能比較

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é)點。

(2)重插策略

①將違反時間窗和載重量的位置排除，這些位置不能插入；②設(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é)果?？梢姡?9組測試數(shù)據(jù)中，改進的混合遺法算法平均目標(biāo)值全部優(yōu)于簡單遺傳算法，最大改進率高達35.54%。改進的混合遺傳算法使用局部搜索策略和精英交叉策略，加快了尋優(yōu)速度，并能有效地避免算法陷入局部最優(yōu)。

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

算例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.

[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] 王君.帶時間窗車輛路徑問題的差分進化混合算法[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.

*基金項目：國家自然科學(xué)基金(71171126)；教育部高等學(xué)校博士學(xué)科點專項科研基金(20130078110001)

中圖分類號：TP301.6

文獻標(biāo)識碼：A

DOI：10.19358/j.issn.1674- 7720.2016.13.007

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

作者簡介：

黃務(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