多商品庫存路徑問題研究

凌鏡珩

（1.西南交通大學 交通運輸與物流學院，四川 成都 611756；2.深圳市城市交通規劃設計研究中心，廣東 深圳 518000）

1 引言

庫存-路徑問題（inventory routing problem，IRP）是整合了庫存管理、車輛路徑以及運輸決策的綜合性優化問題。該問題通常是指在供應商管理庫存（vendor-managed inventory，VMI）模式下，考慮到諸如客戶庫存、運輸車輛容量等約束條件，在單個的供應商與多個地理位置分散的客戶組成的物流系統中，確定庫存策略、配送策略（包括配送數量與路徑決策）的優化問題。

在以往的實際生產經營中，庫存管理環節與運輸環節往往由不同的部門或個人負責。因此，傳統上是單獨研究對庫存管理策略與運輸決策的優化，沒有統籌兼顧。但隨著現代化產品的生命周期變短、更新加快、需求波動復雜等趨勢，供應鏈內的需求信息容易出現傳遞扭曲、變形等問題，從而產生牛鞭效應（Bull-whip effect）。為了解決這個問題，供應商管理用戶庫存策略（Vendor Managed Inventory,VMI）應運而生。VMI 模式以系統、集成的思想去進行庫存管理，削減供應商的生產與分銷成本，整個供應鏈的成本得以降低。對供應商而言，如何對庫存以及運輸這兩個關鍵的物流環節進行有效管理，做出靈活有效率的決策，成為實施VMI戰略的關鍵。

對IRP問題的研究起源于車輛-路徑問題（VRP，vehicle-routing problem）的變種。該問題最早由Bell等[1]在1983年研究在滿足客戶庫存水平、計算運輸成本、需求隨機的情況下的路徑規劃問題。Andersson等[2]、Coelho 等[3]追溯了過去 30年間 IRP 問題的研究成果。Campbell和Savelsbergh[4]建立了一個使用供應商管理庫存的模型，該模型將顧客的補貨與庫存控制交給供應商管理，并采用兩階段法對該模型求解；Moin，Salhi，and Aziz[5]研究了多個供應商對單個客戶配送多種商品的問題，采用了遺傳算法；Coelho and Laporte 等[6]使用精確算法求解了多種商品多車輛的IRP 問題。在國內，傅成紅[7]、段鳳華[8]兩人從不同的方面，在分析庫存路徑問題相關文獻的基礎上，給出了IRP 的一般化定義，并對其進行分類。趙達等[9]以隨機需求下的IRP問題為研究對象，提出了一種基于馬爾科夫決策過程與修正的C-W節約算法的啟發式分解算法。魏江寧，夏唐斌[10]采用模擬退火的啟發式算法計算每個時間段客戶的訂貨量，再分配車輛路徑；張弈[11]研究了多周期易腐品的IRP問題；朱桂陽[12]研究了在考慮缺貨的情況下，有不同腐敗速率的易腐品IRP問題。

庫存-路徑問題將原本分別優化的庫存管理，運輸決策兩者進行聯合優化。庫存管理的核心是在保證安全庫存的情況下盡量減少庫存積壓，而運輸決策卻要求盡可能的減少運輸成本，兩者存在著“效益背反（Trade-off）”的關系。只有通過聯合優化，才能從整體上控制供應鏈的成本。對庫存-路徑問題的研究，有助于在生產經營活動中實施VMI模式，協調整體供應鏈，降低總成本，為供應鏈一體化做好準備。由于IRP問題在一定程度上可視為VRP問題的延伸，其數學優化模型往往是非線性的混合整數優化模型，求解難度較大，所以對IRP問題的研究，除了在實際生產經營中有多種應用場景，還具有理論價值。

2 模型建立

2.1 問題描述

由一個配送中心和多個客戶組成的倉儲配送系統。該配送系統中，客戶地理位置已知，接收由區域倉庫中心發出的多種產品。決策者負責決策計劃期內所有種類的產品是否配送、配送數量、客戶庫存水平、配送路徑等。不同產品的庫存持有成本與缺貨費用均不同，但共同存儲在配送中心與客戶中，配送時也使用同一車隊進行配送，共享車輛容量。

在每一個計劃期開始前，先由區域配送中心對客戶進行配送，再扣除客戶的市場需求。每一種商品的庫存持有成本與缺貨成本是不同的，市場對每一種商品都有互相獨立且隨機的市場需求。計劃期內未被滿足的每一種商品都會被積壓到下一個計劃期并產生缺貨懲罰。

為了方便模型的建立與求解，在實際情況的基礎上做出如下假設：

（1）因配送中心的庫存持有成本遠小于客戶，不考慮配送中心的庫存容量限制與成本；

（2）運輸車隊一個計劃期內最多進行一次以配送中心為起訖點的配送路徑，路徑可包括任意客戶的集合；

（3）不同的商品在客戶中共同存儲，配送時共享同一運輸車隊的容量限制，不單獨配送；

（4）所有的配送與裝卸活動都可以在一個計劃期內完成，車輛的每一次配送不會拖延到下個計劃期；

（5）忽略不同計劃期下的路況差異，配送路況是恒定的；

（6）在每一個計劃期，先有配送中心為客戶補貨，再從客戶的庫存中扣除市場需求的量；

（7）客戶的庫存不滿足需求時，產生缺貨積壓，積壓記入下一計劃期，并產生缺貨成本。

2.2 參數與變量

根據以上問題描述與模型假設，模型涉及到的參數與變量見表1。

2.3 數學模型

根據以上參數設置與模型假設，以最小化時間平均下的配送運輸費用與庫存費用為目標，建立無限計劃期下的多商品庫存路徑問題模型：

表1 參數與變量定義

約束條件：

式（1）為目標函數為最小化時間平均下的配送運輸費用與庫存費用；式（2）表示在客戶節點內運輸車輛進出順序約束，任意運輸車輛進入該客戶點，也需要從該點離開；式（3）是度約束，如果該客戶節點被配送，該節點的度為2，保證該節點在計劃期內只被配送一次，反映了車輛運輸的變量與客戶配送變量之間的約束關系；式（4）是子回路消除約束（subtour elimination constraints），保證配送路徑中不存在子回路；式（5）是庫存的更新約束，表示現計劃期的庫存等于上一計劃期的庫存減去該計劃期的客戶需求量加上該計劃期的配送量；式（6）、（7）是客戶庫存約束，限制了客戶庫存非負并且小于等于庫存容量；式（8）表示對客戶的單次配送量小于庫存容量的剩余空間；式（9）表達客戶配送量與對客戶是否配送0-1變量之間的約束關系，不對客戶進行配送，則配送量為零；式（10）表示配送中心不發出配送車輛時，所有客戶的配送量為0；式（11）表示配送量的非負性；式（12）、（13）聲明了變量屬于0-1變量。

3 求解算法

在客戶需求隨機的情況下，無法預測計劃期內的客戶需求，所以此處采用兩階段法對該模型進行求解。第一階段是根據客戶需求服從的隨機概率分布、單位庫存持有費用、單位缺貨成本來確定（s，S）補貨策略中各個客戶的最優訂貨點、最大庫存水平。Zheng和Federgruen[13]所提出的在隨機需求下計算（s，S）庫存策略的算法是被廣泛使用的一種標準算法，本文也采用該算法計算各客戶的最優訂貨點與最大庫存水平。

第二階段是根據（s，S）補貨策略來計算計劃期內給各客戶的配送數量、期望缺貨數量。將原問題簡化成一個車輛路徑問題來計算給各客戶的配送路徑。該問題在小規模的情況下可作為一個線性的混合整數規劃問題進行求解。

采用分支定界的方法對模型進行求解：

（1）將目標函數式（1）與約束條件（2）-（10）組成一個線性規劃問題記做LP。對LP進行求解，如果解為整數解，則是原問題的最優解，如果解不是整數解則進行下一步的分支定界。

（2）LP的解作為搜索樹的根節點，對出現的第一個非整數解，加上約束(11)。將0-1約束代入線性規劃問題中進行重新優化，并進行計算。

（3）將根節點后的每一個分支表明求解結果，并表明不同分支結果的上下界。

（4）如果滿足整數要求的最優解小于前一個搜索節點計算出的下界，則剪除此支并不再考慮。如果大于搜索節點的下界則重復步驟繼續優化，直到上下界接近或者無法進行分支。

4 算例分析

為了驗證模型的有效性，假設某企業的配送系統由一個配送中心與9 個零售商客戶組成。配送中心對零售商客戶進行某同質產品的配送服務。客戶的需求服從已知的概率分布。為了更加貼近實際情況，算例中假設客戶的需求服從Poisson 分布。具體客戶信息見表2。

本節算例采用Matlab 2018a 計算軟件，使用yalmip 工具箱調用CPLEX Optimization studio 12.8.0求解器對該線性混合整數規劃問題進行求解，求解結果如下：

表2 客戶基礎信息表

算例以10 個計劃期為一組，計算了總計100 個計劃期下的庫存路徑配送方案，并以每10 個計劃期一組的平均值與采用EOQ經濟訂購批量方法的解決方案進行了對比，具體如圖1所示。

圖1 算例計算結果與對比

從圖1的對比結果中可以發現：高服務水平下的EOQ 算法（服務水平為95%）的缺貨費用較低，接近于零；總體庫存成本與本章算法接近，但是為了保持高服務水平頻繁配送，運輸成本明顯高于本章算法。

低服務水平下的EOQ算法（服務水平為75%）因為運輸頻率低的原因，運輸費用較低，但產生了顯著的缺貨費用，導致總庫存成本比本章算法與高服務水平下的EOQ算法分別高出30.82%與29.86%。

本章算法在庫存成本與配送費用之間找到了一個平衡：其缺貨成本位于兩種EOQ算法之間，運輸成本也小于高服務水平的EOQ算法但大于低服務水平的EOQ 算法。在算例的100 個計劃期內，其總的庫存運輸費用分別比高、低服務水平的EOQ 算法要少5.3%與12.2%。

5 結論

庫存與路徑問題聯合優化需要考慮庫存容量限制、車輛容量限制等約束條件，在單個的供應商與多個地理位置分散的客戶組成的物流系統中確定庫存策略、配送策略。本文所建立的混合整數規劃模型的求解結果可以很好地在庫存費用與配送頻率之間達到平衡。聯合優化的結果比分別對庫存策略與配送路徑進行優化的方案更節省配送系統的總成本。

本文研究還存在一定的不足之處，將作為今后進一步研究的方向。在模型的設計中為了簡化計算，未考慮配送中心的庫存容量限制與成本，也沒有動態地對運輸車輛資源進行優化。如果考慮這些因素，可以讓模型更符合實際，對實際的物流配送系統更有參考價值。