趙媛媛　段倩倩

摘 要： 為了快速解決庫存路徑問題（Inventory Routing Problem， IRP），提出用松弛與分解結(jié)合的拉格朗日松弛算法進(jìn)行求解。首先對問題進(jìn)行了詳細(xì)描述和有效假設(shè)，在此基礎(chǔ)上，以系統(tǒng)總成本為優(yōu)化目標(biāo)，建立了混合整數(shù)規(guī)劃模型。針對此模型，本文先采用拉格朗日松弛算法將IRP分解為2個獨立的子問題，然后分別用遺傳算法和次梯度算法進(jìn)行求解，最后通過案例實驗表明，與直接求解對偶問題和智能優(yōu)化算法相比，本文分解算法能在較短的時間內(nèi)構(gòu)造一個配送方案，且所求解的質(zhì)量更好。

關(guān)鍵詞： 庫存路徑問題; 拉格朗日松弛; 遺傳算法; 次梯度算法

文章編號： 2095-2163（2021）07-0185-06中圖分類號：TP391文獻(xiàn)標(biāo)志碼： A

A Lagrangian relaxation method for Inventory Routing Problem

ZHAO Yuanyuan， DUAN Qianqian

（School of Electronic and Electrical Engineering， Shanghai University of Engineering Science， Shanghai 201620， China）

【Abstract】In order to quickly solve the Inventory Routing Problem， a Lagrangian relaxation algorithm combining relaxation and decomposition is proposed.In the research， the problem is described in detail and valid assumptions of the problem are made. On this basis， the mixed integer programming model is established with the total cost of the system as the optimization goal. According to this model， this paper first uses the Lagrangian relaxation algorithm to decompose IRP into two independent sub-problems， and then Genetic Algorithm and sub-gradient algorithm are used? for solving respectively， finally the case experiment result shows that compared with the direct solving the dual problem and intelligent optimization algorithm， the decomposition algorithm in this paper can construct a distribution plan in a shorter time， and the quality of the solution is better.

【Key words】Inventory Routing Problem; Lagrangian relaxation algorithm; Genetic Algorithm; sub-gradient algorithm

0 引 言

庫存路徑問題（Inventory Routing Problem，IRP）是供應(yīng)鏈管理中的一個二級分銷網(wǎng)絡(luò)，是整合了庫存優(yōu)化成本、運輸成本以及運輸路徑規(guī)劃的綜合優(yōu)化問題[1-2]。該問題指在供應(yīng)商管理庫存模式下，由一個供應(yīng)商向多個位置分散的客戶提供配貨服務(wù)，在滿足客戶庫存容量、運輸車數(shù)量等約束條件下，使系統(tǒng)總成本最小，并最終確定配送數(shù)量、配送路線的優(yōu)化問題。IRP是車輛路徑問題（Vehicle Routing Problem， VRP）[3-4]變體，已被證明是NP-hard問題[5-6]，求解比較困難。

近年來，已有不少學(xué)者對IRP問題進(jìn)行研究，秦磊[7]針對易腐蝕產(chǎn)品提出了一種客戶需求確定的庫存路徑問題，目的是制定一套最優(yōu)的庫存策略和補貨路徑方案，并針對該問題提出了一種模擬退火算法，該算法大大減少了供應(yīng)鏈系統(tǒng)的總成本;楊華龍等人[8]研究了異質(zhì)車隊的庫存路徑配送問題，其中客戶需求是不確定的，為了解決此問題，提出了一種改進(jìn)粒子群算法，并通過實驗證明，該算法不僅可以提高運輸車的裝載率，還可以降低系統(tǒng)的總成本;Singh 等人[9]將工業(yè)氣體中分配多產(chǎn)品的IRP稱為一個混合整數(shù)線性規(guī)劃問題，并針對此問題提出了一種局部搜索啟發(fā)式算法，該啟發(fā)式算法是通過增量建模來實現(xiàn)的;Park等人[10]針對單個制造商和多個零售商組成的庫存路徑問題，提出了一種遺傳算法，并通過數(shù)值仿真驗證了算法的有效性。上述研究多用啟發(fā)式智能優(yōu)化算法對庫存路徑問題進(jìn)行求解，但當(dāng)模型中約束條件過多和復(fù)雜時，智能優(yōu)化算法求解NP-hard問題時很難滿足所有約束條件，且近似解的質(zhì)量很難把握，為此研究者將研究轉(zhuǎn)向分解算法。趙達(dá)等人[11]為使系統(tǒng)運行成本和運輸車數(shù)量最小化，建立了隨機需求的庫存路徑問題，針對此問題研究了一種分解算法，求解時將問題分解成幾個子問題分別進(jìn)行求解。Campbell等人[12]為研究同一背景下的庫存路徑問題，設(shè)計了一種基于分解決策集的兩階段方法，并通過仿真試驗證明，該方法可以節(jié)省大量時間。Agra等人 [13]針對單個產(chǎn)品的海運庫存路徑問題，提出了一種新的分解算法，這種通過直接將主問題分解為子問題的方法減少了主問題的運行時間，提高了求解效率。Chitsaz等人[14]研究了單個產(chǎn)品分配給多個客戶的循環(huán)庫存路徑問題（CIRP），目的是設(shè)計一個循環(huán)分配的模式為客戶配送產(chǎn)品，最終實現(xiàn)最小化車輛運輸和庫存管理的組合成本，針對模型的求解，將問題分解為路由和調(diào)度兩個子問題分別求解，實驗證明與直接求解相比，這種分解算法可以節(jié)省大量時間。分解算法通過將復(fù)雜問題分解成子問題來降低求解難度的思想深受深研究者青睞，但是分解的過程一般比較復(fù)雜。

通過上述文獻(xiàn)的學(xué)習(xí)，為簡化庫存路徑問題求解的復(fù)雜度，本文提出了一種將松弛與分解結(jié)合的拉格朗日松弛算法。該算法首先將包含多個決策變量的耦合約束松弛到目標(biāo)問題中得到對偶問題，然后將對偶問題分解為2個獨立的子問題，先用遺傳算法單獨求解最短路徑子問題構(gòu)造一個配送路徑，在此基礎(chǔ)上用次梯度算法求解庫存決策子問題，實驗證明該算法可以加快求解效率，同時得到較好的近似解。

1 庫存路徑問題建模

1.1 問題描述及假設(shè)

IRP問題是一個二級供應(yīng)鏈問題，本文研究了其中的一種情況，即由一個配送中心和多個客戶組成的一對多（1-N）問題。運輸車隊由配送中心向各客戶運輸產(chǎn)品，目的是在運輸費用、損失費用和庫存成本費用最小的前提下，設(shè)計較好的運輸線路。

為了得到實際模型，假設(shè)：在無限的配送周期內(nèi)，由一個配送中心向多個客戶提供配送服務(wù)，且整個分銷網(wǎng)絡(luò)中只對一種產(chǎn)品進(jìn)行配送;配送過程中允許客戶出現(xiàn)缺貨現(xiàn)象，但只要發(fā)生缺貨就會產(chǎn)生缺貨損失成本;整個配送過程中忽略裝卸貨物時間，且配送期間客戶不會有新的需求;運送費包括與配送距離有關(guān)的運輸成本和與配送貨物數(shù)量有關(guān)的運輸成本。

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

（1）索引。i， j分別表示配送中心或客戶點編號，i， j=0時，表示配送中心，否則為客戶點，0≤i， j≤n;h表示運輸車編號，1≤h≤V。

（2）參數(shù)。n表示客戶點數(shù)目;V表示配送點可用貨車數(shù)目;Bh表示運輸車h的最大載量;Q表示配送點可用的庫存量; f1i，j表示表示產(chǎn)品從客戶點i（或配送中心）到客戶點j（或者配送中心），與配送量有關(guān)的單位運輸成本;f2i，j表示產(chǎn)品從客戶點 i （或配送中心）到客戶點j（或者配送中心），單位距離運輸成本;dij表示產(chǎn)品從客戶點i（或倉庫）到客戶點j（或者倉庫）的距離;qi表示客戶i對產(chǎn)品的需求量;Hi表示產(chǎn)品在客戶i的單位的缺貨損失成本;Ci 表示客戶i的庫存成本。

（3）決策變量。si表示客戶i的配貨量;xih表示車輛h為客戶點i的實際配貨量;yijh表示若從客戶點 j（或配送中心）到客戶點i（或者配送中心）配送的產(chǎn)品由運輸車h配送則為1，否則為0;

根據(jù)以上問題描述、模型假設(shè)、參數(shù)及決策變量所作IRP問題模型如：

上述模型中，式（1）目標(biāo)函數(shù)為最小化配送成本、缺貨成本和庫存成本;式（2）表示運輸車必須從倉庫出發(fā)并最終回到倉庫;式（3）和式（4）表示每輛車最多只能拜訪每個客戶一次;式（5）表示若客戶點i到客戶點j的產(chǎn)品由運輸車h配送，則運輸車h總的配送量不能超過其最大載量;式（7）表示總的配送量不能超過配送中心的庫存量;式（8）為實際配送量不能超過客戶缺貨量;式（9）表示配送量不能為負(fù); 式（10）是0-1變量，表示客戶點i到客戶點j的運輸由h完成。

2 基于拉格朗日松弛算法求解庫存路徑問題

拉格朗日松弛算法是求解組合優(yōu)化問題最常用的算法，其主要原理是：首先將原問題中影響求解速度的復(fù)雜約束松弛到目標(biāo)函數(shù)中得到對偶問題，再根據(jù)對偶問題的特性將其分解為幾個獨立的子問題分別進(jìn)行求解，最后通過求解對偶問題得到原問題的近似最優(yōu)解。本文將拉格朗日松弛算法原理應(yīng)用于庫存路徑問題的求解，其算法求解框架如圖1所示。

2.1 松弛偶合約束

上述IRP模型中，與其他約束不同，約束（5）包含了2個不同的變量屬于復(fù)雜約束，導(dǎo)致原IRP模型求解困難，為此，引入拉格朗日乘子

子問題P2屬于整數(shù)規(guī)劃問題，可以用次梯度算法進(jìn)行求解。

2.2 可行解構(gòu)造

由于求解對偶問題時松弛了約束（5），所得對偶問題的解一般為原問題的不可行解，需要根據(jù)已知信息來構(gòu)造可行解，得到原問題的一個上界。其步驟如下：

步驟1 將子問題P1和P2的解作為初始解。

步驟2 對于每一個變量yijh，如果yijh=0，令對應(yīng)的x'ih=0，如果yijh=1，x'ih=xijh。

步驟3 檢驗∑ix'ih與Bh的關(guān)系，若∑ix'ih≤Bh，保持此運輸線，若∑ix'ih>Bh，減少該運輸線上客戶的配送量，直到∑ix'ih≤Bh。

步驟4 所得解yijh，x'ih即為原問題的一個可行解，將此解帶入原問題可得上界UB。

2.3 基于次梯度算法的對偶問題求解

對于拉格朗日對偶問題的求解，使用最多而且比較有效的是次梯度優(yōu)化算法，其基本步驟是：根據(jù)初始化的拉格朗日乘子和已知約束條件，計算出對偶問題的值和相應(yīng)的決策變量，再根據(jù)決策變量得到次梯度，沿著次梯度方向迭代直至找到滿足條件的對偶值。

在庫存路徑問題模型中，用次梯度算法求解拉格朗日對偶問題時，拉格朗日乘子μih（i=1，2，…，n; h=1，2，…，V）更新的方式如下：

但是實際應(yīng)用中，迭代次數(shù)t無法達(dá)到無窮大，因此每次迭代過程中確定步長的方法如下：

其中，UBt為當(dāng)前迭代下的一個上界值;LBt為對偶值;參數(shù)β的值為0.2。

2.4 拉格朗日松弛算法步驟

具體算法步驟如下：

步驟1 初始化，令當(dāng)前迭代次數(shù)t=0，拉格朗日乘子μ0ih=0，LB=0。

步驟2 將約束（5）松弛到原問題IP中，將松弛對偶問題分解為2個子問題P1和P2。

步驟3 用遺傳算法求解子問題P1，先得到?jīng)Q策變量yijh。

步驟4 用次梯度算法求解子問題P2，得到?jīng)Q策變量xih。

步驟5 把決策變量yijh，xih帶入式（19），計算次梯度wt。

步驟6 根據(jù)式（18）更新拉格朗日乘子μtih。

步驟7 迭代停止準(zhǔn)則以對偶間隙為準(zhǔn)。當(dāng)對偶間隙小于設(shè)定值ε時，求解結(jié)束，否則t=t+1，回到步驟4。即：

gap≤ε（22）

其中，gap=UBt-LBtLBt，UBt，LBt分別為當(dāng)前迭代下的上界值和下界值，ε是一個很小的正數(shù)。

3 數(shù)值仿真實驗

3.1 實驗數(shù)據(jù)

假設(shè)某配送系統(tǒng)以1個配送中心、15個零售客戶組成，配送過程中客戶需求不會發(fā)生改變?？蛻舻奈恢米鴺?biāo)在[-50，50]范圍內(nèi)隨機產(chǎn)生，客戶需求qi由區(qū)間[1，50]中產(chǎn)生的離散均勻分布的隨機整數(shù)，客戶的單位缺貨成本Hi是由區(qū)間[1，10]產(chǎn)生的隨機數(shù)，具體客戶信息見表1。

為了更好地體現(xiàn)算法的性能，仿真結(jié)果以10次運行結(jié)果的平均值作為最后實驗結(jié)果。求解模型所用軟件是Matlab版本9.0.0.341360 （R2016a），求解器是CPLEX12.8.0.0。

3.2 實驗指標(biāo)與結(jié)果分析

本文提出采用遺傳算法和次梯度算法分別求解對偶子問題的方法用LRSGA表示，直接用次梯度算法求解對偶問題的求解方式用LRSA表示。為測試本文提出的LRSGA算法在求解庫存路徑問題上的效果，采用上述客戶數(shù)為15的配送系統(tǒng)案例進(jìn)行仿真，分別用LRSA和LRSGA兩種算法求解。LRSA算法和LRSGA算法的優(yōu)劣以下界值質(zhì)量和CPU運行時間這兩個指標(biāo)來衡量，下界值通過對偶間隙來體現(xiàn)，對偶間隙Gap=UB-LBLB×100%，值越小說明下界值越好，CPU運行時間越少，算法收斂越快。為了更好體現(xiàn)LRSGA算法的性能，引入智能優(yōu)化算法GA作對比試驗，并通過目標(biāo)值大小和運行時間兩方面來做比較分析。

LRSGA和LRSA兩種算法的下界值收斂曲線如圖2所示，GA、 LRSA和LRSGA三種算法的具體結(jié)果值見表2。

由圖2可知，LRSA和LRSGA兩種算法的下界值最后均能趨于收斂，但本文提出的LRSGA算法能更快趨于穩(wěn)定，另外從2種算法的曲線圖與上界值的關(guān)系可以看出，LRSGA算法的曲線圖在LRSA算法曲線圖的上面，更接近上界值，所以LRSGA算法的目標(biāo)值質(zhì)量較好。表2為3種算法的相關(guān)結(jié)果值，則更能精確表現(xiàn)算法的性能。從表2可以看出：

（1）LRSA和LRSGA兩種算法所求近似目標(biāo)值的質(zhì)量均比GA算法小。其中，LRSGA算法求得近似值質(zhì)量最好，其近似解是GA算法的75.28%，其對偶間隙僅是LRSA算法間隙的39.47%。

（2）從CPU運行時間上來看，LRSA和GA兩種算法的運行時間相差不大，LRSGA求解所用時間最少，與LRSA和GA算法相比分別節(jié)省了70.17%、71.41%的時間，從迭代次數(shù)也能看出，與LRSA算法相比，LRSGA算法在第10代就能達(dá)到收斂。

LRSGA算法所求得4輛運輸車的配送路線及配送量如圖3所示。從圖3中可以看出，15個客戶均能得到有效的配送。

通過算例不難發(fā)現(xiàn)，由于LRSGA算法先用遺傳算法解決了最短路徑子問題得到了各運輸車的配送路線，在已知配送路線的前提下，用次梯度算法求解庫存決策子問題，在算法迭代過程中，僅需要求一個未知變量就可以獲得次梯度，并更新拉格朗日乘子。因此可以簡化算法計算的復(fù)雜度，并能得到較好的方案。

4 結(jié)束語

本文考慮了一種客戶地理位置、客戶規(guī)模、客戶需求和配送車輛已知的庫存路徑問題。并針對此問題建立了一種混合整數(shù)規(guī)劃模型，且提出用拉格朗日松弛算法求解此模型。首先將松弛對偶問題分解為2個子問題，先用遺傳算法求解最短路徑子問題，構(gòu)造運輸車配送路徑方案，其次用拉格朗日次梯度算法求解庫存子問題。這種分別獨立求解子問題的方式可以降低求解問題的難度，加快計算時間。最后通過具體數(shù)值仿真驗證了算法的有效性，通過與GA算法和LRSA算法相比，該算法能得到較好的近似解，同時可以加快收斂速度。

參考文獻(xiàn)

[1]SU Zhouxing， L=- Zhipeng， WANG Zhuo， et al. A matheuristic algorithm for the inventory routing problem[J]. Transportation Science， 2020， 54（2）： 330-354.

[2]BERTAZZI L， COELHO L C， De MAIO A， et al. A matheuristic algorithm for the multi-depot inventory routing problem[J]. Transportation Research Part E： Logistics and Transportation Review， 2019， 122（C）： 524-544.

[3]趙志學(xué)，李夏苗. 時變交通下生鮮配送電動車輛路徑優(yōu)化方法[J]. 交通運輸系統(tǒng)工程與信息，2020，20（5）：218-225，239.

[4]李紅啟，陳鋆，趙佳敏. 兩級物流網(wǎng)絡(luò)車輛路徑問題研究綜述[J]. 供應(yīng)鏈管理，2020，1（9）：88-100.

[5]WANG Zelin， PAN Jiansheng. Research on IRP of perishable products based on improved differential evolution algorithm[C]//International Symposium on Intelligence Computation and Applications.? Singapore： Springer， 2019： 497-513.

[6]CHENG Shi， WANG Zelin. Solve the IRP problem with an improved discrete differential evolution algorithm[J]. International Journal of Intelligent Information and Database Systems， 2019， 12（1-2）： 20-31.

[7] 秦磊. 基于模擬退火算法的易逝品庫存路徑問題[J]. 計算機工程與設(shè)計，2017，38（2）：424-429.

[8]楊華龍，陸婷，辛禹辰. 基于改進(jìn)粒子群算法的異質(zhì)車隊二級IRP優(yōu)化[J]. 計算機工程與應(yīng)用，2020，56（22）：272-278.

[9]SINGH T， ARBOGAST J E， NEAGU N. An incremental approach using local-search heuristic for inventory routing problem in industrial gases[J]. Computers & Chemical Engineering， 2015， 80： 199-210.

[10]PARK Y B， YOO J S， PARK H S. A genetic algorithm for the vendor-managed inventory routing problem with lost sales[J]. Expert Systems with Applications， 2016， 53： 149-159.

[11]趙達(dá)，馬丹祥. 求解隨機需求庫存—路徑問題的分解算法研究[J]. 統(tǒng)計與決策，2013（18）：64-68.

[12]CAMPBELL A M， SAVELSBERGH M W P. A decomposition approach for the inventory-routing problem[J]. Transportation Science， 2004， 38（4）： 488-502.

[13]AGRA A， CHRISTIANSEN M， HVATTUM L M， et al. Robust optimization for a maritime inventory routing problem[J]. Transportation Science， 2018， 52（3）： 509-525.

[14]CHITSAZ M， DIVSALAR A， VANSTEENWEGEN P. A two-phase algorithm for the cyclic inventory routing problem[J]. European Journal of Operational Research， 2016， 254（2）： 410-426.

基金項目： 國家重點研發(fā)計劃（SQ2019YFB170208）; 上海市青年科技英才揚帆計劃（17YF1428100）。

作者簡介： 趙媛媛（1993-），女，碩士研究生，主要研究方向：優(yōu)化調(diào)度; 段倩倩（1986-），女，博士，講師，主要研究方向：優(yōu)化調(diào)度、數(shù)學(xué)建模及優(yōu)化算法、非線性規(guī)劃。

通訊作者： 段倩倩Email： dqq1019@163.com

收稿日期： 2021-01-02