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

　?。?.上海財(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í)間窗的車輛路徑問(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í)間窗車輛路徑問(wèn)題；遺傳算法；交叉算子；局部搜索；整數(shù)規(guī)劃

0引言

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

　　定義如下決策變量：

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

　　0,其他

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

　　0，其他

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

　　式(4)表示客戶i只能由一輛車為其配送服務(wù)；式(5)表示配送中心最多發(fā)出M輛車；式(6)和式(7)表示兩個(gè)變量之間的關(guān)系；式(8)確保每輛車承載的貨物總量不超過(guò)其最大容量，且不為負(fù)；式(9)初始化到達(dá)配送中心時(shí)間、開(kāi)始服務(wù)時(shí)間與持續(xù)服務(wù)時(shí)間都為0；式(10)表示車輛到達(dá)客戶i的時(shí)間先于或等于開(kāi)始服務(wù)時(shí)間，且為非負(fù)時(shí)間；式(11)表示顧客i的持續(xù)服務(wù)時(shí)間為正數(shù)；式(12)表示車輛由客戶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］最早提出的，是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。本文結(jié)合實(shí)際問(wèn)題，提出一種改進(jìn)的遺傳算法，稱之為IGALS (Improved Genetic Algorithm with Local Search)。

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

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

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

　　最后，將交叉種子精英路段替換掉目標(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所示。

　　2.2局部搜索策略

　　局部搜索算法也稱大規(guī)模鄰域搜索（Large Neighborhood Search，LNS），是一類改正型算法，它是1998年由SHAW P［6］提出的，算法的每一步迭代都是通過(guò)搜索當(dāng)前解的鄰域得到一個(gè)改進(jìn)的解。因時(shí)間窗約束，種子在迭代過(guò)程中解的質(zhì)量并不十分理想?；诖耍疚脑O(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)為車輛要配送貨物的客戶點(diǎn)，已知客戶i的時(shí)間窗［ETi，LTi］和配送中心時(shí)間窗［0,H］，車輛在vi點(diǎn)的持續(xù)服務(wù)時(shí)間STi，tij為車輛從i到j(luò)的時(shí)間，WTi為車輛在vi點(diǎn)的等待時(shí)間。

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

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

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

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

　　因車輛在配送中心無(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)移除策略

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

　?。?）重插策略

　?、賹⑦`反時(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í)間范圍較短，車輛容量較小的特點(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ī)上。車輛路由速度為單位速度，交叉概率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)。

　　算例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í)間窗的車輛路徑問(wèn)題，建立數(shù)學(xué)模型；為克服遺傳算法收斂速度慢和早熟的缺陷，設(shè)計(jì)并采用了一種段交叉算子和基于延遲時(shí)間的局部搜索策略。通過(guò)Solomon標(biāo)準(zhǔn)算例測(cè)試表明，改進(jìn)的混合遺傳算法較簡(jiǎn)單遺傳算法有較好的全局尋優(yōu)能力，驗(yàn)證了本文算法的有效性。

參考文獻(xiàn)

　?。?］ 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.

　?。?］ 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.

　?。?］ 王君.帶時(shí)間窗車輛路徑問(wèn)題的差分進(jìn)化混合算法［J］. 計(jì)算機(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.

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