[摘要] 本文利用遺傳算法求解了一種隨機需求條件下的IRP問題的數(shù)學模型，并以配送系統(tǒng)為例，獲得了路徑安排和庫存策略的優(yōu)化目標解。計算結果表明模型的求解可以改善優(yōu)化計算結果。

[關鍵詞] 遺傳算法 隨機需求 IRP

一、問題提出和數(shù)學模型

隨機需求下的存貯路徑問題(Inventory Routing Problem，簡稱IRP)是針對由一個配送中心和多個客戶構成的配送系統(tǒng)，主要研究庫存和配送兩個環(huán)節(jié)同時優(yōu)化的問題；確定車輛的最優(yōu)行駛路徑和各客戶點的庫存補充策略（如配送數(shù)量和頻率等）；這是一個典型的NP難題。

本文針對這種隨機需求條件下的IRP，建立了以優(yōu)化配送路徑和庫存策略為目標的數(shù)學模型；并借助改進的遺傳算法進行求解，使遺傳算法在隨機需求下IRP問題的求解過程中能自動尋找滿足最低成本要求的最佳庫存策略和最優(yōu)路徑，能有效克服遺傳算法的“早熟性收斂”，得到的優(yōu)化結果也更接近最優(yōu)解。

基本假設：

1.系統(tǒng)只考慮單一品種貨物，從配送中心用車輛將產(chǎn)品按時間范圍要求送至各個客戶點；

2.不允許發(fā)生客戶缺貨現(xiàn)象，客戶的需求只對其本身的庫存量產(chǎn)生影響；

3.客戶的需求是隨機的、相互獨立，不考慮中心庫存成本；

4.每輛車至少可以服務一個客戶，而且不容許“路由失敗”；

5.中心到各客戶和各客戶之間的最短距離已知。

數(shù)學模型表示如下：

(1)

庫存數(shù)量計算；（2）

離開配送客戶的次數(shù)等于到達的次數(shù)； （3）

單次運輸線路的車輛容量限制； （4）

近似于正態(tài)分布計算每輛車的可服務客戶數(shù);（ 5）

:是由結點組成的路線。

為中心到結點的距離，為結點到結點的距離。

（6）

二、基于遺傳算法的隨機需求IRP問題

構造染色體。用矢量(1，2，3，…，m)表示染色體G，其中元素(基因)m為[1，N]之間互不重復的自然數(shù)。隨機產(chǎn)生一組染色體G1、G2、…Gk(其中k為一代種群中的個體數(shù))，Gk各不相同，它為第1代種群。

適應度的計算。對種群中每一個染色體G1、G2、…Gk，在滿足約束條件的情況下求得對應的可行解和目標函數(shù)值TC；若某一染色體對應的是不可行解，則賦予TC為一個很大的整數(shù)M。令其適應度函數(shù)為1／C，則適應度函數(shù)值越大，表明該染色體的性能越好，對應的解就越趨近最優(yōu)解。

染色體交叉變異操作。用MX3方法進行交叉操作，兩個父體復合產(chǎn)生一個新個體。具體的交叉過程為:;任意給定兩個互不相同的染色體A和B，隨機產(chǎn)生兩個交叉點，將B染色體的交叉段移到A染色體的對應部位，消去相同項得到一個新個體AB3。然后按一定概率P對每代種群進行染色體變異，采用的是兩點基因值交換的變異策略。

終止條件。迭代終止的條件是判斷迭代的代數(shù)是否達到指定值。如果達到則停止進化，選擇適應度最大的染色體G所對應的可行解，作為原本文隨機需求下IRP問題的優(yōu)化解。

三、實例分析

以某物流公司在全省8個市州的配送系統(tǒng)為例，運用本文改進后的遺傳算法來計算最優(yōu)配送路徑，以實現(xiàn)優(yōu)化配載。假定全部采用裝載容量為8t的車輛通過公路運輸完成配送，配送中心與各客戶間的距離(公里)也給定。一代種群中的染色體條數(shù)為15，交叉概率為0.7，變異率為0.3，迭代的代數(shù)為600。用MATHLAB計算實驗優(yōu)化結果如下。

車輛1 配送：1-2-3-7-8車輛2配送:4-5-6總成本:1836

四、結論

本文綜合考慮了客戶需求隨機、庫存要求和路徑最短等因素，利用改進遺傳算法對隨機需求下的IRP模型進行了求解。并結合某物流公司的實際配送情況，利用MATHLAB求得了客戶的最短路徑和最優(yōu)的配送策略。計算結果比傳統(tǒng)算法和原來調度方法有明顯改善。

參考文獻:

[1]Tan KLee T:OuK，et a1．A messy genetic algorithm for the vehicle routing problem with window constraints．proceedings of IEEE Congress on Evolutionary Computation，2001(1):679～686

[2]姜大立李軍:車輛路徑問題的遺傳算法研究．系統(tǒng)工程理論與實踐，1999，19(6):40～45

[3]李大衛(wèi)王莉王夢光:遺傳算法在有時間窗車輛路徑問題上的應用.系統(tǒng)工程理論與實踐，1999，19(8):65～69

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