鄔開俊，王鐵君

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

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

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

鄔開俊1，王鐵君2

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

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

1 引言

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

圖1 一個(gè)VRP實(shí)例（左）及其可行解（右）

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

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

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

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

定義如下變量：

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

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

3 基于改進(jìn)DE的VRP求解算法

3.1 編碼方式

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

解碼方式為：

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

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

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

以9個(gè)顧客點(diǎn)，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序列，即此編碼表示：動(dòng)用了3輛車，分別按照（1→2→3），（4→5→6），（7→8→9）的路線行駛。

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

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

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

3.3 種群的初始化

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

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

步驟2隨機(jī)選擇一個(gè)顧客點(diǎn)A作為起點(diǎn)，并將此點(diǎn)作為當(dāng)前顧客點(diǎn)T，插入SList，并從List中移除。

步驟3從List中選擇距離顧客點(diǎn)T最近的顧客點(diǎn)作為新的當(dāng)前顧客點(diǎn)T，將T插入SList，并從List中移除。

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

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

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

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

3.4 變異及其合法化處理

將隨機(jī)選擇的個(gè)體進(jìn)行直接按位相加減，而后進(jìn)行合法化處理。

對(duì)于5個(gè)顧客點(diǎn)，2輛車的例子，隨機(jī)選擇3個(gè)個(gè)體：（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ù)個(gè)0。此時(shí)，vi=(-2，2，1，6，1，7)。

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

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

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

3.5 改進(jìn)的貪婪順序交叉

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

步驟1選切點(diǎn)c1、c2。

步驟2交換中間部分。

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

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

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

圖2 交叉運(yùn)算示意圖

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

3.6 選擇操作及流程的改進(jìn)

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

3.7 改進(jìn)DE算法的總流程

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

步驟2貪婪初始化。

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

步驟4令目標(biāo)個(gè)體索引號(hào)i=1。

步驟5在目標(biāo)個(gè)體xi之外隨機(jī)選擇另外3個(gè)不同的個(gè)體。

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

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

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

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

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

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

4 實(shí)驗(yàn)

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

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

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

運(yùn)行改進(jìn)DE算法的最優(yōu)個(gè)體為：（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 顧客點(diǎn)的坐標(biāo)和需求

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

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

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

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

圖4 進(jìn)化過程對(duì)比

5 結(jié)束語

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

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

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

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

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

[5]王君，李波.帶模糊預(yù)約時(shí)間的車輛路徑問題的多目標(biāo)禁忌搜索算法[J].計(jì)算機(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]段海濱，張祥銀，徐春芳.仿生智能計(jì)算[M].北京：科學(xué)出版社，2011：107-127.

[9]劉波，王凌，金以慧.差分進(jìn)化算法研究進(jìn)展[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

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

差分進(jìn)化算法；車輛路徑問題；貪心算法；NP問題；進(jìn)化算法

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）。

鄔開俊（1978—），男，博士研究生，副教授，CCF會(huì)員，研究方向：智能優(yōu)化算法，應(yīng)急調(diào)度；王鐵君（1981—），女，博士研究生，講師，CCF會(huì)員，研究方向：智能優(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