基于改進遺傳算法的車輛路徑問題

甘 寶，薛玉璽，魏文萍

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

基于改進遺傳算法的車輛路徑問題

甘 寶，薛玉璽，魏文萍

（蘭州交通大學 交通運輸學院，甘肅 蘭州 730070）

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

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

0 引言

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

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

1 VRP數學模型

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

此外，還包括以下約束和假設：

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

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

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

（4）假設車型相同，容量相同；

（5）假設配送中心唯一。

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

由此，建立車輛路徑問題的數學模型如下：

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

2 VRP的遺傳算法

遺傳算法是一種基于生物自然選擇和基因遺傳學原理的優化搜索方法。自然選擇學說是進化論的核心思想，根據進化論，生物的發展進化主要有三個原因：遺傳、變異和選擇[10]。

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

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

2.1 算法編碼

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

2.2 初始種群的產生

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

2.3 適應值函數

適應值函數是評價每個染色體優劣的函數，一般與問題的目標函數有密切關系，染色體的適應值函數（簡稱適值）是染色體優劣的量化指標。VRP的目標是使車輛的總里程最短，其目標函數如式（6）所示，本文將其目標函數直接作為適應值函數。

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

2.4 評價函數與種群選擇

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

本文采用基于序的評價函數，首先將群體按適應值排序，之后依據下式進行選擇：

式中：n為種群大小；fi為染色體i的適應值。

評價函數可以作為種群中染色體被選入種群的概率。利用評價函數可以確定染色體進入種群的累計概率：

式中：pi為第i個種群的累計概率，當pi-1＜r≤pi時，第i個染色體進入種群（r為偽隨機數）。

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

2.5 交叉算子

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

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

2.6 變異算子

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

2.7 算法終止條件

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

2.8 算法流程

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

Step1：產生500個初始可行解作為初始種群，并令k=1，轉Step2；

Step2：利用評價函數評價第k代種群P(k)，并對種群按適應值由小到大進行排序，轉Step3；

Step3：保存到目前為止的最優解及其適應值，轉Step4；

Step4：如果k≤2000，轉 Step5；否則轉Step8；

Step5：依據輪盤賭從父代中獲取種群，轉Step6；

Step6：對由Step5產生的種群進行交叉操作，轉Step7；

Step7：對由Step6產生的種群進行變異操作，轉Step2；

Step8：獲取最優方案并輸出結果，算法結束。

圖1 算法流程圖

3 實例分析

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

表1 需求點地理坐標及需求量一覽表

表1 （續）

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

圖2 第1代的車輛路徑圖

圖3 第500代的車輛路徑圖

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

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

圖6 當前最優解適應值f與迭代次數N的關系圖

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

表2 GA第1代時的車輛及其服務對象

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

表3 GA第2000代時的車輛及其服務對象

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

4 結論

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

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

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

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

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

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

[2]陶波，朱玉琴.改進的動態規劃法在車輛最短路徑問題中的應用[J].重慶工學院學報：自然科版，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]程世東，劉小明，王兆賡.物流配送車輛調度研究的回顧與展望[J].交通運輸工程與信息報，2004（3）：93-97，116.

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

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

[10]賀國先.現代物流系統仿真[M].北京：中國鐵道出版社，2008：198.

[11]祁振華.基于敏捷制造的動態聯盟組建過程中伙伴選擇問題的研究[D].沈陽：沈陽工業大學，2005.

[12]占焱發.基于遺傳算法的物流配送車輛路徑問題研究[D].西安：長安大學，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—）男，甘肅涇川人，碩士研究生，研究方向為交通運輸規劃與管理。E-mail:ganbao2012@163.com。