基于遺傳算法的隨機需求ＩＲＰ問題研究

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

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

一、問題提出和數學模型

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

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

基本假設：

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

2.不允許發生客戶缺貨現象，客戶的需求只對其本身的庫存量產生影響；

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

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

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

數學模型表示如下：

(1)

庫存數量計算；（2）

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

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

近似于正態分布計算每輛車的可服務客戶數;（ 5）

:是由結點組成的路線。

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

（6）

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

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

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

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

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

三、實例分析

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

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

四、結論

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

參考文獻:

[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]姜大立李軍:車輛路徑問題的遺傳算法研究．系統工程理論與實踐，1999，19(6):40～45

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

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