隨機需求下帶時間窗ＩＲＰ問題的遺傳算法研究

摘要：研究隨機需求條件下帶時間窗的IRP問題的數學模型，并借助遺傳算法來求解這一模型。以某物流公司配送系統為例，獲得了路徑安排和庫存策略的優化目標解。實驗結果表明這不僅能明顯減少迭代次數，而且可以改善優化計算結果。

關鍵詞：遺傳算法；隨機需求；時間窗；IRP

中圖分類號：F019 文獻標識碼：A

Genetic Algorithm Research on Inventory Routing Problem with Time Window Under Stochastic Demand

LV Xiong-wei，SUN Bin-feng，LI Jun

(SouthWest JiaoTong University，Chendu 610012，China)[GK2!2]

Abstract:

This paper presents a mathematical model of stochastic demand inventory routing problem with time windows (IRPTW). A genetic algorithm is introduced to solve the model．Itaims at optimizing the solution to both route arrangement and inventory strategy，by taking a logistic company delivery system for example. The findings show that it can not only reduce the iterations， but also improve the optimization results．

Key words:

一、引言

存貯路徑問題(Inventory Routing Problem，簡稱IRP)主要研究庫存和配送兩個環節同時優化的問題；它針對一個配送中心和若干客戶需求點，確定車輛的最優行駛路徑和各客戶點的庫存補充策略（如配送數量和頻率等）；這是一個典型的NP難題。IRP問題與一般的車輛路徑問題（VRP）^[1]在配送基礎和計劃水平等方面都有很大的差異。對IRP模型和算法的研究已經有了很多成果，但主要研究還是針對確定性需求、有上下界需求的情況；如Ann Campbell等提出了一種兩階段分解算法來求解確定需求性IRP問題。對于隨機需求和帶時間窗的IRP問題研究得很少，目前對隨機需求研究得較多是假設需求服從某種隨機分布(如Wiener 分布)^[2]；這在郵政投遞、火車調度和公交規劃等服務性交通行業應用普遍。

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

二、問題描述和數學模型

隨機需求下的IRPTW問題可以描述為由一個配送中心和多個客戶構成的配送系統，系統中僅考慮單一貨物不允許缺貨發生的情況（含中心和客戶），擁有最大裝載量為q的同一類型車輛k輛，負責對N個客戶進行物流配送作業，客戶i的需求為隨機函數g(i)，i=1，…，N，i=0時表示為配送中心，車輛必須在一定時間范圍[a，b]內到達客戶處，即不早于a 和不晚于b ，求滿足條件的路程最短的車輛行駛路徑和庫存策略。

主要假設如下：

1.在這個由配送運輸中心和多個客戶組成的配送系統中，整個系統只考慮單一品種貨物，從配送中心用車輛將產品按時間范圍要求送至各個客戶點；

2.整個系統充分保證貨物供應，即不允許發生客戶缺貨現象；

3.[JP3]配送運輸中心擁有足夠的庫存以滿足所有客戶的需求，客戶的需求只對其本身的庫存量產生影響；

4.[JP3]中心庫存容量沒有限制，也不考慮其庫存成本；

5.各個客戶的需求是隨機的、相互獨立，沒有銷售出去的貨物產生庫存成本；

6.所有客戶的最大需求值小于單個車輛的容量，即每輛車至少可以服務一個客戶；

7.車輛不能為客戶提供部分服務，當剩余的貨物不能服務于下一個客戶時，必須返回中心重新裝載，回此客戶繼續服務，即不容許“路由失敗”；

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

筆者以這種需求隨機、帶時間窗約束的存貯路徑問題為研究對象，建立優化模型并用遺傳算法求解，以確定配送中心在某一運行周期內的訂貨頻率、訂貨數量以及每個客戶的配送數量和配送路線，目標函數是使總成本(包括配送中心固定訂貨成本、配送中心庫存持有成本、客戶庫存持有成本以及運輸成本)最小。

SC=SC0+∑SCi=∑[DD(]T[]t=1[DD)]h0I0t+∑[DD(]T[]t=1[DD)]∑[DD(]N[]k=1[DD)]hkIkt庫存成本，由配送中心庫存持有成本和客戶庫存持有成本兩部分組成；其中h為單位產品的庫存成本；[JY]（4）

三、隨機需求下帶時間窗IRP問題的遺傳算法

1．構造染色體。定義染色體的編碼方式是利用遺傳算法解決問題前提。在文中的問題求解中，是采用自然數編碼（也叫序然編碼）^[5]。這種編碼方式比較直接，已被廣泛應用于求解TSP、VRP、Flow Shop環境下的調度問題等一些與順序有關地組合優化問題。用矢量(1，2，3，? ，m)表示染色體G，其中元素(基因)m為[1，N]之間互不重復的自然數。隨機產生一組染色體G1、G2、…Gk(其中k為一代種群中的個體數)，Gk各不相同，它為第1代種群。

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

3．自然選擇。采用比例選擇和精華模型相結合的選擇策略，對每代種群的染色體按適應度值排序，將適應度值最大的染色體復制一個直接進入下一代。下一代種群中剩下的k-1個染色體用輪盤選擇法產生。這樣，首先可以保證最優個體可以生存到下一代，既給了適應度較大的個體較大的機會進入下一代，又避免了個體間因適應值不同而被選人下一代的機會懸殊。

4．染色體交叉操作。在每代種群中，以一定的交叉概率對染色體進行交叉重組，是用MX3方法進行交叉操作，兩個父體復合產生一個新個體。這樣既減弱了對群體多樣性的要求，也能有效地避免“早熟收斂”現象。具體的交叉過程為：[JB(]A:2561|7|3849B:2574|1|6938[JB)][FY(]交叉復合[FY）]AB3：2561|4|7389；任意給定兩個互不相同的染色體A和B，隨機產生兩個交叉點，將B染色體的交叉段移到A染色體的對應部位，消去相同項得到一個新個體AB3。

5．染色體變異操作。由于交叉只能對現有基因排列組合，無法產生新的基因；而變異可使搜索跳出局部最優，避免算法早熟。但是變異的可能性較小，所以變異操作只起輔助作用。是按一定概率P對每代種群進行染色體變異，采用的是兩點基因值交換的變異策略。

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

四、實例和比較分析

以四川省某物流公司在全省8個市州的配送系統為例，運用改進后的遺傳算法來計算最優配送路徑，以實現優化配載。相當于8個客戶和1個配送中心，各個客戶的配送量、配送所需時間和各個客戶的時間窗要求已經給定。假定全部采用裝載容量為8t的車輛通過公路運輸完成配送，配送中心與各客戶間的距離(公里)也給定。一代種群中的染色體條數為20，交叉概率為0．75，變異率為0．25，迭代的代數為500。用MATHLAB計算實驗優化結果如下。

車輛1 配送：O-A-B-D-O路途時間為7．5小時(含裝卸時間)，返程時間為6小時，滿足時間窗要求。

車輛2 配送：O-D-O單點配送滿足時間窗要求。

車輛3 配送：O-E-F-O 路途時間為9小時(含裝卸時間)，返程時間為8小時，滿足時間窗要求。

車輛4 配送：O-G-H-O 路途時間為4小時(含裝卸時間)，返程時間為3小時，滿足時間窗要求。

說明：按照24小時計算，0時開始。車輛最大裝載量為8噸，單位噸公里的運輸成本為1。為了便于計算，對隨機配送貨物重量進行入位取整，并每個地方一般至少配送1噸，返空費用每公里為1，固定派車費用為300。

如果不考慮時間窗等限制條件，按路徑0-G-H-E-F-O派車是派車數最少的，但是其總費用為7488。對比結果在滿足時間窗約束的情況下，總費用反而可以節省費用4．65%。

五、結論

通過建立隨機需求下的IRPTW問題模型，在充分考慮客戶需求、庫存要求、時間窗限制和最短路徑等情況下，利用改進遺傳算法對模型進行了求解。并結合四川某物流公司的實際配送情況，借用先進的MATHLAB工具，求得了客戶的最短路徑和最優的配送策略。采用改進遺傳算法求解IRPTW問題的計算結果表明，其比傳統算法能夠獲得更優的結果。

參考文獻:

[1] Tan K，Lee 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] Dantig G，Ramser J . The truck dispatching problem [J]. Management Science， 1959（6）:80 - 91.

[3] 謝秉磊，李 軍．劉建新．有時間約束旅行商問題的啟發式遺傳算法[J]．西南交通大學學報．2001，36(2)：211-213.

[4] 姜大立，李 軍．車輛路徑問題的遺傳算法研究[J]．系統工程理論與實踐，1999，19(6)：40-45.

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

(責任編輯：習文)

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