一种求解库存路径问题的拉格朗日松弛法

赵媛媛　段倩倩

摘 要： 为了快速解决库存路径问题（Inventory Routing Problem， IRP），提出用松弛与分解结合的拉格朗日松弛算法进行求解。首先对问题进行了详细描述和有效假设，在此基础上，以系统总成本为优化目标，建立了混合整数规划模型。针对此模型，本文先采用拉格朗日松弛算法将IRP分解为2个独立的子问题，然后分别用遗传算法和次梯度算法进行求解，最后通过案例实验表明，与直接求解对偶问题和智能优化算法相比，本文分解算法能在较短的时间内构造一个配送方案，且所求解的质量更好。

关键词： 库存路径问题; 拉格朗日松弛; 遗传算法; 次梯度算法

文章编号： 2095-2163（2021）07-0185-06中图分类号：TP391文献标志码： 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）是供应链管理中的一个二级分销网络，是整合了库存优化成本、运输成本以及运输路径规划的综合优化问题[1-2]。该问题指在供应商管理库存模式下，由一个供应商向多个位置分散的客户提供配货服务，在满足客户库存容量、运输车数量等约束条件下，使系统总成本最小，并最终确定配送数量、配送路线的优化问题。IRP是车辆路径问题（Vehicle Routing Problem， VRP）[3-4]变体，已被证明是NP-hard问题[5-6]，求解比较困难。

近年来，已有不少学者对IRP问题进行研究，秦磊[7]针对易腐蚀产品提出了一种客户需求确定的库存路径问题，目的是制定一套最优的库存策略和补货路径方案，并针对该问题提出了一种模拟退火算法，该算法大大减少了供应链系统的总成本;杨华龙等人[8]研究了异质车队的库存路径配送问题，其中客户需求是不确定的，为了解决此问题，提出了一种改进粒子群算法，并通过实验证明，该算法不仅可以提高运输车的装载率，还可以降低系统的总成本;Singh 等人[9]将工业气体中分配多产品的IRP称为一个混合整数线性规划问题，并针对此问题提出了一种局部搜索启发式算法，该启发式算法是通过增量建模来实现的;Park等人[10]针对单个制造商和多个零售商组成的库存路径问题，提出了一种遗传算法，并通过数值仿真验证了算法的有效性。上述研究多用启发式智能优化算法对库存路径问题进行求解，但当模型中约束条件过多和复杂时，智能优化算法求解NP-hard问题时很难满足所有约束条件，且近似解的质量很难把握，为此研究者将研究转向分解算法。赵达等人[11]为使系统运行成本和运输车数量最小化，建立了随机需求的库存路径问题，针对此问题研究了一种分解算法，求解时将问题分解成几个子问题分别进行求解。Campbell等人[12]为研究同一背景下的库存路径问题，设计了一种基于分解决策集的两阶段方法，并通过仿真试验证明，该方法可以节省大量时间。Agra等人 [13]针对单个产品的海运库存路径问题，提出了一种新的分解算法，这种通过直接将主问题分解为子问题的方法减少了主问题的运行时间，提高了求解效率。Chitsaz等人[14]研究了单个产品分配给多个客户的循环库存路径问题（CIRP），目的是设计一个循环分配的模式为客户配送产品，最终实现最小化车辆运输和库存管理的组合成本，针对模型的求解，将问题分解为路由和调度两个子问题分别求解，实验证明与直接求解相比，这种分解算法可以节省大量时间。分解算法通过将复杂问题分解成子问题来降低求解难度的思想深受深研究者青睐，但是分解的过程一般比较复杂。

通过上述文献的学习，为简化库存路径问题求解的复杂度，本文提出了一种将松弛与分解结合的拉格朗日松弛算法。该算法首先将包含多个决策变量的耦合约束松弛到目标问题中得到对偶问题，然后将对偶问题分解为2个独立的子问题，先用遗传算法单独求解最短路径子问题构造一个配送路径，在此基础上用次梯度算法求解库存决策子问题，实验证明该算法可以加快求解效率，同时得到较好的近似解。

1 库存路径问题建模

1.1 问题描述及假设

IRP问题是一个二级供应链问题，本文研究了其中的一种情况，即由一个配送中心和多个客户组成的一对多（1-N）问题。运输车队由配送中心向各客户运输产品，目的是在运输费用、损失费用和库存成本费用最小的前提下，设计较好的运输线路。

为了得到实际模型，假设：在无限的配送周期内，由一个配送中心向多个客户提供配送服务，且整个分销网络中只对一种产品进行配送;配送过程中允许客户出现缺货现象，但只要发生缺货就会产生缺货损失成本;整个配送过程中忽略装卸货物时间，且配送期间客户不会有新的需求;运送费包括与配送距离有关的运输成本和与配送货物数量有关的运输成本。

1.2 数学模型

（1）索引。i， j分别表示配送中心或客户点编号，i， j=0时，表示配送中心，否则为客户点，0≤i， j≤n;h表示运输车编号，1≤h≤V。

（2）参数。n表示客户点数目;V表示配送点可用货车数目;Bh表示运输车h的最大载量;Q表示配送点可用的库存量; f1i，j表示表示产品从客户点i（或配送中心）到客户点j（或者配送中心），与配送量有关的单位运输成本;f2i，j表示产品从客户点 i （或配送中心）到客户点j（或者配送中心），单位距离运输成本;dij表示产品从客户点i（或仓库）到客户点j（或者仓库）的距离;qi表示客户i对产品的需求量;Hi表示产品在客户i的单位的缺货损失成本;Ci 表示客户i的库存成本。

（3）决策变量。si表示客户i的配货量;xih表示车辆h为客户点i的实际配货量;yijh表示若从客户点 j（或配送中心）到客户点i（或者配送中心）配送的产品由運输车h配送则为1，否则为0;

根据以上问题描述、模型假设、参数及决策变量所作IRP问题模型如：

上述模型中，式（1）目标函数为最小化配送成本、缺货成本和库存成本;式（2）表示运输车必须从仓库出发并最终回到仓库;式（3）和式（4）表示每辆车最多只能拜访每个客户一次;式（5）表示若客户点i到客户点j的产品由运输车h配送，则运输车h总的配送量不能超过其最大载量;式（7）表示总的配送量不能超过配送中心的库存量;式（8）为实际配送量不能超过客户缺货量;式（9）表示配送量不能为负; 式（10）是0-1变量，表示客户点i到客户点j的运输由h完成。

2 基于拉格朗日松弛算法求解库存路径问题

拉格朗日松弛算法是求解组合优化问题最常用的算法，其主要原理是：首先将原问题中影响求解速度的复杂约束松弛到目标函数中得到对偶问题，再根据对偶问题的特性将其分解为几个独立的子问题分别进行求解，最后通过求解对偶问题得到原问题的近似最优解。本文将拉格朗日松弛算法原理应用于库存路径问题的求解，其算法求解框架如图1所示。

2.1 松弛偶合约束

上述IRP模型中，与其他约束不同，约束（5）包含了2个不同的变量属于复杂约束，导致原IRP模型求解困难，为此，引入拉格朗日乘子

子问题P2属于整数规划问题，可以用次梯度算法进行求解。

2.2 可行解构造

由于求解对偶问题时松弛了约束（5），所得对偶问题的解一般为原问题的不可行解，需要根据已知信息来构造可行解，得到原问题的一个上界。其步骤如下：

步骤1 将子问题P1和P2的解作为初始解。

步骤2 对于每一个变量yijh，如果yijh=0，令对应的x'ih=0，如果yijh=1，x'ih=xijh。

步骤3 检验∑ix'ih与Bh的关系，若∑ix'ih≤Bh，保持此运输线，若∑ix'ih>Bh，减少该运输线上客户的配送量，直到∑ix'ih≤Bh。

步骤4 所得解yijh，x'ih即为原问题的一个可行解，将此解带入原问题可得上界UB。

2.3 基于次梯度算法的对偶问题求解

对于拉格朗日对偶问题的求解，使用最多而且比较有效的是次梯度优化算法，其基本步骤是：根据初始化的拉格朗日乘子和已知约束条件，计算出对偶问题的值和相应的决策变量，再根据决策变量得到次梯度，沿着次梯度方向迭代直至找到满足条件的对偶值。

在库存路径问题模型中，用次梯度算法求解拉格朗日对偶问题时，拉格朗日乘子μih（i=1，2，…，n; h=1，2，…，V）更新的方式如下：

但是实际应用中，迭代次数t无法达到无穷大，因此每次迭代过程中确定步长的方法如下：

其中，UBt为当前迭代下的一个上界值;LBt为对偶值;参数β的值为0.2。

2.4 拉格朗日松弛算法步骤

具体算法步骤如下：

步骤1 初始化，令当前迭代次数t=0，拉格朗日乘子μ0ih=0，LB=0。

步骤2 将约束（5）松弛到原问题IP中，将松弛对偶问题分解为2个子问题P1和P2。

步骤3 用遗传算法求解子问题P1，先得到决策变量yijh。

步骤4 用次梯度算法求解子问题P2，得到决策变量xih。

步骤5 把决策变量yijh，xih带入式（19），计算次梯度wt。

步骤6 根据式（18）更新拉格朗日乘子μtih。

步骤7 迭代停止准则以对偶间隙为准。当对偶间隙小于设定值ε时，求解结束，否则t=t+1，回到步骤4。即：

gap≤ε（22）

其中，gap=UBt-LBtLBt，UBt，LBt分别为当前迭代下的上界值和下界值，ε是一个很小的正数。

3 数值仿真实验

3.1 实验数据

假设某配送系统以1个配送中心、15个零售客户组成，配送过程中客户需求不会发生改变。客户的位置坐标在[-50，50]范围内随机产生，客户需求qi由区间[1，50]中产生的离散均匀分布的随机整数，客户的单位缺货成本Hi是由区间[1，10]产生的随机数，具体客户信息见表1。

为了更好地体现算法的性能，仿真结果以10次运行结果的平均值作为最后实验结果。求解模型所用软件是Matlab版本9.0.0.341360 （R2016a），求解器是CPLEX12.8.0.0。

3.2 实验指标与结果分析

本文提出采用遗传算法和次梯度算法分别求解对偶子问题的方法用LRSGA表示，直接用次梯度算法求解对偶问题的求解方式用LRSA表示。为测试本文提出的LRSGA算法在求解库存路径问题上的效果，采用上述客户数为15的配送系统案例进行仿真，分别用LRSA和LRSGA两种算法求解。LRSA算法和LRSGA算法的优劣以下界值质量和CPU运行时间这两个指标来衡量，下界值通过对偶间隙来体现，对偶间隙Gap=UB-LBLB×100%，值越小说明下界值越好，CPU运行时间越少，算法收敛越快。为了更好体现LRSGA算法的性能，引入智能优化算法GA作对比试验，并通过目标值大小和运行时间两方面来做比较分析。

LRSGA和LRSA两种算法的下界值收敛曲线如图2所示，GA、 LRSA和LRSGA三种算法的具体结果值见表2。

由图2可知，LRSA和LRSGA两种算法的下界值最后均能趋于收敛，但本文提出的LRSGA算法能更快趋于稳定，另外从2种算法的曲线图与上界值的关系可以看出，LRSGA算法的曲线图在LRSA算法曲线图的上面，更接近上界值，所以LRSGA算法的目标值质量较好。表2为3种算法的相关结果值，则更能精确表现算法的性能。从表2可以看出：

（1）LRSA和LRSGA两种算法所求近似目标值的质量均比GA算法小。其中，LRSGA算法求得近似值质量最好，其近似解是GA算法的75.28%，其对偶间隙仅是LRSA算法间隙的39.47%。

（2）从CPU运行时间上来看，LRSA和GA两种算法的运行时间相差不大，LRSGA求解所用时间最少，与LRSA和GA算法相比分别节省了70.17%、71.41%的时间，从迭代次数也能看出，与LRSA算法相比，LRSGA算法在第10代就能达到收敛。

LRSGA算法所求得4辆运输车的配送路线及配送量如图3所示。从图3中可以看出，15个客户均能得到有效的配送。

通过算例不难发现，由于LRSGA算法先用遗传算法解决了最短路径子问题得到了各运输车的配送路线，在已知配送路线的前提下，用次梯度算法求解库存决策子问题，在算法迭代过程中，仅需要求一个未知变量就可以获得次梯度，并更新拉格朗日乘子。因此可以简化算法计算的复杂度，并能得到较好的方案。

4 结束语

本文考虑了一种客户地理位置、客户规模、客户需求和配送车辆已知的库存路径问题。并针对此问题建立了一种混合整数规划模型，且提出用拉格朗日松弛算法求解此模型。首先将松弛对偶问题分解为2个子问题，先用遗传算法求解最短路径子问题，构造运输车配送路径方案，其次用拉格朗日次梯度算法求解库存子问题。这种分别独立求解子问题的方式可以降低求解问题的难度，加快计算时间。最后通过具体数值仿真验证了算法的有效性，通过与GA算法和LRSA算法相比，该算法能得到较好的近似解，同时可以加快收敛速度。

参考文献

[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]趙志学，李夏苗. 时变交通下生鲜配送电动车辆路径优化方法[J]. 交通运输系统工程与信息，2020，20（5）：218-225，239.

[4]李红启，陈鋆，赵佳敏. 两级物流网络车辆路径问题研究综述[J]. 供应链管理，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]. 计算机工程与设计，2017，38（2）：424-429.

[8]杨华龙，陆婷，辛禹辰. 基于改进粒子群算法的异质车队二级IRP优化[J]. 计算机工程与应用，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]赵达，马丹祥. 求解随机需求库存—路径问题的分解算法研究[J]. 统计与决策，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.

基金項目： 国家重点研发计划（SQ2019YFB170208）; 上海市青年科技英才扬帆计划（17YF1428100）。

作者简介： 赵媛媛（1993-），女，硕士研究生，主要研究方向：优化调度; 段倩倩（1986-），女，博士，讲师，主要研究方向：优化调度、数学建模及优化算法、非线性规划。

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

收稿日期： 2021-01-02