基于遺傳算法的物流配送車輛路徑優化問題

蘇楠，鹿靜，王棟梁

（長安大學汽車學院，陜西 西安 710064）

?

基于遺傳算法的物流配送車輛路徑優化問題

蘇楠，鹿靜，王棟梁

（長安大學汽車學院，陜西 西安 710064）

在當代社會，物流越來越受到各國的重視，是企業創造利潤的又一有效途徑。文章主要研究在物流配送中的一個方面，也就是車輛路徑優化問題，主要采用遺傳算法進行計算。依據遺傳算法，建立車輛路徑優化的數學模型，配送路徑的限制條件。在用遺傳算法進行計算時，采用自然數序列進行編碼，在選擇時采用最優個體保留策略和輪盤賭法，變異時不只是單一的變異，而是兩位基因同時變異，最終求得最優解。我國物流起步較晚，不及一些發達國家，所以有很大的進步空間。

物流；路徑優化；遺傳算法

10.16638/j.cnki.1671-7988.2016.06.002

CLC NO.: U468.8 Document Code: A Article ID: 1671-7988 (2016)06-04-03

引言

遺傳算法是來源于達爾文的進化論，模擬生物的一代代繁衍，進化。它是由美國Michigan大學的John，H. Holland教授在20世紀60年代中期提出，并和他的學生逐漸完善起來的[1]。在眾多的智能優化算法中，遺傳算法是對生物進化過程的模擬，應用最為廣泛，研究歷史很長。

在現代社會中，物流的重視度在不斷被提高，所以，降低物流運輸的成本，提高運輸效率，將效益最大化就是很重要的問題。本文主要是針對車輛路徑優化問題進行研究。

1、本文的研究背景與意義

當代全球越來越趨于全球村，物流產業也開始壯大起來，逐漸成為一個龐大的產業，越來越受到各個企業的重視。物流本身所具備的流動性和開放性，能夠大力的促進社會經濟的進步。

物流配送就是運輸衍生出來的一種功能，是市場不斷發展的必然產物，也是經濟發展的重點之一。在盡可能的減少成本，提高利益的目的下，而物流配送中更關鍵的就是怎樣合理的調度車輛[2]。

配送中心的地理位置，各個客戶的地理位置也是已知的，還有各個客戶的需求量以及配送車輛的限載量和最遠配送距離都是已知的，要求合理安排車輛的行駛路線，從調度中心出發，依次到達各個客戶，最后返回配送中心，使行駛距離最短，成本最低，利益最大化。

2、基于遺傳算法的車輛路徑問題研究

2.1物流配送車輛路徑優化的數學模型

2.1.1變量的設定

在保證滿足每個客戶的要求的前提下，不超過每臺車的限載量和最遠行駛距離，使配送距離最短，效益最優，并且還需要滿足以下條件[3]：

每一條配送路徑上的所有客戶的需求量的總和不能超過該臺車的限載量；

每一條配送路徑的總長度不得超過該車輛的最遠行駛距離；

必須保證每個客戶都能拿到相應數量的貨物，并且每個客戶只能由一臺車進行配送；

K：物流中心共有K臺配送車輛。

Qk：每臺配送車輛的限載量為Qk(k = 1、2……K)。

Dk：每臺配送車輛的最遠行駛距離為Dk。

L：一共的客戶數為L個。

qi：每個客戶需要的貨物量為qi（i=1.2……L）。

dij：從客戶i到客戶j的運輸距離為dij。

d0j：物流中心到各個客戶之間的的距離為d0j(i、j = 1、2……L)。

nk：第k臺車輛一共配送的客戶數為nk(nk=0表示未使用第k臺車輛)。

Rk：第k條路徑。

rki：rki表示客戶在路徑k中的順序為i(不包括物流中心)。rk0=0表示物流中心。

若以配送距離最短為目標函數，則可建立如下最優化物流配送路徑問題的數學模型[3]:

2.1.2約束條件

(1)式為目標函數值，既總配送距離。

(2)式限制每一條配送路徑上的所有客戶的需求量的總和不能超過該臺車的限載量。

(3)式限制每一條配送路徑的總長度不得超過該車輛的最遠行駛距離。

(4)式限制每條配送路線上的的客戶數不得多于總客戶數。(5)式保證每個客戶都能拿到相應數量的貨物。(6) 式限制每個客戶只能由一臺車進行配送。(7)式中為0表示該臺車沒有被利用[4]。

2.2針對算法優化物流配送車輛路徑優化的遺傳算法構造

2.2.1編碼方法的選定

采用直接編碼方式，有L個客戶，將1~（L+1）間的自然數進行隨機排列，0表示的是配送中心，有K臺配送車輛，將K-1個0隨機插入該排列中，則形成了一個類似于二進制碼的代碼。

2.2.2初始種群的產生

隨機產生一個由1~（L+1）和K-1個0組成的的序列，形成一條染色體，種群大小為M，則由M條不同的染色體構成初始種群。

2.2.3適應度評估

每一條染色體對應一個配送方案，在計算他的目標值之前，要先判斷它的可用性，不可用的話，為不可行路徑，直接淘汰掉，對剩下的可用染色體計算目標值。可行染色體的適應度可用下式表示：

式中：G為權重因子，取一個較大的正數(G值太小則會影響適應度的比較)。

2.2.4選擇操作

同時采用最優個體保留策略和輪盤賭法[5]。先是最優個體保留策略，將最優的個體，也就是適應度值最高的個體，直接進行復制到下一代。然后，運用輪盤賭法。將該代種群中所有可用染色體適應度加起來，得到，再計算出每條染色體的適應度在總的適應度值里所占的比例，得到，這就是該條染色體被選中的概率。

2.2.5交叉操作

交叉操作，就是將兩個隨機組合的染色體相互交換對方的一部分基因，從而形成兩個全新的個體。

由第n代到第n+1代產生的新種群，除了一條直接復制過來的最優染色體外，其余的都要依據交叉概率進行交叉配對[6]。

例如：兩條n代染色體分別為A=52|073|6014，B=31| 507|0264，將B中間的交配區域加到A染色體的的前面，A的中間交配區域加到B染色體的前面，將其中的0去掉得：A1=57|520736014，B1=73|315070264；在A1、B1中自交配區域后刪除與交配區相同的自然數,得到的最終下一代個體為：A2=572036014，B2=73150264。

2.2.6變異操作

本文中因為特殊的編碼方法，也要采用一種特殊的變異方法[7]，根據變異概率，染色體的一個部位發生變異時，另一個相應的部位也要發生相應的變異。例如：染色體572036014上的3位發生了變異，變成了4，則4位上也要發生變異，變成3。

2.3實驗與計算

例：某物流中心一共擁有2臺配送車輛,兩臺車輛的限載量均為8t，車輛每次配送的最大行駛距離也均為50km,配送中心與8個客戶之間以及8個客戶相互之間的距離、8個客戶的貨物需求量均見表 1。要求合理的安排物流配送路線，使車輛配送總里程最短。

表1　已知條件表

表2　計算結果表

計算時采用以下參數：初始群體規模M取為20，進化代數N取為25，交叉概率取為0.9，變異概率取為0.09，變異時基因換位次數取5，懲罰權重取100km。隨機求解10次，得到的計算結果見表2。

從結果可以看出，遺傳算法的計算效率非常高，求解結果也比較穩定，在10次求最優解時中，有3次得到了問題的最優解，7次得到了問題的近似最優解。

3、結論

由實驗結果可以看出，先隨機建立物流配送的模型，然后再用遺傳算法進行求解，是一種比較方便，快捷的求解方式，可以在較短的時間內就求得物流配送路徑的最優解。

但是遺傳算法也有缺點，雖然全局搜索能力比較強，但是局部搜索能力很弱，能夠在短時間內就接近最優解，但是在接近最優解后，達到最優解還需要一段時間，如果能和其他算法一起計算，則能迅速提高效率。

[1] 武交鋒. 應用遺傳算法提高蟻群算法性能的研究[D]. 太原:太原理工大學2007.

[2] 占焱發. 基于遺傳算法的物流配送車輛路徑問題研究[D]. 西安:長安大學2010.

[3] 余玥;胡宏智. 基于改進遺傳算法的物流配送路徑求解[J]. 計算機技術與發展,2009,19(3):52-55.

[4] 朗茂祥.基于遺傳算法的物流配送路徑優化問題研究[J].中國公路學報,2002,15(3):77-78.

[5] 周和平.軍事物流配送路徑優化問題研究[D]. 合肥:合肥工業大學2009.

[6] 王旭升;尤小霞. 基于混合遺傳優化算法的物流配送路徑分析[J].物流技術,2014,5:269-271.

[7] 安立軍;俞宏生.基于遺傳算法(GA)的配送路徑優化問題研究[J].物流科技,2007,10：33-36.

Routing optimization problem of logistics distribution vehicle based on genetic algorithm

Su Nan, Lu Jing, Wang Dongliang
( College of automotive engineering, Chang'an University, Shaanxi xi'an 710064 )

In contemporary society, the logistics gets more and more national attention ,it is another effective way for enterprises to create profits.This paper studies one aspect of the logistics and distribution, which is the vehicle routing problem, mainly using genetic algorithms to calculate. The mathematical model of VRP is built on genetic algorithm with distribution route restrictions.When calculated with the genetic algorithm, the natural number sequence is encoded,the best individual retention policies and roulette method is used on choosing.Compiled with not just a single mutation, but simultaneously two gene mutation, and ultimately get the optimal solution.China's logistics start late, less than some developed countries, so there is great potential for improvement.

Logistics; Route optimization; Genetic Algorithm

蘇楠，就讀于長安大學。

U468.8

A

1671-7988 （2016）06-04-03