郭淑紅　楊曉慧

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

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

中圖分類號(hào)：O29 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-7597（2009）0110046-01

一、引言

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

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

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

二、問題的提出

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

三、問題的分析

為便于討論，對(duì)問題做幾點(diǎn)假設(shè)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五、實(shí)例

某配送中心用2輛汽車對(duì)8個(gè)客戶配送貨物。設(shè)汽車的載量為8×103kg。每次配送的最大行駛距離為40km，配送中心與客戶、客戶與客戶之間的距離及各客戶的需求量見下表。在實(shí)驗(yàn)中采用了以下參數(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，其對(duì)應(yīng)的配送路徑方案為：1-1-1-0-1-1-1-1-1-0（具體配送路徑為4-7-6-0-2-8-5-3-1）。

參考文獻(xiàn)：

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

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

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