基于改進(jìn)遺傳算法的車輛路徑問題

甘 寶，薛玉璽，魏文萍

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

基于改進(jìn)遺傳算法的車輛路徑問題

甘 寶，薛玉璽，魏文萍

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070）

為了研究物流中心的服務(wù)效率和車輛的合理調(diào)度方案，以汽車載重量作為影響車輛路線安排的主要因素，以經(jīng)典的車載容量約束條件下的車輛路徑問題為原型建立數(shù)學(xué)模型，通過求解該數(shù)學(xué)模型的最優(yōu)解來獲得車輛最優(yōu)路徑。由初始狀態(tài)隨機(jī)生成的可行解作為初始的車輛路徑方案，通過改進(jìn)的遺傳算法不斷地調(diào)整染色體的交叉和變異概率進(jìn)行優(yōu)化，最終得到物流中心車輛安排的合理方案。通過多次求解算例，都能夠得到滿意的車輛路徑方案，不僅驗(yàn)證了該數(shù)學(xué)模型的有效性和實(shí)踐性，而且也驗(yàn)證了改進(jìn)后遺傳算法的收斂性和魯棒性，同時(shí)得到了改進(jìn)遺傳算法交叉和變異概率的調(diào)整范圍。該模型和算法不僅可以提高物流中心的服務(wù)效率，而且可以為物流中心的車輛調(diào)度方案提供支持和幫助。

物流配送；車輛路徑問題；遺傳算法；交叉算子；收斂性

0 引言

當(dāng)代物流業(yè)在電子商務(wù)的推動下蓬勃發(fā)展，客戶對貨物配送的要求也越來越高。就配送中心而言，要考慮如何降低配送費(fèi)用、縮短配送時(shí)間以及提高配送效率和服務(wù)水平等。要實(shí)現(xiàn)這些目標(biāo)，車輛路徑安排（又稱車輛路徑問題，Vehicle Routing Problem，簡稱VRP）是關(guān)鍵所在。該問題由Dantzig和Ramse[1]于1959年首先提出，其一般定義為：對一系列裝、卸點(diǎn)，合理組織行車路線，使車輛有序地通過它們，在滿足一定的約束條件（如：貨物需求量、車輛容量限制、行駛里程限制、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如：費(fèi)用最少、時(shí)間最短、用車數(shù)最少等）。車輛路徑問題是一個(gè)NP（Non-Deterministic Polynomi?al，非確定性多項(xiàng)式）完全問題[2]，只有在節(jié)點(diǎn)較少時(shí)能夠求得精確解。因此，關(guān)于車輛路徑問題的各種算法的研究成為熱點(diǎn)，尤其是啟發(fā)式算法，如由Clarke和Wright[3]提出的節(jié)約法、Gillett和Miller[4]提出的掃描法、Fisher和Jaikumar[5]建立的一般分配算法以及Pureza和Franca[6]研究的Tabu搜索算法等。這些算法[7]用以求解車輛路徑問題時(shí)都很有效，但也有各自的局限：如節(jié)約法按節(jié)約量從大到小構(gòu)造路徑，具有運(yùn)算速度快的優(yōu)點(diǎn)，但存在未組合點(diǎn)零亂、邊緣點(diǎn)難于組合的問題；而掃描法卻不是漸進(jìn)優(yōu)化算法[7]。如何針對車輛路徑問題的特點(diǎn)，構(gòu)造運(yùn)算簡單、尋優(yōu)性能優(yōu)異的啟發(fā)式算法，不僅對于配送系統(tǒng)而且對于許多可轉(zhuǎn)化為車輛路徑問題的優(yōu)化組合問題具有十分重要的意義。

遺傳算法（Genetic Algorithm，簡稱GA）是John H.Holland[8]根據(jù)生物進(jìn)化模型提出的一種優(yōu)化算法。它是一種以自然選擇和遺傳理論為基礎(chǔ)，將生物進(jìn)化過程中適者生存的規(guī)則與種群中染色體的隨機(jī)信息變化機(jī)制相結(jié)合的全局尋優(yōu)搜索算法[8]。遺傳算法通過構(gòu)造特征問題的解，形成初始種群，然后通過反復(fù)的選擇、交叉、變異算子的作用進(jìn)行迭代，求得問題的滿意解或最優(yōu)解。該算法具有隱含并行操作機(jī)制，針對編碼而非針對問題本身進(jìn)行操作，尋優(yōu)規(guī)則由概率決定，快速收斂等特點(diǎn)，因此發(fā)展很快，在很多領(lǐng)域有著廣泛的應(yīng)用[9]。為此，本文在GA基礎(chǔ)上構(gòu)造初始可行解，并設(shè)計(jì)算法來求解車輛路徑問題。

1 VRP數(shù)學(xué)模型

假定配送中心用K輛車對N個(gè)需求點(diǎn)進(jìn)行配送，每輛車的載重量均為C，每個(gè)需求點(diǎn)的需求量為Di(i=1,2,…,n)，需求點(diǎn)i到需求點(diǎn)j的距離為dij，配送中心的編號為0。

此外，還包括以下約束和假設(shè)：

（1）所有客戶只能被1輛車訪問，并且只能被訪問1次；

（2）所有車輛必須由配送中心出發(fā)并最終回到配送中心；

（3）所有車輛必須滿足容量限制，不可超載；

（4）假設(shè)車型相同，容量相同；

（5）假設(shè)配送中心唯一。

為建模方便，再引入2個(gè)決策變量：和。其中，當(dāng)車輛k由客戶i到客戶j時(shí)，取，否則；當(dāng)車輛k訪問客戶i時(shí)，取，否則。

由此，建立車輛路徑問題的數(shù)學(xué)模型如下：

在模型中，式（1）為目標(biāo)函數(shù)，要求配送完所有需求點(diǎn)的總路徑最短；式（2）保證每輛車僅訪問1個(gè)需求點(diǎn)；式（3）保證每個(gè)需求點(diǎn)僅被1輛車訪問；式（4）表示共有K輛車從配送中心出發(fā)；式（5）為容量約束。

2 VRP的遺傳算法

遺傳算法是一種基于生物自然選擇和基因遺傳學(xué)原理的優(yōu)化搜索方法。自然選擇學(xué)說是進(jìn)化論的核心思想，根據(jù)進(jìn)化論，生物的發(fā)展進(jìn)化主要有三個(gè)原因：遺傳、變異和選擇[10]。

遺傳是指子代總是與親代具有相似性，通過遺傳，親代將自身的某些特質(zhì)、性狀遺傳給后代，被稱為生物進(jìn)化的基礎(chǔ)。變異是指子代和親代出現(xiàn)不相似的現(xiàn)象，即子代永遠(yuǎn)不會和親代一模一樣。它是生物個(gè)體之間相互區(qū)別的基礎(chǔ)。變異為生物進(jìn)化和發(fā)展創(chuàng)造了條件。選擇是指生物群體所具有的精選能力，決定著生物進(jìn)化方向[11]。自然選擇是指生物在自然界的生存環(huán)境中適者生存，不適者被淘汰的現(xiàn)象。生物就是在遺傳、變異和選擇三種因素的綜合作用下，不斷適應(yīng)環(huán)境、進(jìn)化和發(fā)展的。

進(jìn)化論的自然選擇過程蘊(yùn)含著一種搜索和優(yōu)化的先進(jìn)思想。遺傳算法正是吸取了生物系統(tǒng)“適者生存，優(yōu)勝劣汰”的進(jìn)化原理，從而使它能夠提供一個(gè)在復(fù)雜空間里進(jìn)行的“魯棒性”搜索算法。

2.1 算法編碼

針對車輛路徑問題解的特點(diǎn)，本文采用占焱發(fā)[12]提出的自然數(shù)編碼方式進(jìn)行染色體編碼，即一條染色體便是一個(gè)配送方案，染色體長度為N+K+1，n為客戶數(shù)量，K為車輛數(shù)，其編碼形式如下：，其中的一條子路徑用表示，含義是：第k輛車從配送中心出發(fā)，配送完相應(yīng)的需求點(diǎn)后返回配送中心；0代表配送中心；表示第k輛車訪問的第i個(gè)客戶。

2.2 初始種群的產(chǎn)生

隨機(jī)產(chǎn)生互不相同的N個(gè)數(shù)（范圍為1～N），在這組數(shù)的前后兩端各加一個(gè)0，然后從第1個(gè)0元素之后開始，計(jì)算需求點(diǎn)對應(yīng)的累計(jì)需求量，如果，則在第i個(gè)需求點(diǎn)之后加入0元素，至此前兩個(gè)0元素之間的需求點(diǎn)由車輛1來配送；以此類推，直到加入第K個(gè)0元素為止；第K個(gè)0元素與末端的0元素之間的需求點(diǎn)由第K輛車來配送。這樣做可以保證所產(chǎn)生的初始解滿足車輛的容量約束、每個(gè)需求點(diǎn)只能被1輛車訪問以及每輛車只能訪問1個(gè)需求點(diǎn)的約束條件。重復(fù)上述步驟n次，就可以產(chǎn)生n個(gè)初始可行解。本文為保證種群的多樣性和快速求解，取n=500，即產(chǎn)生500個(gè)初始種群。

2.3 適應(yīng)值函數(shù)

適應(yīng)值函數(shù)是評價(jià)每個(gè)染色體優(yōu)劣的函數(shù)，一般與問題的目標(biāo)函數(shù)有密切關(guān)系，染色體的適應(yīng)值函數(shù)（簡稱適值）是染色體優(yōu)劣的量化指標(biāo)。VRP的目標(biāo)是使車輛的總里程最短，其目標(biāo)函數(shù)如式（6）所示，本文將其目標(biāo)函數(shù)直接作為適應(yīng)值函數(shù)。

式中：f為適應(yīng)值函數(shù)；表示第i輛車由需求點(diǎn)j到k的行駛距離（為簡單起見，這里采用兩點(diǎn)之間的直線距離），對于不滿足容量約束的染色體由于不能求得其目標(biāo)函數(shù)，所以令其適應(yīng)值為一個(gè)很大的正整數(shù)，即f=max。

2.4 評價(jià)函數(shù)與種群選擇

評價(jià)函數(shù)（記為Eval(V)）是遺傳過程中優(yōu)勝劣汰的基本依據(jù)[10]。利用評價(jià)函數(shù)選擇染色體的一般原則是優(yōu)良的染色體以一個(gè)較大的概率被選擇而得以進(jìn)入種群，反之劣質(zhì)的染色體被選中的概率較小。

本文采用基于序的評價(jià)函數(shù)，首先將群體按適應(yīng)值排序，之后依據(jù)下式進(jìn)行選擇：

式中：n為種群大?。籪i為染色體i的適應(yīng)值。

評價(jià)函數(shù)可以作為種群中染色體被選入種群的概率。利用評價(jià)函數(shù)可以確定染色體進(jìn)入種群的累計(jì)概率：

式中：pi為第i個(gè)種群的累計(jì)概率，當(dāng)pi-1＜r≤pi時(shí)，第i個(gè)染色體進(jìn)入種群（r為偽隨機(jī)數(shù)）。

在此，將評價(jià)函數(shù)值的全體稱為“輪盤賭”。本文采用輪盤賭的方式選擇種群。

2.5 交叉算子

交叉操作用于組合出新的個(gè)體，并使算法能夠搜索更多的解，同時(shí)降低對有效模式的破壞概率。由于車輛路徑問題編碼的特殊性，為了防止交叉后出現(xiàn)不滿足車輛容量限制的現(xiàn)象以及兩個(gè)0元素相鄰的現(xiàn)象，本文采用雙親雙子法進(jìn)行單點(diǎn)交叉運(yùn)算，取交叉概率Pc=0.95。隨機(jī)選取一位基因進(jìn)行交換，不能為0元素，并且兩個(gè)父代染色體的基因不能相同。為了保證解的合法性，必須要做內(nèi)部交換，防止1個(gè)需求點(diǎn)被多次訪問以及兩個(gè)0元素相鄰的現(xiàn)象。例如：

式中：Pa和Pb分別為兩個(gè)父代染色體，隨機(jī)選取交叉位9，分別對應(yīng)染色體Pa和Pb中的基因7和 3，將Pa中的7與Pb中的3互換，得到；檢查染色體中的基因，將其中重復(fù)的元素?fù)Q成缺失的元素，得到兩個(gè)子代。

2.6 變異算子

當(dāng)交叉操作產(chǎn)生的后代適配值不再進(jìn)化且沒有達(dá)到最優(yōu)時(shí)，就意味著算法的早熟收斂，而變異則是增加染色體多樣性的一個(gè)手段，它可以得到一些新的基因，通常賦予每1個(gè)染色體1個(gè)相對較小的變異概率。本文采用互換變異算子，由于是單點(diǎn)操作，所以變異概率取值稍大，取Pm=0.3?；Q變異即隨機(jī)交換染色體中兩個(gè)不同基因的位置，為保證染色體的合法性，隨機(jī)選取兩個(gè)不同的子路徑中不為0的基因進(jìn)行交換。如某個(gè)體為[012｜3045067｜80]（其中“｜”表示變異位），分別選取子路徑[01230]中的2和子路徑[06780]中的7進(jìn)行互換變異，得到新個(gè)體為[017304506280]。

2.7 算法終止條件

雖然遺傳算法在理論上具有以概率1收斂的極限性質(zhì)，但在實(shí)際中很難實(shí)現(xiàn)，因此在求解實(shí)際問題時(shí)追求的是快速搜索到具有一定質(zhì)量的滿意解。常用的終止規(guī)則有：給定最大遺傳迭代步數(shù)，給定最佳搜索解的最大滯留步數(shù)，給定問題的下界和1個(gè)偏差度，當(dāng)前最優(yōu)解與下界的差不大于偏差度時(shí)停止運(yùn)算。本文在給定最大遺傳迭代步數(shù)達(dá)到2 000次時(shí)，終止算法。

2.8 算法流程

基于改進(jìn)遺傳算法的車輛路徑問題算法流程如圖1所示，具體分為以下幾個(gè)步驟：

Step1：產(chǎn)生500個(gè)初始可行解作為初始種群，并令k=1，轉(zhuǎn)Step2；

Step2：利用評價(jià)函數(shù)評價(jià)第k代種群P(k)，并對種群按適應(yīng)值由小到大進(jìn)行排序，轉(zhuǎn)Step3；

Step3：保存到目前為止的最優(yōu)解及其適應(yīng)值，轉(zhuǎn)Step4；

Step4：如果k≤2000，轉(zhuǎn) Step5；否則轉(zhuǎn)Step8；

Step5：依據(jù)輪盤賭從父代中獲取種群，轉(zhuǎn)Step6；

Step6：對由Step5產(chǎn)生的種群進(jìn)行交叉操作，轉(zhuǎn)Step7；

Step7：對由Step6產(chǎn)生的種群進(jìn)行變異操作，轉(zhuǎn)Step2；

Step8：獲取最優(yōu)方案并輸出結(jié)果，算法結(jié)束。

圖1 算法流程圖

3 實(shí)例分析

某配送中心地理坐標(biāo)為（40，50），向100個(gè)需求點(diǎn)配送貨物，每輛車的載重為200，現(xiàn)有貨車10輛，每個(gè)需求點(diǎn)的地理坐標(biāo)和貨物需求量如表1所示（其中，NO為需求點(diǎn)編號，X為橫坐標(biāo)，Y為縱坐標(biāo)，D為需求點(diǎn)的需求量）。下面在保證每個(gè)需求點(diǎn)的送貨量和車輛不超載的前提下，求出配送中心對這100個(gè)需求點(diǎn)送貨的最短路徑。

表1 需求點(diǎn)地理坐標(biāo)及需求量一覽表

表1 （續(xù)）

用C++語言、CodeBlock開發(fā)工具編寫遺傳算法，在CPU主頻為2.53GHz、內(nèi)存為4G的電腦上對該算法進(jìn)行實(shí)例驗(yàn)證，求得了當(dāng)前最優(yōu)解。將當(dāng)前最優(yōu)解的迭代過程以圖的形式展示如下：第1代、第500代、第1 000代、第2 000代的車輛路徑分別如圖2、圖3、圖4、圖5所示（橫、縱坐標(biāo)表示客戶點(diǎn)的地理位置）。當(dāng)前最優(yōu)解的適應(yīng)值函數(shù)f與進(jìn)化迭代次數(shù)N的曲線關(guān)系如圖6所示。

圖2 第1代的車輛路徑圖

圖3 第500代的車輛路徑圖

圖4 第1 000代的車輛路徑圖

圖5 第2 000代的車輛路徑圖

圖6 當(dāng)前最優(yōu)解適應(yīng)值f與迭代次數(shù)N的關(guān)系圖

在第1代中，即初始可行解中，車輛路徑如表2所示，總的車輛里程為3 583.64。

表2 GA第1代時(shí)的車輛及其服務(wù)對象

在第2 000代中，即最優(yōu)解中，車輛路徑如表3所示，求得總的車輛里程為3 220.07。

表3 GA第2000代時(shí)的車輛及其服務(wù)對象

相比之下，最優(yōu)解比初始解節(jié)約里程約363.57。由于初始種群數(shù)量很多，所以初始解中的最優(yōu)解與當(dāng)前最優(yōu)解的差距相對就小。上述圖表形象地說明了本文設(shè)計(jì)的遺傳算法在求解VRP時(shí)的收斂情況及其魯棒性。

4 結(jié)論

本文通過車載容量約束的車輛路徑問題的模型以及改進(jìn)的遺傳算法研究了物流中心的配送路徑優(yōu)化問題，得出以下結(jié)論。

（1）初始種群規(guī)模影響著算法收斂速度，規(guī)模越大，染色體就越具有多樣性，算法收斂也就越快。

（2）交叉概率與變異概率的取值對優(yōu)化結(jié)果有著直接的影響：當(dāng)交叉概率Pc取0.9～1時(shí)，本文算法可以有效地求出當(dāng)前最優(yōu)解；生物進(jìn)化中變異只起輔助作用，但本文中變異算子與交叉算子同等重要，因此變異算子的概率取值偏大，取Pm≥0.3。

（3）對于受車載容量約束的車輛路徑問題，本文設(shè)計(jì)的遺傳算法能夠很好地求得其滿意解，可以為現(xiàn)實(shí)中物流配送方案提供支持和幫助。

不過，本文的研究還存在以下不足之處：沒有考慮服務(wù)時(shí)間窗的約束；沒有考慮車載容量可以允許輕微超載；在算法設(shè)計(jì)方面比較單一，應(yīng)該考慮多種智能算法的混合運(yùn)用，這樣可以提高求解速度和最優(yōu)解的質(zhì)量。以上這些都是未來進(jìn)一步研究的方向。

[1]史春燕，黃輝.車輛路徑問題：研究綜述及展望[J].物流科技，2014（12）：75-77.

[2]陶波，朱玉琴.改進(jìn)的動態(tài)規(guī)劃法在車輛最短路徑問題中的應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)：自然科版，2009（1）：24-27.

[3]CLARKE G,WRIGHT J W.Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J].Operations Research,1964,12(4):568-581.

[4]GILLETT B E,MILLER L R.A Heuristic Algorithm for the Vehicle Dispatch Problem[J].Operations Research,1974 (22):340-349.

[5]FISHER M L,JAIKUMAR R J.Ageneralized Assignment Heuristic for Vehicle Routing[J].Networks,1981(11):109-124.

[6]PUREZA V M,FRANCA P M.Vehicle Routing Problems via Tabu Search Metaheuristic[R].Montreal,Canada:Cen?tre for Research on Transportation,1991.

[7]程世東，劉小明，王兆賡.物流配送車輛調(diào)度研究的回顧與展望[J].交通運(yùn)輸工程與信息報(bào)，2004（3）：93-97，116.

[8]姜大立，楊西龍，杜文，等.車輛路徑問題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐，1999（6）：41.

[9]常洪江.遺傳算法綜述[J].電腦學(xué)習(xí)，2010（3）：115.

[10]賀國先.現(xiàn)代物流系統(tǒng)仿真[M].北京：中國鐵道出版社，2008：198.

[11]祁振華.基于敏捷制造的動態(tài)聯(lián)盟組建過程中伙伴選擇問題的研究[D].沈陽：沈陽工業(yè)大學(xué)，2005.

[12]占焱發(fā).基于遺傳算法的物流配送車輛路徑問題研究[D].西安：長安大學(xué)，2010.

An Improved GeneticAlgorithm for Vehicle Routing Problem

GAN Bao,XUE Yu-xi,WEI Wen-ping
(School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou 730070,China)

In order to research the service efficiency and reasonable scheduling scheme of vehicles of a logistics center,the vehicle load was taken as the main factor which influenced the vehicle routing ar?rangement,the classical capacitated vehicle routing problem was used as the prototype to establish the mathematical model,and the optimal path was obtained by solving the optimal solution of the mathemati?cal model.The initial feasible solution generated randomly served as the initial vehicle routing plan,a reasonable vehicle arrangement plan of logistics center was found finally by constantly adjusting chromo?somal crossover and mutation probability of the improved genetic algorithm to optimize the solution.It verifies the effectiveness and practicality of the proposed model,the convergence and robustness of the improved genetic algorithm by solving a numerical example for many times.Meanwhile the adjusting range of crossover and mutation probability of the improved genetic algorithm are obtained.The model and algorithm not only improves the service efficiency of logistics center,but also provide support and help for the vehicle scheduling scheme of logistics center.

logistics distribution;vehicle routing problem;genetic algorithm;crossover operator; convergence

U492.312

：A

：2095-9931（2015）04-0088-07

10.16503/j.cnki.2095-9931.2015.04.013

2015-07-06

甘寶（1989—）男，甘肅涇川人，碩士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理。E-mail:ganbao2012@163.com。