基于遺傳算法（ＧＡ）的配送路徑優(yōu)化問題研究

摘要：文章在建立配送車輛路徑優(yōu)化問題數(shù)學模型的基礎上，構造了遺傳算法來求解該問題，并在算法中引入了自然選擇、交叉操作、變異操作等思想。實驗結(jié)果表明，此算法可以有效求得車輛路徑問題的優(yōu)化解或近似優(yōu)化解，是求解車輛路徑問題的一個較好的方案。

關鍵詞：配送；路徑優(yōu)化；遺傳算法

中圖分類號：F252文獻標識碼：A文章編號：1002-3100(2007)10-0033-04

Abstract: On the basis of the mathematic model for logistics distribution VRP， this paper presents Genetic Algorithm（GA）to solving this problem， and has led into idea such as natural selection， interlace operation， dissociation operation in the algorithm. This algorithm can find the optimal or nearly optimal solution to the vehicle routing problem effectively， which is proved by the number experiment provided by this paper.

Key words: distribution; routing optimizing; Genetic Algorithm

0引言

物流配送路徑優(yōu)化問題，即所謂的車輛路徑問題（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser于1959年提出的，屬于典型的復雜組合優(yōu)化問題。其研究的問題可以描述為：有n個商品需求點（可以稱之為顧客），各個顧客之間的距離以及商品需求量事先已知，要求從中心倉庫（或稱為配送中心）最多用k輛車來運輸商品，每輛車載重量一定，使得運輸路程最短并滿足所有顧客的需求。車輛路徑問題的研究具有應用的廣泛性和經(jīng)濟上的重大價值，受到國內(nèi)外學者的廣泛關注。

由于車輛路徑問題是NP完全問題，隨著顧客數(shù)量的增加，其解呈指數(shù)級增長，用精確算法很難求得最優(yōu)解。因此， 用啟發(fā)式算法求解該問題就成為人們研究的一個重要方向，遺傳算法（Genetic Algorithm，GA）是由J.H.Holland等于20世紀70年代發(fā)展起來的。它抽象于生物體的進化過程，是一種以自然選擇和遺傳理論為基礎，將生物進化過程中適者生存規(guī)則與同一群染色體的隨機信息變換機制相結(jié)合的搜索算法。其通過給解向量編碼、形成初始種群，然后用變異、交叉重組、自然選擇等算子，進行并行迭代，求得優(yōu)化解。由于它采用隨機選擇，對搜索空間無特殊要求，無需求導，具有運算簡單、收斂速度快等優(yōu)點，尤其適用于處理傳統(tǒng)搜索方法難于解決的復雜和非線性的問題，目前已廣泛應用于組合優(yōu)化、機器學習、自適應控制等領域。為此，本文研究運用GA編碼構造求解車輛路徑問題的算法，并對其運算過程和結(jié)果進行分析。實驗數(shù)據(jù)表明本算法行之有效，不失為一種求解車輛路徑問題的性能優(yōu)越的啟發(fā)式算法。

1VRP優(yōu)化問題的數(shù)學模型

VRP可以描述為：有多個商品需求點（可以稱之為顧客），各個顧客之間的距離以及商品需求量事先已知，要求從中心倉庫（或稱為配送中心）最多用k輛車來運輸商品，每輛車載重量一定，要求合理安排車輛配送路線，使目標函數(shù)得到優(yōu)化，并滿足以下條件：（1）每條配送路徑上各客戶的需求量之和不超過配送車輛的載重量；（2）每條配送路徑的長度不超過配送車輛一次配送的最大行駛距離；（3）每個客戶的需求必須滿足，且只能由一臺配送車輛送貨。

2VRP優(yōu)化問題的遺傳算法

2.1遺傳算法的基本原理

在自然進化中，每一物種越來越適應環(huán)境；物種的個體的基本特征被其后代所繼承，但后代又不完全同于自己的父代；個體的性質(zhì)是由染色體決定的，染色體是由基因有序排列組成的；由染色體決定的個體對環(huán)境有不同的適應性，通過基因雜交和基因突變產(chǎn)生適應性強的個體；在世代進化中，“適者生存”的自然選擇的強制作用，使得更能適應環(huán)境的個體的特征（對應適應值高的基因結(jié)構）被保存下來。GA正是基于自然選擇和自然遺傳這種生物進化機制的搜索算法，把優(yōu)化問題的解的搜索空間映射為遺傳空間，把每一可能的解編碼為一個稱為染色體的二進制串（也有其它編碼方法），染色體的每一位稱為基因。每個染色體（對應一個個體）代表一個解，一定數(shù)量的個體組成群體。GA首先隨機地產(chǎn)生一些個體組成初始群體（即問題的一群候選解），按預先根據(jù)目標函數(shù)確定的適應度函數(shù)計算各個體的對問題環(huán)境的適應度，再根據(jù)個體適應度對個體對應的染色體進行選擇，抑制適應度低的染色體，弘揚適應度高的染色體，然后進行交叉、變異等遺傳操作產(chǎn)生進化了的一代群體。如此反復操作，一代一代不斷向更優(yōu)解方向進化，最后得到滿足某種收斂條件的最適應問題環(huán)境的群體，從而獲得問題的最優(yōu)解。

如圖1是一個使用選擇（再生）、交換和突變?nèi)N遺傳操作的GA。

選擇：其過程為，基于個體對環(huán)境的適應度（由f∑f決定，其中f是對象函數(shù)值，∑f是群體里所有對象函數(shù)值的和），決定哪個個體被復制。選擇意味著較高對象函數(shù)值的個體，有較大的概率在下一代提供一個或多個后代。

為了能使算法收斂到全局最優(yōu)，遺傳群體應具有一定規(guī)模，但為了保證計算效率，群體規(guī)模也不能太大。在初始化染色體時，先生成k個分倉庫的一個全排列，再將m+1個0隨機插入排列中。需要注意的是，必須要有兩個0被安排在排列的頭部和尾部，并且在排列中不能有連續(xù)的兩個0。這樣就構成一條滿足問題需要的染色體，重復這一過程，直至生成滿足群體規(guī)模數(shù)的染色體。

2.2.2計算適應度函數(shù)

對于某個個體所對應的配送路徑方案，要判定其優(yōu)劣，一是要看其是否滿足配送的約束條件；二是要計算其目標函數(shù)值（即各條配送路徑的長度之和）。根據(jù)配送路徑優(yōu)化問題的特點所確定的編碼方法，隱含能夠滿足每個需求點都得到配送服務及每個需求點僅由一輛汽車配送的約束條件，但不能保證滿足每條路徑上各需求點需求量之和不超過汽車載重量及每條配送路線的長度不超過汽車一次配送的最大行駛距離的約束條件。

為此，對每個個體所對應的配送路徑方案，要對各條路徑逐一進行判斷，看其是否滿足上述兩個約束條件，若不滿足，則將該條路徑定為不可行路徑，最后計算其目標函數(shù)值。對于某個個體j，設其對應的配送路徑方案的不可行路徑數(shù)為Mj（Mj=0表示該個體對應一個可行解），其目標函數(shù)值為Zj，則該個體的適應度Fj可用下式表示

Fj=1Zj+MjG（9）

式中，G為對每條不可行路徑的懲罰權重， 可根據(jù)目標函數(shù)的取值范圍取一個相對較大的正數(shù)。

2.2.3自然選擇

根據(jù)計算父代和子代的適應度，并將每代群體中的N個個體按適應度由大到小排列，排在第一位的個體性能最優(yōu)，將它復制一個直接進入下一代，并排在第一位。下一代群體的另N-1個個體需要根據(jù)前代群體的N個個體的適應度，采用輪盤賭選擇法產(chǎn)生。

2.2.4交叉操作實現(xiàn)

（1）隨機在父代個體中選擇一個交配區(qū)域，如兩父代個體及交配區(qū)域選定為：A=47|8563|921，B=83|4691|257；

（2）將B的交配區(qū)域加到A的前面，A的交配區(qū)域加到B的前面，得：A'=4691|478563921，B'=8563|834691257；

（3）在A'、B'中自交配區(qū)域后依次刪除與交配區(qū)相同的自然數(shù)，得到最終的兩個體為：A\"=469178532，B\"=856349127。

與其他交叉方法相比，這種方法在兩父代個體相同的情況下仍能產(chǎn)生一定的變異效果，這對維持群體的多樣性有一定的作用。

2.2.5變異操作實現(xiàn)

2.2.6結(jié)束條件

當算法的當前進化代數(shù)小于預先設定的N時，返回3.2.2計算適應度函數(shù)部分，算法繼續(xù)。

3實例計算及結(jié)果分析

3.1實例計算

3.2實例計算結(jié)果分析

從表中數(shù)據(jù)可以看出，應用遺傳算法求解VRP時，得到最終的配送路徑方案為：路徑1：0-4-7-6-0；路徑2：0-2-8-5-3-1-0，而且第4次還得到了該問題的最優(yōu)解67.5 km。然而用節(jié)約法再對其進行求解，得到的最終配送路徑方案為：路徑1：0→6→5→7→3→0，路徑2：0→4→8→2→1→0，并且得到相應運輸距離為79.5km。

由表中數(shù)據(jù)可見，應用遺傳算法得到的10次運行結(jié)果均優(yōu)于節(jié)約法所得的結(jié)果79.5 km。所以說，應用遺傳算法進行配送路徑優(yōu)化的方案，既能滿足車輛容量約束又滿足了各客戶的貨物需求，是上述車輛路徑問題的一個可行解，而且利用遺傳算法可以方便有效地求得VRP的最優(yōu)解或近似最優(yōu)解（滿意解）。

4結(jié)論

在物流配送系統(tǒng)中，合理選擇配送路徑是提高服務質(zhì)量、降低配送成本、提高經(jīng)濟效益的重要手段。但是由于VRP本身的NP完全性質(zhì)，要精確求解非常困難，因此，研究啟發(fā)式算法不失為一種可行的研究方向。

本文在建立VRP數(shù)學模型的基礎上，通過對VRP優(yōu)化問題的分析，提出了構造求解VRP的遺傳算法，在算法中設計的個體編碼方法、個體適應度計算方法及選擇、交叉、變異算子，對解決類似的組合優(yōu)化問題具有一定的參考價值。實驗計算結(jié)果表明本算法是一種性能較好的啟發(fā)式搜索方法， 利用該方法可以較快地找到問題的優(yōu)化解或近似優(yōu)化解，是求解車輛路徑問題的一個較好的方案。

參考文獻：

[1] 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國物資出版社，2001.

[2] 李軍，謝秉磊，郭強. 非滿載車輛調(diào)度問題的遺傳算法[J]. 系統(tǒng)工程理論方法應用，2000(3):235-239.

[3] 李敏強，寇紀淞，等. 遺傳算法的基本理論與應用[M]. 北京：科學出版社，2003.

[4] 姜大立，楊西龍，杜文，等. 車輛路徑問題的遺傳算法研究[J]. 系統(tǒng)工程理論與實踐，1999，19(6):40-45.

[5] 郎茂祥. 基于遺傳算法的物流配送路徑優(yōu)化問題研究[J]. 中國公路學報，2002，15(3):76-79.

[6] 李向陽. 遺傳算法求解VRP問題[J]. 計算機工程與設計，2004，25(2):271-276.

[7] 唐坤. 車輛路徑問題中的遺傳算法設計[J]. 東華大學學報：自然科學版，2002，28(1):66-70.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”