凌鏡珩

（1.西南交通大學(xué) 交通運(yùn)輸與物流學(xué)院，四川 成都 611756；2.深圳市城市交通規(guī)劃設(shè)計(jì)研究中心，廣東 深圳 518000）

1 引言

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

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

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

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

2 模型建立

2.1 問題描述

由一個(gè)配送中心和多個(gè)客戶組成的倉儲(chǔ)配送系統(tǒng)。該配送系統(tǒng)中，客戶地理位置已知，接收由區(qū)域倉庫中心發(fā)出的多種產(chǎn)品。決策者負(fù)責(zé)決策計(jì)劃期內(nèi)所有種類的產(chǎn)品是否配送、配送數(shù)量、客戶庫存水平、配送路徑等。不同產(chǎn)品的庫存持有成本與缺貨費(fèi)用均不同，但共同存儲(chǔ)在配送中心與客戶中，配送時(shí)也使用同一車隊(duì)進(jìn)行配送，共享車輛容量。

在每一個(gè)計(jì)劃期開始前，先由區(qū)域配送中心對(duì)客戶進(jìn)行配送，再扣除客戶的市場(chǎng)需求。每一種商品的庫存持有成本與缺貨成本是不同的，市場(chǎng)對(duì)每一種商品都有互相獨(dú)立且隨機(jī)的市場(chǎng)需求。計(jì)劃期內(nèi)未被滿足的每一種商品都會(huì)被積壓到下一個(gè)計(jì)劃期并產(chǎn)生缺貨懲罰。

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

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

（2）運(yùn)輸車隊(duì)一個(gè)計(jì)劃期內(nèi)最多進(jìn)行一次以配送中心為起訖點(diǎn)的配送路徑，路徑可包括任意客戶的集合；

（3）不同的商品在客戶中共同存儲(chǔ)，配送時(shí)共享同一運(yùn)輸車隊(duì)的容量限制，不單獨(dú)配送；

（4）所有的配送與裝卸活動(dòng)都可以在一個(gè)計(jì)劃期內(nèi)完成，車輛的每一次配送不會(huì)拖延到下個(gè)計(jì)劃期；

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

（6）在每一個(gè)計(jì)劃期，先有配送中心為客戶補(bǔ)貨，再從客戶的庫存中扣除市場(chǎng)需求的量；

（7）客戶的庫存不滿足需求時(shí)，產(chǎn)生缺貨積壓，積壓記入下一計(jì)劃期，并產(chǎn)生缺貨成本。

2.2 參數(shù)與變量

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

2.3 數(shù)學(xué)模型

根據(jù)以上參數(shù)設(shè)置與模型假設(shè)，以最小化時(shí)間平均下的配送運(yùn)輸費(fèi)用與庫存費(fèi)用為目標(biāo)，建立無限計(jì)劃期下的多商品庫存路徑問題模型：

表1 參數(shù)與變量定義

約束條件：

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

3 求解算法

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

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

采用分支定界的方法對(duì)模型進(jìn)行求解：

（1）將目標(biāo)函數(shù)式（1）與約束條件（2）-（10）組成一個(gè)線性規(guī)劃問題記做LP。對(duì)LP進(jìn)行求解，如果解為整數(shù)解，則是原問題的最優(yōu)解，如果解不是整數(shù)解則進(jìn)行下一步的分支定界。

（2）LP的解作為搜索樹的根節(jié)點(diǎn)，對(duì)出現(xiàn)的第一個(gè)非整數(shù)解，加上約束(11)。將0-1約束代入線性規(guī)劃問題中進(jìn)行重新優(yōu)化，并進(jìn)行計(jì)算。

（3）將根節(jié)點(diǎn)后的每一個(gè)分支表明求解結(jié)果，并表明不同分支結(jié)果的上下界。

（4）如果滿足整數(shù)要求的最優(yōu)解小于前一個(gè)搜索節(jié)點(diǎn)計(jì)算出的下界，則剪除此支并不再考慮。如果大于搜索節(jié)點(diǎn)的下界則重復(fù)步驟繼續(xù)優(yōu)化，直到上下界接近或者無法進(jìn)行分支。

4 算例分析

為了驗(yàn)證模型的有效性，假設(shè)某企業(yè)的配送系統(tǒng)由一個(gè)配送中心與9 個(gè)零售商客戶組成。配送中心對(duì)零售商客戶進(jìn)行某同質(zhì)產(chǎn)品的配送服務(wù)?？蛻舻男枨蠓囊阎母怕史植肌榱烁淤N近實(shí)際情況，算例中假設(shè)客戶的需求服從Poisson 分布。具體客戶信息見表2。

本節(jié)算例采用Matlab 2018a 計(jì)算軟件，使用yalmip 工具箱調(diào)用CPLEX Optimization studio 12.8.0求解器對(duì)該線性混合整數(shù)規(guī)劃問題進(jìn)行求解，求解結(jié)果如下：

表2 客戶基礎(chǔ)信息表

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

圖1 算例計(jì)算結(jié)果與對(duì)比

從圖1的對(duì)比結(jié)果中可以發(fā)現(xiàn)：高服務(wù)水平下的EOQ 算法（服務(wù)水平為95%）的缺貨費(fèi)用較低，接近于零；總體庫存成本與本章算法接近，但是為了保持高服務(wù)水平頻繁配送，運(yùn)輸成本明顯高于本章算法。

低服務(wù)水平下的EOQ算法（服務(wù)水平為75%）因?yàn)檫\(yùn)輸頻率低的原因，運(yùn)輸費(fèi)用較低，但產(chǎn)生了顯著的缺貨費(fèi)用，導(dǎo)致總庫存成本比本章算法與高服務(wù)水平下的EOQ算法分別高出30.82%與29.86%。

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

5 結(jié)論

庫存與路徑問題聯(lián)合優(yōu)化需要考慮庫存容量限制、車輛容量限制等約束條件，在單個(gè)的供應(yīng)商與多個(gè)地理位置分散的客戶組成的物流系統(tǒng)中確定庫存策略、配送策略。本文所建立的混合整數(shù)規(guī)劃模型的求解結(jié)果可以很好地在庫存費(fèi)用與配送頻率之間達(dá)到平衡。聯(lián)合優(yōu)化的結(jié)果比分別對(duì)庫存策略與配送路徑進(jìn)行優(yōu)化的方案更節(jié)省配送系統(tǒng)的總成本。

本文研究還存在一定的不足之處，將作為今后進(jìn)一步研究的方向。在模型的設(shè)計(jì)中為了簡化計(jì)算，未考慮配送中心的庫存容量限制與成本，也沒有動(dòng)態(tài)地對(duì)運(yùn)輸車輛資源進(jìn)行優(yōu)化。如果考慮這些因素，可以讓模型更符合實(shí)際，對(duì)實(shí)際的物流配送系統(tǒng)更有參考價(jià)值。