[摘 要] 我們在物流配送系統的研究中，對物流配送的數學模型以及所采用的算法進行了深入的探討，并取得了一定的成果。遺傳算法的改進，一定程度上避免了早熟現象的發(fā)生，提高了遺傳算法用于求解物流配送問題的效率。

[關鍵詞] 物流配送 遺傳算法 早熟 種群

物流配送是指按客戶的訂貨要求，在配送中心進行分貨、配貨，并將配好的貨物及時送達客戶手中。目前我國大部分物流配送企業(yè)，仍依賴人工經驗采用人工安排的方式，從而導致企業(yè)運輸資源無法充分利用，增加了企業(yè)的運行成本或者根本無法滿足客戶的要求，從而限制了物流配送企業(yè)的進一步發(fā)展。對物流配送優(yōu)化問題進行深入研究，建立即時反映客戶需求的自動化車輛調度及路線安排系統，是提升服務質量、提高資源利用率、降低企業(yè)成本的重要課題。

對一個大型配送中心來講，客戶數量往往很多，要精確計算最優(yōu)配送路徑是一件非常困難的事，現在有人利用遺傳算法來求解配送路徑優(yōu)化問題，已經取得了一些研究成果，但實際應用卻不是十分的理想，究其原因，主要是由于傳統的遺傳算法，存在著局部搜索能力不強，容易出現早熟而造成的。為了提高遺傳算法的搜索能力，避免在算法進化的早期出現收斂，文章對傳統的遺傳算法進行了改進，經大量的實驗表明:改進的遺傳算法較傳統的遺傳算法在物流配送優(yōu)化中，求解效率有了非常明顯的提高，完全能適應網絡配送的要求。

一、數學模型

設配送中心有m臺相同的配送車輛要向n個客戶配送貨物，客戶i到客戶j的距離為dij，客戶i到配送中心的距離為di0，客戶i的需求量為qi，車輛的最大載重量為Z，最大行駛距離為D，最大裝載體積為V，成本為C0+kx(其中x為距離），按費用最低為優(yōu)化目標，其數學模型為：。

約束條件:(1)每臺配送車輛的最大行駛距離不能超過D;(2)每臺配送車輛的最大裝載體積不能超過V;(3)配送車輛總數不能超過m。

二、改進的遺傳算法

1.遺傳算法

將每個客戶按十進制從1到n進行編號，隨機對換編號的位置，組成初始群體，計算適應度時，需要在編碼的開始和結束位置插入0，并在編碼之間按車輛的載重量插入若干0，其中0表示配送中心。遺傳運算分別采用聯賽選擇，循環(huán)交叉(CX)和對換變異。

2.遺傳算法的改進

定義1:進化的初期，算法的主要任務是全局尋優(yōu)，稱這個時期為尋優(yōu)期。進化的后期，算法的主要任務是局部收斂，稱這個時期為收斂期。尋優(yōu)期一般為總進化代數的三分之二，收斂期一般為總進化代數的三分之一。

定義2:設個體A=X1，X2，…，Xn-1，Xn，稱A’=Xn，Xn-1，…，X2，X1為A的逆序。

改進的遺傳算法在尋優(yōu)期采用較大的交叉和變異概率，在收斂期采用較小的交叉和變異概率。由于交叉和變異概率只與遺傳代數有關，因此不會影響算法的效率，同時也能較好的抑制早熟現象的發(fā)生。

交叉運算前，先要對種群兩兩配對，如果將兩個相同的個體進行配對，那么交叉運算就失去了作用。改進的遺傳算法為了避免這種情況的發(fā)生，先對種群進行試配對，若在某次試配中，經幾次試配對均不成功，可重新產生一個新個體，從新個體以及新個體的逆序中選擇一個適應度高的個體來替代其中的一個個體，這樣可以保證每對個體它們的基因物質不會完全相同。

出現早熟的原因往往是由于種群中出現了某些超級個體，隨著模擬生物演化過程的進行，這些超級個體的基因物質很快占據了種群的統治地位，導致種群中由于缺乏新鮮的基因物質而不能找到全局最優(yōu)值。改進的遺傳算法在進化的過程中不斷用一些新鮮的個體來替代適應度低的個體，使得種群中始終含有新鮮的基因物質，不至于算法過早收斂，每個新個體可從隨機產生的個體及它的逆序中選擇一個適應度高的個體。在尋優(yōu)期增加的新個體的數量可適當多些（一般為種群的20%左右)，促使算法盡快收斂，在收斂期加入的新個體的數量可適當少些(一般為種群的5%左右）或不再增加新個體。

三、仿真實驗

實驗數據來自文獻的實例2，變異概率為0.01，交叉概率為0.8，初始群體規(guī)模為80，總進化代數為200，共進行了100次實驗。

從表中可以看到，改進的遺傳算法，在不降低速度的前提下，每次實驗基本都可以求出優(yōu)秀解，說明經改進的遺傳算法對物流配送問題的求解能力有了很大程度的提高。

四、結束語

遺傳算法作為一種優(yōu)化算法有著廣泛應用前景，但同時也存在著很多有待解決的問題。文章針對傳統的遺傳算法提出的幾項改進措施，一定程度上克服了早熟現象，增強了對物流配送問題的求解能力。文章作為基本遺傳算法的改進設計，他的優(yōu)劣性還需要在實踐中進一步的檢驗。

參考文獻:

[1]閻 慶 鮑遠律:新型遺傳模擬退火算法求解物流配送路徑問題[J].計算機應用， 2004，24(S1) 261～263

[2]郎茂祥 胡思繼:用混和遺傳算法求解物流配送路徑優(yōu)化問題的研究[J].中國管理科學，2002，10(5).51～56

[3]陳國良 王熙法等:遺傳算法及其應用[M].北京:人民郵電出版社，2001年2月76～143

[4]何 信:多目標物流配送路經優(yōu)化聚類-遺傳混合算法[J].商場現代化，2006 8(上旬刊)總第475期120～121

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”