基于改進差分進化的車輛路徑優(yōu)化算法

鄔開俊，王鐵君

1.蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

2.西北民族大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，蘭州 730030

基于改進差分進化的車輛路徑優(yōu)化算法

鄔開俊1，王鐵君2

1.蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

2.西北民族大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，蘭州 730030

1 引言

車輛路徑問題（Vehicle Routing Problem，VRP）是指由一組車輛從一個或多個車場點出發(fā)對分布在不同地理位置的一系列顧客點進行服務(wù)，要求每個顧客點的需求必須被滿足，每個車輛的路線開始于車場點，并最終結(jié)束于車場點[1]。如圖1所示，左圖是一個有1個車場一系列顧客點的VRP的實際問題，右圖為一種動用5輛車的可行方案。優(yōu)化一般以動用車輛數(shù)盡可能少，以及所有車輛的總運行路線長度盡可能短為目標。它是組合優(yōu)化和運籌學(xué)研究領(lǐng)域的熱點問題之一，在現(xiàn)實生活中應(yīng)用廣泛，如城市垃圾收集，包裹配送，校車接送路線安排等。研究滿足生產(chǎn)經(jīng)營和運作需要的車輛路徑問題，并構(gòu)建具有高質(zhì)量和高魯棒性的問題求解算法，對于提高生產(chǎn)經(jīng)營管理水平和降低運作成本具有重要的理論意義和現(xiàn)實價值。

圖1 一個VRP實例（左）及其可行解（右）

VRP是很多實際問題求解的最終轉(zhuǎn)化形式，同時也是著名的NP難題，在短時間內(nèi)精確地求出其最優(yōu)解非常困難，尤其對于大規(guī)模問題，很難求得最優(yōu)解。近年來，遺傳、粒子群、蟻群、禁忌等算法在解決這一類問題時得到了初步的應(yīng)用[2-5]，但是在求解精度和求解效率等方面還有待于提高。

差分進化算法（Differential Evolution，DE）是一種模擬“優(yōu)勝劣汰，適者生存”的自然進化法則的仿生智能計算方法[6]。DE在解決復(fù)雜的全局優(yōu)化問題方面的性能更加優(yōu)秀，過程也更為簡單，受控參數(shù)少，被視為仿生智能計算產(chǎn)生以來在算法結(jié)構(gòu)方面取得的重大進展[7-8]。針對該算法存在收斂速度緩慢，計算量大，易早熟等問題[9]，本文提出了一種改進的差分進化算法。實驗結(jié)果表明，改進DE算法能夠高效地解決VRP問題。

2 VRP的數(shù)學(xué)模型

從圖論的角度來看，VRP可以被表示為：一個完備圖G=(V，A)，V={0，1，…，n}表示頂點集，其中0表示車場，V′={1，2，…，n}表示顧客點集，A={(i，j)|i，j∈V，i≠j}表示邊集。

定義如下變量：

式中，Z表示目標函數(shù)；Z1、Z2分別表示使用車輛數(shù)和所有車輛的總運行路線長度；k1、k2為其權(quán)值系數(shù)；ci，j是邊(i，j)的權(quán)重，表示點i到點j的旅行費用；di，j是點i到點j的空間距離；Q是車輛的最大裝載能力；needi是顧客點i的需求；m是服務(wù)車輛數(shù)；R是車輛集，R={1，2，…，m}。

約束條件中，式（4）表示每個顧客點都要服務(wù)到；式（5）表示每個頂點進出車輛數(shù)相等；式（6）表示每個顧客點只能由一輛車來服務(wù)；式（7）表示車輛不能超載，即每輛車所服務(wù)的顧客點的需求之和不能超過車輛最大裝載能力Q；式（8）表示顧客點j只能由來自其他顧客點i的車輛中的一輛來服務(wù)。

3 基于改進DE的VRP求解算法

3.1 編碼方式

編碼方式采用簡單直觀的序號編碼。顧客點序號集為{1，2，…，n}，車場序號為0，車輛數(shù)目為k。編碼結(jié)構(gòu)為：{v1,v2,…,vi,…,vn+k-1}，是由顧客點序號集{1，2，…，n}和(k-1)個0任意組合而成的。其中(k-1)個0的加入是為了區(qū)分不同車輛的行駛路線。

解碼方式為：

（1）在每條編碼的兩頭各加一個0；

（2）依次遍歷每條編碼，將編碼中被0隔開的每段非0序列保存，即為一輛車的訪問路徑。

每條編碼可解碼出1至k輛車的路徑來。

以9個顧客點，5輛車為例，編碼X=（0，1，2，3，0，0，4，5，6，0，7，8，9），解碼出：（1，2，3），（4，5，6），（7，8，9）三段非0序列，即此編碼表示：動用了3輛車，分別按照（1→2→3），（4→5→6），（7→8→9）的路線行駛。

編碼中不能出現(xiàn)負數(shù)、小數(shù)編碼和非0位位值重復(fù)等問題，即存在合法化問題。這也正是變異操作后需要進行的合法化處理的原因。

3.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)按式（1）定義：使用車輛數(shù)Z1和所有車輛的總運行路線長度Z2的加權(quán)和。權(quán)值系數(shù)k1、k2的取值根據(jù)具體情況進行設(shè)置，即若優(yōu)先考慮使用車輛數(shù)目少，則可設(shè)置k1?k2；若優(yōu)先保證車輛總行駛距離短，則可設(shè)置k1?k2。

3.3 種群的初始化

為提高初始種群的質(zhì)量，采用貪婪的初始化方法。對于初始種群的每個個體，產(chǎn)生方法如下：

步驟1初始化待服務(wù)的顧客點列表List為包含所有顧客點序號的列表，已經(jīng)服務(wù)的顧客點列表SList為空。

步驟2隨機選擇一個顧客點A作為起點，并將此點作為當前顧客點T，插入SList，并從List中移除。

步驟3從List中選擇距離顧客點T最近的顧客點作為新的當前顧客點T，將T插入SList，并從List中移除。

步驟4判斷List是否為空，若是，則轉(zhuǎn)步驟5；若否，則轉(zhuǎn)步驟3。

步驟5將(K-1)個0隨機插入SList序列中。

步驟6判斷SList是否滿足所有的約束條件，若不滿足，則跳至步驟1；若滿足，則結(jié)束。

通過以上貪婪方法初始化初始種群，直接得到局部較優(yōu)解，能夠大幅加快收斂速度。

3.4 變異及其合法化處理

將隨機選擇的個體進行直接按位相加減，而后進行合法化處理。

對于5個顧客點，2輛車的例子，隨機選擇3個個體：（1，0，2，3，0，4，5），（2，5，0，3，1，0，4），（5，3，1，0，0，4，2）。

合法化處理過程：

（1）提取編碼vi中的0并記錄其位置。如果0值位超過車輛數(shù)，則只提取車輛數(shù)個0。此時，vi=(-2，2，1，6，1，7)。

（2）將提取過0的編碼vi從小到大排序，然后使用其序號代替原編碼值。

如：vi=(-2，2，1，6，1，7)，排序后為：(-2，1，1，2，6，7)。從前到后依次：位值-2的序號為1，位值2的序號為4，依次類推進行合法化處理后的編碼為（1，4，2，5，3，6）。

（3）將步驟（1）中提取出的0重新插入編碼。此時vi=（1，4，2，5，3，0，6）。

3.5 改進的貪婪順序交叉

順序交叉可以看做是帶有不同修復(fù)程序的部分映射交叉PMX的變形，能夠較好地保留相鄰關(guān)系、先后關(guān)系[10]。改進主要是針對編碼中0值位可能出現(xiàn)重復(fù)的問題，即在去掉已有基因時，從前往后進行刪除，并且，已有基因中有幾個0則刪除幾個0。其步驟如下：

步驟1選切點c1、c2。

步驟2交換中間部分。

步驟3從第二個切點c2后，第一個基因起列出原順序，去掉已有基因（注意0的個數(shù)）。

步驟4從第二個切點c2后，第一個位置起，將獲得的無重復(fù)順序填入。

以上步驟可以用圖2來說明。

圖2 交叉運算示意圖

每次順序交叉會產(chǎn)生兩個交叉?zhèn)€體，而DE交叉操作中只需要一個交叉?zhèn)€體，為了提高收斂速度，改進算法貪婪選擇適應(yīng)度更優(yōu)的個體作為返回的交叉?zhèn)€體。

3.6 選擇操作及流程的改進

基本差分進化算法變異操作之后，直接進行交叉操作，可能導(dǎo)致變異操作產(chǎn)生的優(yōu)良基因被交叉操作所破壞。為了防止交叉操作消除或者影響變異操作產(chǎn)生的尋優(yōu)效果，改進算法在保留原有交叉操作之后的貪婪選擇機制之外，增加了變異操作之后的選擇機制，即：如果變異個體的適應(yīng)度優(yōu)于原個體，則直接跳過交叉操作，選擇變異個體進入下一代種群；否則，如果變異個體劣于原個體，按照基本差分進化算法的流程，在變異的基礎(chǔ)上進一步進行交叉操作。

3.7 改進DE算法的總流程

步驟1初始化參數(shù)。令迭代次數(shù)t=0，設(shè)置最大迭代次數(shù)，種群規(guī)模NP，放縮因子F，以及交叉常數(shù)CR。

步驟2貪婪初始化。

步驟3循環(huán)次數(shù)t←t+1。

步驟4令目標個體索引號i=1。

步驟5在目標個體xi之外隨機選擇另外3個不同的個體。

步驟6執(zhí)行變異操作，產(chǎn)生變異個體vi。

步驟7計算vi的適應(yīng)度，執(zhí)行選擇操作，若變異個體vi優(yōu)于目標個體xi，則跳轉(zhuǎn)到步驟10；否則執(zhí)行步驟8。

步驟8對xi和vi執(zhí)行交叉操作，產(chǎn)生交叉?zhèn)€體ui。

步驟9計算ui的適應(yīng)度，執(zhí)行選擇操作。

步驟10目標個體索引號i←i+1，返回步驟5直至i=NP；否則，執(zhí)行步驟11。

步驟11若迭代次數(shù)大于最大迭代次數(shù)，則循環(huán)結(jié)束并輸出計算結(jié)果；否則跳轉(zhuǎn)到步驟3，繼續(xù)下一次迭代。

4 實驗

為了證明改進DE算法的實用性和有效性，使用Matlab語言環(huán)境編程實現(xiàn)了改進算法，選用國際通用的VRP測試數(shù)據(jù)集實例：A-n32-k5.vrp（http：//www.coin-or.org/SYMPHONY/branchandcut/VRP/data/）進行求解，并與基本差分進化算法和基本蟻群算法進行了對比。測試數(shù)據(jù)集中顧客點的坐標和需求，如表1所示。

車場位置坐標(X，Y)=(82，76)，車輛總數(shù)為8輛，車輛最大載重Q=100 t。

設(shè)置改進DE算法的參數(shù)：種群規(guī)模NP為100，最大迭代次數(shù)為500，差分進化算法的交叉概率CR為0.5，放縮因子F為1，k1=1000，k2=1。

運行改進DE算法的最優(yōu)個體為：（21，31，19，17，13，7，26，0，0，0，12，1，16，30，0，27，24，0，0，29，18，8，9，22，15，10，25，5，20，0，14，28，11，4，23，3，2，6），解碼如表2所示。

表1 顧客點的坐標和需求

表2 最優(yōu)個體的解碼結(jié)果

所需車輛數(shù)為5，所有車輛路線長度之和為787.81 km，每輛車的載重均小于100 t，符合約束條件。此解也是該數(shù)據(jù)集實例目前已知的最優(yōu)解，具體路線如圖3所示。

圖3 最優(yōu)解示意圖

改進DE算法與基本蟻群算法、基本DE算法進化過程對比，如圖4所示。從圖可知，在進化前期，改進DE算法與基本蟻群算法和基本DE算法都迅速優(yōu)化，基本DE算法優(yōu)化較慢；在進化后期時，基本蟻群算法和基本DE算法收斂速度慢，而改進DE算法能夠不斷優(yōu)化，更快地在有限迭代次數(shù)里搜索到了最優(yōu)解。因此，證明了本文改進DE算法求解VRP時的良好性能。

圖4 進化過程對比

5 結(jié)束語

提出了一種將差分進化算法應(yīng)用于VRP問題的新的改進方法。實驗證明了改進的DE算法針對VRP問題的良好性能。但本文求解的標準VRP是VRP問題中約束條件最少的情況，下一步將進一步增加約束機制，改進模型，從而應(yīng)用于更為復(fù)雜的VRP問題。

[1]Dantzig G，Ramser J.The truck dispatching problem[J].Management Science，1959（6）：58-102.

[2]陳迎欣.基于改進蟻群算法的車輛路徑優(yōu)化問題研究[J].計算機應(yīng)用研究，2012，29（6）：2031-2034.

[3]王鐵君，鄔開俊.帶時間窗的多車場車輛路徑優(yōu)化的粒子群算法[J].計算機工程與應(yīng)用，2012，48（27）：27-30.

[4]蔣波.基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D].北京：北京交通大學(xué)，2010-06.

[5]王君，李波.帶模糊預(yù)約時間的車輛路徑問題的多目標禁忌搜索算法[J].計算機集成制造系統(tǒng)，2011，17（4）：858-866.

[6]Storn R，Price K.Differential evolution-a simple and efficient adaptiveschemeforglobaloptimizationovercontinuous spaces，TR-95-012[R].Berkley：International Computer Science Institute，1995.

[7]Vesterstorm J，Thomsen R.A comparative study of differential evolution，particle swarm optimization and evolutionary algorithm on numerical benchmark problem[C]//Proceedings of IEEE Congress on Evolutionary Computation，2004：1980-1987.

[8]段海濱，張祥銀，徐春芳.仿生智能計算[M].北京：科學(xué)出版社，2011：107-127.

[9]劉波，王凌，金以慧.差分進化算法研究進展[J].控制與決策，2007，22（7）：721-729.

[10]汪定偉.智能優(yōu)化方法[M].北京：高等教育出版社，2007：38-39.

WU Kaijun1,WANG Tiejun2

1.School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China
2.School of Mathematics and Computer Science Institute,Northwest University for Nationalities,Lanzhou 730030,China

As a new kind of evolutionary algorithm,Differential Evolution（DE）algorithm with the characteristics of remembering individual optimal solution and information sharing can be regarded as a real coded and excellent security greedy genetic algorithm.To solve the Vehicle Routing Problem（VRP）,which belongs to NP problems,the paper puts forward an improved differential evolution algorithm.A greedy algorithm is used to generate the initial population,legalized method is used to repair mutation,improved order crossover is used,then,after the mutation operator,a new selection mechanism is added in.The new algorithm is implemented in Matlab,the experimental results show that the improved differential evolution algorithm can efficiently solve the VRP.

Differential Evolution（DE）;Vehicle Routing Problem（VRP）;greedy algorithm;NP problem;evolutionary algorithm

差分進化算法是一種具有記憶個體最優(yōu)解和種群內(nèi)部信息共享的特點的新型進化算法，本質(zhì)上可看做是一種基于實數(shù)編碼的、具有保優(yōu)思想的貪婪遺傳算法。針對具有NP難的車輛路徑優(yōu)化問題，提出了一種改進的差分進化算法。利用貪心算法產(chǎn)生初始種群，定義合法化修復(fù)變異個體的方法，采用改進的順序交叉，并在變異操作之后，加入新的選擇機制。使用Matlab進行了算法的實現(xiàn)，實驗結(jié)果表明了改進DE算法能夠高效地解決VRP問題。

差分進化算法；車輛路徑問題；貪心算法；NP問題；進化算法

A

TP301.6

10.3778/j.issn.1002-8331.1301-0363

WU Kaijun,WANG Tiejun.Vehicle Routing Problem algorithm based on improved differential evolution.Computer Engineering and Applications,2013,49（13）：17-20.

國家社科基金（No.12CGL004）；蘭州交通大學(xué)青年科學(xué)研究基金（No.2011005）。

鄔開?。?978—），男，博士研究生，副教授，CCF會員，研究方向：智能優(yōu)化算法，應(yīng)急調(diào)度；王鐵君（1981—），女，博士研究生，講師，CCF會員，研究方向：智能優(yōu)化算法，車輛路徑優(yōu)化。E-mail：wkj@mail.lzjtu.cn

2013-02-05

2013-04-05

1002-8331（2013）13-0017-04

CNKI出版日期：2013-04-11http://www.cnki.net/kcms/detail/11.2127.TP.20130411.1555.003.html