基于改進差分進化的車輛路徑優化算法

鄔開俊，王鐵君

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

2.西北民族大學 數學與計算機科學學院，蘭州 730030

基于改進差分進化的車輛路徑優化算法

鄔開俊1，王鐵君2

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

2.西北民族大學 數學與計算機科學學院，蘭州 730030

1 引言

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

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

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

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

2 VRP的數學模型

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

定義如下變量：

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

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

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

3.1 編碼方式

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

解碼方式為：

（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）的路線行駛。

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

3.2 適應度函數

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

3.3 種群的初始化

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

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

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

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

步驟4判斷List是否為空，若是，則轉步驟5；若否，則轉步驟3。

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

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

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

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值位超過車輛數，則只提取車輛數個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 改進的貪婪順序交叉

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

步驟1選切點c1、c2。

步驟2交換中間部分。

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

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

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

圖2 交叉運算示意圖

每次順序交叉會產生兩個交叉個體，而DE交叉操作中只需要一個交叉個體，為了提高收斂速度，改進算法貪婪選擇適應度更優的個體作為返回的交叉個體。

3.6 選擇操作及流程的改進

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

3.7 改進DE算法的總流程

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

步驟2貪婪初始化。

步驟3循環次數t←t+1。

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

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

步驟6執行變異操作，產生變異個體vi。

步驟7計算vi的適應度，執行選擇操作，若變異個體vi優于目標個體xi，則跳轉到步驟10；否則執行步驟8。

步驟8對xi和vi執行交叉操作，產生交叉個體ui。

步驟9計算ui的適應度，執行選擇操作。

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

步驟11若迭代次數大于最大迭代次數，則循環結束并輸出計算結果；否則跳轉到步驟3，繼續下一次迭代。

4 實驗

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

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

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

運行改進DE算法的最優個體為：（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 最優個體的解碼結果

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

圖3 最優解示意圖

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

圖4 進化過程對比

5 結束語

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

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

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

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

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

[5]王君，李波.帶模糊預約時間的車輛路徑問題的多目標禁忌搜索算法[J].計算機集成制造系統，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].北京：科學出版社，2011：107-127.

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

[10]汪定偉.智能優化方法[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

差分進化算法是一種具有記憶個體最優解和種群內部信息共享的特點的新型進化算法，本質上可看做是一種基于實數編碼的、具有保優思想的貪婪遺傳算法。針對具有NP難的車輛路徑優化問題，提出了一種改進的差分進化算法。利用貪心算法產生初始種群，定義合法化修復變異個體的方法，采用改進的順序交叉，并在變異操作之后，加入新的選擇機制。使用Matlab進行了算法的實現，實驗結果表明了改進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）；蘭州交通大學青年科學研究基金（No.2011005）。

鄔開俊（1978—），男，博士研究生，副教授，CCF會員，研究方向：智能優化算法，應急調度；王鐵君（1981—），女，博士研究生，講師，CCF會員，研究方向：智能優化算法，車輛路徑優化。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