基于遺傳算法的物流配送車輛路徑優(yōu)化問(wèn)題

蘇楠，鹿靜，王棟梁

（長(zhǎng)安大學(xué)汽車學(xué)院，陜西 西安 710064）

?

基于遺傳算法的物流配送車輛路徑優(yōu)化問(wèn)題

蘇楠，鹿靜，王棟梁

（長(zhǎng)安大學(xué)汽車學(xué)院，陜西 西安 710064）

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

物流；路徑優(yōu)化；遺傳算法

10.16638/j.cnki.1671-7988.2016.06.002

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

引言

遺傳算法是來(lái)源于達(dá)爾文的進(jìn)化論，模擬生物的一代代繁衍，進(jìn)化。它是由美國(guó)Michigan大學(xué)的John，H. Holland教授在20世紀(jì)60年代中期提出，并和他的學(xué)生逐漸完善起來(lái)的[1]。在眾多的智能優(yōu)化算法中，遺傳算法是對(duì)生物進(jìn)化過(guò)程的模擬，應(yīng)用最為廣泛，研究歷史很長(zhǎng)。

在現(xiàn)代社會(huì)中，物流的重視度在不斷被提高，所以，降低物流運(yùn)輸?shù)某杀?，提高運(yùn)輸效率，將效益最大化就是很重要的問(wèn)題。本文主要是針對(duì)車輛路徑優(yōu)化問(wèn)題進(jìn)行研究。

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

當(dāng)代全球越來(lái)越趨于全球村，物流產(chǎn)業(yè)也開(kāi)始?jí)汛笃饋?lái)，逐漸成為一個(gè)龐大的產(chǎn)業(yè)，越來(lái)越受到各個(gè)企業(yè)的重視。物流本身所具備的流動(dòng)性和開(kāi)放性，能夠大力的促進(jìn)社會(huì)經(jīng)濟(jì)的進(jìn)步。

物流配送就是運(yùn)輸衍生出來(lái)的一種功能，是市場(chǎng)不斷發(fā)展的必然產(chǎn)物，也是經(jīng)濟(jì)發(fā)展的重點(diǎn)之一。在盡可能的減少成本，提高利益的目的下，而物流配送中更關(guān)鍵的就是怎樣合理的調(diào)度車輛[2]。

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

2、基于遺傳算法的車輛路徑問(wèn)題研究

2.1物流配送車輛路徑優(yōu)化的數(shù)學(xué)模型

2.1.1變量的設(shè)定

在保證滿足每個(gè)客戶的要求的前提下，不超過(guò)每臺(tái)車的限載量和最遠(yuǎn)行駛距離，使配送距離最短，效益最優(yōu)，并且還需要滿足以下條件[3]：

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

每一條配送路徑的總長(zhǎng)度不得超過(guò)該車輛的最遠(yuǎn)行駛距離；

必須保證每個(gè)客戶都能拿到相應(yīng)數(shù)量的貨物，并且每個(gè)客戶只能由一臺(tái)車進(jìn)行配送；

K：物流中心共有K臺(tái)配送車輛。

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

Dk：每臺(tái)配送車輛的最遠(yuǎn)行駛距離為Dk。

L：一共的客戶數(shù)為L(zhǎng)個(gè)。

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

dij：從客戶i到客戶j的運(yùn)輸距離為dij。

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

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

Rk：第k條路徑。

rki：rki表示客戶在路徑k中的順序?yàn)閕(不包括物流中心)。rk0=0表示物流中心。

若以配送距離最短為目標(biāo)函數(shù)，則可建立如下最優(yōu)化物流配送路徑問(wèn)題的數(shù)學(xué)模型[3]:

2.1.2約束條件

(1)式為目標(biāo)函數(shù)值，既總配送距離。

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

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

(4)式限制每條配送路線上的的客戶數(shù)不得多于總客戶數(shù)。(5)式保證每個(gè)客戶都能拿到相應(yīng)數(shù)量的貨物。(6) 式限制每個(gè)客戶只能由一臺(tái)車進(jìn)行配送。(7)式中為0表示該臺(tái)車沒(méi)有被利用[4]。

2.2針對(duì)算法優(yōu)化物流配送車輛路徑優(yōu)化的遺傳算法構(gòu)造

2.2.1編碼方法的選定

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

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

隨機(jī)產(chǎn)生一個(gè)由1~（L+1）和K-1個(gè)0組成的的序列，形成一條染色體，種群大小為M，則由M條不同的染色體構(gòu)成初始種群。

2.2.3適應(yīng)度評(píng)估

每一條染色體對(duì)應(yīng)一個(gè)配送方案，在計(jì)算他的目標(biāo)值之前，要先判斷它的可用性，不可用的話，為不可行路徑，直接淘汰掉，對(duì)剩下的可用染色體計(jì)算目標(biāo)值?？尚腥旧w的適應(yīng)度可用下式表示：

式中：G為權(quán)重因子，取一個(gè)較大的正數(shù)(G值太小則會(huì)影響適應(yīng)度的比較)。

2.2.4選擇操作

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

2.2.5交叉操作

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

由第n代到第n+1代產(chǎn)生的新種群，除了一條直接復(fù)制過(guò)來(lái)的最優(yōu)染色體外，其余的都要依據(jù)交叉概率進(jìn)行交叉配對(duì)[6]。

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

2.2.6變異操作

本文中因?yàn)樘厥獾木幋a方法，也要采用一種特殊的變異方法[7]，根據(jù)變異概率，染色體的一個(gè)部位發(fā)生變異時(shí)，另一個(gè)相應(yīng)的部位也要發(fā)生相應(yīng)的變異。例如：染色體572036014上的3位發(fā)生了變異，變成了4，則4位上也要發(fā)生變異，變成3。

2.3實(shí)驗(yàn)與計(jì)算

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

表1　已知條件表

表2　計(jì)算結(jié)果表

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

從結(jié)果可以看出，遺傳算法的計(jì)算效率非常高，求解結(jié)果也比較穩(wěn)定，在10次求最優(yōu)解時(shí)中，有3次得到了問(wèn)題的最優(yōu)解，7次得到了問(wèn)題的近似最優(yōu)解。

3、結(jié)論

由實(shí)驗(yàn)結(jié)果可以看出，先隨機(jī)建立物流配送的模型，然后再用遺傳算法進(jìn)行求解，是一種比較方便，快捷的求解方式，可以在較短的時(shí)間內(nèi)就求得物流配送路徑的最優(yōu)解。

但是遺傳算法也有缺點(diǎn)，雖然全局搜索能力比較強(qiáng)，但是局部搜索能力很弱，能夠在短時(shí)間內(nèi)就接近最優(yōu)解，但是在接近最優(yōu)解后，達(dá)到最優(yōu)解還需要一段時(shí)間，如果能和其他算法一起計(jì)算，則能迅速提高效率。

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

[2] 占焱發(fā). 基于遺傳算法的物流配送車輛路徑問(wèn)題研究[D]. 西安:長(zhǎng)安大學(xué)2010.

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

[4] 朗茂祥.基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題研究[J].中國(guó)公路學(xué)報(bào),2002,15(3):77-78.

[5] 周和平.軍事物流配送路徑優(yōu)化問(wèn)題研究[D]. 合肥:合肥工業(yè)大學(xué)2009.

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

[7] 安立軍;俞宏生.基于遺傳算法(GA)的配送路徑優(yōu)化問(wèn)題研究[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

蘇楠，就讀于長(zhǎng)安大學(xué)。

U468.8

A

1671-7988 （2016）06-04-03