遺傳算法在物流配送路徑優(yōu)化問題中的應(yīng)用

郭淑紅　楊曉慧

[摘要]遺傳算法是一種基于自然進化原理的全局搜索隨機算法。遺傳算法在物流管理的運輸問題、布局問題、選址問題、配送問題、調(diào)度問題等方面應(yīng)用非常廣泛。首先建立物流配送路徑優(yōu)化問題數(shù)學(xué)模型，在此基礎(chǔ)上構(gòu)造求解物流配送路徑優(yōu)化問題的遺傳算法。用此遺傳算法進行物流配送路徑優(yōu)化，可以方便有效地求得問題的最優(yōu)解或近似最優(yōu)解。

[關(guān)鍵詞]物流配送 遺傳算法 優(yōu)化

中圖分類號：O29 文獻標識碼：A 文章編號：1671-7597（2009）0110046-01

一、引言

當(dāng)前在解決物流配送車輛調(diào)度問題上有很多種算法，如神經(jīng)元網(wǎng)絡(luò)、蟻群算法（Ant Colony Optimization）等，但運用最多的是啟發(fā)式算法，其中又有遺傳算法、模擬退火算法、爬山算法、禁忌搜索算法等。

遺傳算法（Genetic Algorithms，簡稱GA）是J.Holland于1975年受生物進化論的啟發(fā)而提出的。遺傳算法將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解或滿意解。

該算法包括以下6個基本要素：(1)編碼；(2)生成初始種群；(3)評估適應(yīng)度；(4)選擇：根據(jù)“適者生存”的選擇原理；(5)交叉；(6)變異。

二、問題的提出

假定一配送中心，向n個顧客運送貨物，每個顧客對貨物有一定的需求量，貨運車在配送中心配裝發(fā)車后，把貨物送到各顧客處，如何確定費用最小的車輛行駛路線?問題的關(guān)鍵是如何合理安排車輛數(shù)目和車輛路線，使得總的旅行路程最短。

三、問題的分析

為便于討論，對問題做幾點假設(shè)：

1．被配送的是已知的同一種物資；

2．各用戶的所在地已知；

3．各用戶的需求量已知；

4．從配送網(wǎng)點到各用戶之間的運輸距離已知；

5．配送網(wǎng)點有足夠的資源可以供應(yīng)配送，并且擁有足夠的配送能力。

另外，配送計劃中的最優(yōu)發(fā)車路線，必須符合下列約束條件：

1．配送必須滿足所有用戶的需求；

2．對每一輛發(fā)送車的裝載量有一定的限制，不允許超載運行；

3．對發(fā)送車每天的總運行時間（或總運行距離）有預(yù)定的上限；

4．必須滿足用戶提出的到貨時間要求。

對一個具體的問題，上述約束條件可能全部存在，也可能只存在一部分。解決配送問題就是在以上約束條件下應(yīng)如何派送車輛，給出車輛數(shù)、型號和各車輛的具體行車路線。訂單上的貨物全部送到即可完成當(dāng)日的運輸任務(wù)，又可以使總運輸公里數(shù)最小。

物流配送路徑的優(yōu)化可以描述為：從配送中心用多輛汽車向多個客戶送貨，每個客戶的位置和需求量一定，每輛汽車的載量一定，要求合理安排汽車路線，使總運距離最短，并滿足以下條件：

1．每條配送路徑上各個客戶的需求量之和不超過汽車載量；

2．每條配送路徑的長度不超過汽車一次配送的最大行駛距離；

3．每個客戶的需求必須滿足，且只能由一輛汽車送貨。充分考慮上述問題的約束條件和優(yōu)化目標。

四、優(yōu)化算法優(yōu)化物流配送路徑遺傳算法的構(gòu)造

針對優(yōu)化物流配送路徑的特點，本文構(gòu)造了求解該問題的遺傳算法。

（一）編碼方法的選定。采用二進制編碼，用0表示配送中心，用1表示某個客戶（L個1表示有L個不同的客戶）。由于配送中心有K輛汽車，則最多存在K條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。這樣，L個1或K-1個0隨機排列成一條染色體（N+K-1位），對應(yīng)于一種配送路徑方案。

（二）初始種群的生成。隨機產(chǎn)生一個L個1和K-1個0的序列，形成一條染色體（個體位串），M條不同的染色體構(gòu)成初始種群（設(shè)種群大小為M）。

（三）適應(yīng)度評估。要評判某條染色體所對應(yīng)的配送路徑方案，既要看其能否滿足配送的約束條件，又要計算其目標函數(shù)值，本文使用的編碼方法，能夠保證每個客戶都得到配送服務(wù)，及每個客戶僅由一輛汽車配送的約束條件，但不能滿足每條路徑上各客戶需求量之和不超過汽車載量及每條配送路線的長度不超過汽車一次配送的最大行駛距離的約束條件。所以，對于每條染色體所對應(yīng)的配送路徑方案，要對各條路徑逐一進行判斷，看其能否滿足約束條件：如果不滿足，則該條路徑為不可行路徑，并計算其目標函數(shù)值。

（四）選擇操作、結(jié)合使用最優(yōu)個體保留策略和輪盤賭法，將每代種群中的N條染色體按適應(yīng)度從大到小排列。適應(yīng)度最高的染色體，復(fù)制直接進入下一代。然后，根據(jù)種群的N條染色體的適應(yīng)度。采用輪盤賭法產(chǎn)生下一代種群的另N-1條染色體。方法為計算出種群中所有染色體適應(yīng)度的總和（∑Fi）；再計算每條染色體的適應(yīng)度所占的比例（Fi/∑Fi），作為其被選中的概率Psi。

（五）交叉操作。選擇操作產(chǎn)生的新種群，除第一條染色體外，另N-1條染色體要根據(jù)交叉概率Pc進行交叉配對，可以采用一種改進的兩點交叉法。

（六）變異操作。適度的變異，既能保持種群內(nèi)個體的多樣化，又能提高遺傳算法的效率。根據(jù)變異概率Pmi一旦染色體的某基因片段需要發(fā)生變異，則染色體上的另一片段也要同時發(fā)生變異。

五、實例

某配送中心用2輛汽車對8個客戶配送貨物。設(shè)汽車的載量為8×103kg。每次配送的最大行駛距離為40km，配送中心與客戶、客戶與客戶之間的距離及各客戶的需求量見下表。在實驗中采用了以下參數(shù)值：種群大小M取50，交叉概率Pc取0.65，變異概率取0.005，終止代數(shù)T取100。權(quán)重因子取100km。

一共求解10次得出的結(jié)果都優(yōu)于節(jié)約法所求得的結(jié)果（79.5km）。且第5次還得到了最優(yōu)解67.5km，其對應(yīng)的配送路徑方案為：1-1-1-0-1-1-1-1-1-0（具體配送路徑為4-7-6-0-2-8-5-3-1）。

參考文獻：

[1]陳國良、王煦法、莊鎮(zhèn)泉等，遺傳算法及其應(yīng)用[M].北京：人民郵電出版社，1996.

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

[3]趙剛，物流運籌[M].成都：四川人民出版社，2002.