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

摘要：存貯路徑問題針對當前供應鏈條件下庫存控制與運輸調度問題分別研究的現狀，將二者整合系統加以分析；在分析現有問題求解方法的基礎上，針對多周期隨機需求IRP問題提出了基于遺傳算法的求解思路，利用二進制編碼處理零售商的庫存策略。正交試驗驗證了算法的有效性，得到客戶需求、運輸車輛等相關因素不同程度的影響最優補貨策略，從而有效求解多周期IRP問題。

關鍵詞：存貯路徑問題；遺傳算法；多周期；隨機需求

中圖分類號：F224．9 文獻標識碼：A

Study on the IRP with Multi-period and Stochastic Demand Based on Genetic Algorithms

SUN Bin-feng， LV Xi-ong-wei， LI Jun

(School of Economics and Management， Southewest Jiaotong University， ChengDu， 610031， China)

Abstract:

The inventory routing problem refersto the inventoryand transportation control in uniform system under the traditional supply chain management. This paper focuses on the inventory routing problem with stochastics demand and multi-period time， and designs GA arithmetic to set up the mathematics model. It shows its reasonable results by anglicizing the orthogonal test.It also finds in the test thatcustomer demands， delivery vehicles and lead time affect the decision of the optimal delivery policies.

Key words:inventory routing problem; genetic algorithms; multi-period; stochastic demand

一、引言

庫存控制與運輸調度是運籌學研究的經典問題，目前的文獻大多將二者作為單獨的問題分別進行研究。存貯路徑問題(Inventory Routing Problem， IRP)則將庫存與運輸兩個相互影響的因素集成在一個問題中系統地加以分析，考慮由一個配送中心和若干個零售商組成的二階配銷系統，在給定的補貨周期內確定零售商的庫存策略及車輛的配送方案，實現系統總運行成本(庫存保管費用，缺貨損失成本，運輸變動成本等)極小。在供應鏈管理思想普遍地為人們接受的今天，尤其是供應商管理庫存(Vendor Managed Inventory， VMI)方法在各行各業的廣泛應用^{[2-5; 7; 10; 11; 13]}，IRP問題的研究更顯示出它的應用價值，不僅能在監控客戶庫存水平的基礎上制定具有實際價值的作業計劃，更能實現供需雙方雙贏(Win-Win)的局面。

二、文獻回顧及問題描述

（一）文獻回顧

IRP問題最優策略的制定需要將系統內零售商的補貨時間、補貨數量與車輛配送路線聯合考慮，是典型的NP難題^[8]，涉及到經濟學、運籌學、組合優化、運輸管理與物流科學等眾多學科。兩階段算法^{[6; 11]}是處理該類問題常見的啟發式方法，即將原問題分解成庫存分配問題和路徑問題加以求解，在取得初始可行解的基礎上進行路線間的零售商交換，實現目標值的改進。Anily和Federgruen^[1]采用固定分區準則(Fixed Partitiion Policies， FPP)首先將零售商按照地理位置或需求特性進行分組，然后在組內求解一個履行商問題(Travel Salesman Problem， TSP)。Roundy^[9]提出power-of-two客戶補貨策略，以某客戶補貨時間間隔為基準，假定其它客戶的補貨周期為該基準間隔的2的冪倍，設計啟發式算法進行求解。

現有IRP問題的求解方法在處理零售商庫存的時候多采用“零庫存”思想?？紤]到車輛配送成本的影響，零售商的庫存策略需要從系統整體上進行考慮，因此本文在分析多周期隨機需求IRP問題的基礎上，提出基于遺傳算法^[16](Genetic Algorithms， GA)的求解思路，利用二進制編碼處理零售商的庫存策略，并設計正交試驗，分析需求、庫存和運輸等相關因素對最優補貨策略的影響。

（二）問題描述

考慮由1個配送中心和N個零售商組成的二階配銷系統。配送中心負責零售商的庫存管理，但不考慮配送中心庫存相關成本。零售商庫存容積C_i，客戶需求概率密度為fi(x)，均值方差已知；允許缺貨，但要付出一定的缺貨損失；在周期t內，Ii(t)表示期初庫存；配送中心給該零售商的補貨量為R_i(t)，零售商實際需求為D_i(t)。配送中心擁有K輛車，載重能力為Q，車輛固定出車成本為g_k，負責零售商的產品配送。試確定計劃期T內零售商的庫存策略及配送中心運輸方案。

假設：（1）零售商采用（t_i，R_i）^[14]庫存策略；（2）零售商之間需求相互獨立；（3）系統外部供應商供給能力無限；（4）零售商初始庫存Ii(0)=R_i;（5）訂貨提前期LT_i固定。

三、系統分析與模型建立

（一）零售商庫存成本模型

通過對系統進行分析，不難發現在不考慮配送中心庫存相關成本的條件下，系統庫存成本是由所有零售商在計劃期內產品的保管與缺貨造成的損失構成的。

零售商i周期t的庫存成本可以表示為：

（二）配送車輛運輸模型

當確定了零售商i周期t內補貨量R_i(t)之后，配送車輛運輸模型可以用VRP問題^[12]進行求解。為構造數學模型方便，將配送中心編號為0。定義變量如下：

其中，約束錯誤！未找到引用源。使得車輛承載的補貨量不大于其容積；約束錯誤！未找到引用源。錯誤！未找到引用源。確保每個客戶在周期內最多只能被訪問一次；約束錯誤！未找到引用源。錯誤！未找到引用源。保證每輛車的配送路線不出現回路。

（三）系統成本模型

約束錯誤！未找到引用源。錯誤！未找到引用源?？傻谜麄€IRP問題研究的二階配銷系統總成本表達式：

約束條件為錯誤！未找到引用源。-錯誤！未找到引用源。錯誤！未找到引用源。-錯誤！未找到引用源。

四、基于GA的算法設計

在配送中心監控系統內各零售商庫存水平的基礎上，零售商的庫存策略主要確定補貨時間和數量。針對研究問題周期特性，筆者在遺傳算法(Genetic Algorithms， GA)的基礎上進行算法設計。

（一）算法流程

步驟1：初始化。按照設定的零售商庫存策略編碼規則(見3．2)生成初始種群。

步驟2：從種群中選擇某一零售商策略集作為當前研究對象。

步驟3：在計劃期[1，T]內，根據庫存策略，在客戶需求變動的影響下，順序生成多個補貨任務，包括時間、數目及對應零售商三大屬性值。

步驟4：對于時間屬性值相同的補貨任務，由車輛負責完成補貨任務的分配，并執行。

步驟5：計算在該策略集下計劃期T內的庫存與運輸費用總和，將其作為適應函數值賦予當前策略集。

步驟6：重復步驟Step2-Step5，直至當前種群內所有策略集都被試運行為止。

步驟7：利用遺傳算法，在保有一定數量優秀補貨策略的基礎上產生新的種群，重復步驟Step2-Step6直至到達最大迭代次數；輸出當前最優補貨策略。

（二）編碼規則

遺傳算法進化過程是建立在編碼規則基礎上的，編碼的優劣直接影響到算法的性能。筆者采用二進制方法對零售商庫存策略進行編碼，利用二進制編碼快速的搜索能力尋找最優解。為了能讓零售商的庫存策略在進貨過程中盡可能多的產生種群，將系統內零售商庫存策略（t，R）同時編入一條染色體中，具體操作如下：

1.首先格式化補貨周期，設定LenL個數字表示染色體中的補貨周期，它滿足以下要求:2LenL≤T≤2LenL+1，顯然零售商在補貨周期T至少完成一次補貨。

2.最大補貨量R可以用LenR個數字表述，其中2LenR≤C≤2LenR+1，C為零售商庫存容積。

3.因此，系統零售商庫存策略集合可以表示一條由N組上述編碼數列組成的染色體。

假設系統內包括3家零售商，庫存策略為(4，11)、（2，3）、(3，10)，則對應一條染色體：100 1011 10 11 11 1010。當然在具體算法實現時，中間是沒有空格的。

（三）運輸調度

筆者側重點在于對零售商庫存策略的確定，對于配送車輛運輸調度計劃可以采用Clarke-Wright提出的節約啟發式算法進行處理。在文獻[12]的提出的節約啟發式算法基礎上進行了修改，增加了車輛運載能力 的約束。

五、試驗仿真設計與分析

（一）試驗參數設計

考慮到一個由1個配送中心和10個零售商組成的二階配送系統，各節點間距如表1所示；各零售商的年需求服從指數分布，運輸費用為1元/公里，車輛固定費用為1000元/次。在實驗設計中，筆者設計了4類不同控制參數以分析其對最終補貨策略的影響，其中每類參數分別設置3個不同水平。如果各種不同的水平搭配，需要生成81種組合試驗環境。為選出具有代表性試驗環境作測試，選擇正交表L₉(3₄)^[15]，共計9種組合試驗環境。每種組合執行1年(1天為1個補貨周期)，利用前文闡述方法計算得到補貨策略和對應的庫存與運輸成本。為獲得每一組試驗穩定的目標值，共運行100次，取其平均值為該組合對應的實驗觀察值。具體控制參數設計見表2。

(二)仿真結果分析

表3給出了零售商在不同組合試驗環境下的補貨策略、成本及服務水平，其中服務水平不同于教材中的定義，它是客戶需求的產品總量與補貨量之間的比值。通過對該表的分析，可以得到下面重要的研究結論：[LM]

1.運輸車輛的規格能降低系統總成本。由組(E1、E4、E7)，(E2、E5、E8)和(E3、E6、E9)可以發現車輛容積的增加能調整零售商的補貨策略，有效利用運能進行聯合配送，以降低整個系統的成本。

2.客戶需求是影響系統成本的關鍵因素。從表3可以知道，隨著客戶需求變異系數的增大，零售商庫存策略中的庫存最大值R也逐漸增大，以消除變動需求帶來的影響，增加了系統庫存成本。

同時，也能從實驗結果中看出客戶需求變異率也影響著零售商的服務水平。

3.訂貨提前期影響著零售商的服務水平。從這9種組合試驗環境中可以發現，提前期為2天的(E2、E6、E7)和提前期為3天的(E3、E4、E8)的客戶服務水平是相對提前期為1天的組合要低一些。通過察看提前期為3天的組合，它又明顯低于提前期為2天的組合，所以服務水平的高低與訂貨提前期的長短有絕對的關系。

4.單位保管費用與缺貨損失比值越低，零售商的庫存成本越會增加。從表3中可以發現，缺貨損失成本越大，零售商存放足夠的庫存就能滿足客戶的需求，從而降低系統的總成本。

5.庫存與運輸的集成能極大的降低系統總成本。IRP問題研究的是在庫存與運輸的整合條件下的最優補貨策略，從實驗結果中可以得到：如果將庫存與運輸分別考慮，單獨為每一個零售商進行配送，顯然產生的運輸成本高于集成后的運輸成本。

六、小結與展望

筆者利用二進制編碼處理零售商的補貨策略，設計了基于遺傳算法的多周期、隨機需求IRP問題的求解步驟。正交試驗結果表明，該方法能夠得到零售商最優補貨策略，從而有效求解多周期IRP問題。同時從設計的多種試驗組合中得到客戶需求變異率、采購提前期、運輸容積等因素對補貨策略的選擇有著十分重要的影響。

筆者在設計與選擇編碼時，盡管能滿足Balakrishman等提出的完全性、緊致性和可擴展性等要求^[16]，但存在產生無效染色體的可能性，如在較差、變異時導致基因對應的補貨策略t或R為0的情況。對于這種情況，筆者采取的是將其拋棄處理，因而存在著改進編碼的空間。

參考文獻：

[1] Anily， Shoshana， Federgruen， Awi. One Warehouse Multiple Retailer Systems with Vehicle Routing Costs[J]. Management Science. 1990，36(1):92-114.

[2] Baita， Flavio， Ukovich， Walter， Pesenti， Raffaele等. Dynamic Routing-and-Inventory Problems: A Review[J]. Transportation Science. 1998，32(8):585-598.

[3] Daganzo， C. F.， F.， Newell G. Physical Distribution from a Warehouse: Vehicle Coverage and Inventory Levels[J]. Transportation Research: Part B. 1985，19:397-407.

[4] Dror， Moshe， Ball， Michael， Golden， Burce L. A Computational Comparison of Algorithms for the Inventory Routing Problem[J]. Annals of Operations Research. 19854:3-23.

[5] Federgruen， Awi， Zipkin， Paul H. Allocation Policies and Cost Approximations for Multilocation Inventory Systems[J]. Naval Research Logistics. 1984，(31):97-129.

[6] Federgruen， Awi， Zipkin， Paul H. A Combined Vehicle Routing and Inventory Allocation Problem. Operation Research[J]. 1984，32(5):1019-1037.

[7] Herer， Yale， Levy， Roberto. The Metered Inventory Routing Problem， an Integrative Heuristic Algorithm[J]. International Journal of Production Economics. 1997，51:69-81.

[8] Reiman， Martin I.， Rubio， Rodrigo， Wein， Lawrence M. Heavy Traffic Analysis of the Dynamic Stochastic Inventory-Routing Problem[J]. Transportation Science. 1999，33(4):361-380.

[9] Roundy， Robin. 98%-Effective Integer-Ratio Lot-Sizing for One-Warehouse Multi-Retailer System[J]. Management Science. 1985，31(11):1416-1429.

[10] Viswanathan， S.， Mathur， Kamlesh. Integrating Routing and Inventroy Decisions in One-Warehouse Multiretailer Multiproduct Distribution Systems[J]. Management Science. 1997，43(3):294-312.

[11] Wendy， W. Qu， Bookbinder， James H.， Iyogun， Paul. An Integrated Inventory-Transportation System with Modified Periodic Policy for Multiple Products[J]. European Journal of Operational Research. 1999，11(5):254-269.

[12] 李軍， 郭耀煌. 物流配送車輛優化調度理論與方法[M].北京：中國物資出版社， 2001.

[13] 劉奕青. 自動販賣機存貨途程問題之研究[D]. 私立元智大學工業工程與管理研究所. 2003.

[14] 馬士華， 林勇， 陳志祥. 供應鏈管理[M].北京：機械工業出版社， 2000.

[15] 唐煥文， 賀明峰. 數學模型引論[M]. .北京：高等教育出版社， 2001.

[16] 王小平， 曹立明. 遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社， 2002.

（責任編輯：呂洪英）

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>