物流包装租赁系统配送库存路径模型与算法

李家斌，何世伟，刁丹丹，靳国伟，郭小乐

1.河南工程学院 商学院，郑州451191

2.北京交通大学 综合交通运输大数据应用技术交通运输行业重点实验室，北京100044

3.郑州科技学院 外国语学院，郑州450064

在我国，各行各业普遍在生产和流通过程中使用了大量的一次性纸箱、铁桶、木箱等物流包装，这种落后的包装使用方式不仅成为社会环境的负担，也造成了巨大的资源和成本的浪费。发展物流包装租赁共享系统是解决这一问题的有效手段。

目前在我国市场上，已有多个物流包装租赁系统，如中包精力、邦臣、招商路凯、无锡美捷、箱箱共用等，但由于我国的物流包装租赁系统刚起步，还存在着服务站点和网络不完善，标准化不足，空容器派送、回收调度复杂以及容器维修程序繁琐，有关政策缺失等问题[1]。物流包装租赁系统建立以后，对空包装的合理分布以及对空包装的配送与回收的集成优化问题——库存路径问题（Inventory Routing Problem，IRP）的解决就成了日常运营层面频繁和迫切需要解决的问题。

国外对库存路径问题的研究是在20世纪80年代出现，它是车辆路径问题（Vehicle Routing Problem，VRP）的扩展，对车辆路径问题、配送计划和库存决策进行了综合考虑[2]，在车辆路径问题的空间维度上增加了时间维度，进一步增加了路径问题的复杂性。它是在满足一定的约束条件下（如客户需求的数量、时间、库存量等约束），在计划期内针对多个需求客户，确定给各客户进行库存补充的数量和时间，并优化车辆的运输路径，使系统总成本最小或总效益最大的问题。VRP 模型只能解决某一天的车辆、路径决策优化问题，而IRP 可以解决更长时间的包含车辆路径及库存综合优化问题。

Coelho 等人[3]在2013 年对IRP 进行了文献综述，总结了其主要扩展形式、模型和算法，该作者关注的是问题的方法论，而Andersson 等人[4-5]进行的综述调查则是强调企业的实践应用。

IRP模型涉及的情况非常复杂，可以按照服务中心和客户不同数目组成的拓扑结构（1-1，1-多-1，多-多）、货物品种数（单品种，多品种）、客户需求类型（确定，不确定）、库存补货方式（最大补货，随机补货）、车辆型号（同型，异型）、成本（库存成本，运输成本）、求解方法（精确算法，启发式算法）等特征角度进行具体分类，见文献[6]。具体阐述如下：

在建立的模型类型方面，主要有类经济订货批量（EOQ-liked）模型、混合整数规划模型和随机动态规划模型这三大类IRP 模型[7]。在模型的拓扑结构方面，大多数考虑两层级1-多系统（1 个服务中心，多个客户）为对象，三层级问题的研究也有所增加[8-12]。在模型的目标方面，主要考虑的是费用目标，考虑低碳和多个目标的研究也出现不少，如唐金环等人[13]的研究。关于货物种类方面，多以单产品为主要研究对象，多产品研究成果较少[14]。在需求的特性方面，多以确定性需求问题为研究对象，随机性需求研究也有不少[15-18]。在需求的周期性方面，单周期研究较多，多周期研究也有所增加[19-21]。大部分IRP研究仍然只是考虑客户处库存单一环节与运输的整合优化，考虑多环节库存成本的研究也已出现[17]。

在模型的求解算法方面，可采用的算法有精确算法和启发式算法，目前仍以启发式算法为主要研究方向。采用的方法如禁忌搜索算法和改进的Clarke-Wright 算法（C-W算法）[10]、整合贪婪算法、遗传算法以及禁忌算法思想的混合启发式算法[22]、遗传算法[23-24]、免疫算法[25]、模拟退火算法[26]等。

在结合的行业方面，有电厂燃煤运输-库存问题[27]、分销行业[28]、备件物流[29]、原油[30]、沿河子公司运煤问题[31]、制造行业[32]、易腐品[33-[34]、汽车零部件[35]、救援物资[36]、军事领域[37]等研究。

但在针对物流包装租赁系统的配送库存路径问题研究方面，现有研究比较缺乏。国内研究方面，笔者在中国知网数据库以“物流包装的配送与库存”“托盘回收”“托盘配送”为关键字搜索共找到相关文章12 篇。其中3 篇是从运输问题模型的角度进行空托盘调度模型的研究[38-41]，但没有考虑车辆路径的问题；有3篇文章考虑了路径问题[42-44]，但都没有考虑相关的库存费用。有些文章结合库存、路径进行了研究[45]，但只考虑了服务中心的库存控制问题，没有考虑客户点的库存能力和费用问题。在国外方面，笔者以“returnable transport items”+“routing”+“inventory”为关键字在ScienceDirect、Springer、Taylor &Francis 三大数据库中搜索，共找到与本文研究主题物流包装库存与路径集成优化问题相关的有3篇文献[46-48]，其他稍相关的是物流包装的库存控制或其他方面的研究[49-51]。但这些研究都是站在生产企业自我进行采购包装使用和回收的角度，未考虑容器租赁模式下的企业运营与管理目标和约束。

基于以上考虑，借鉴供应商管理库存（Vendor Managed Inventory，VMI）模式下库存路径模型[53]，本文建立了物流包装租赁共享系统的库存路径问题优化模型并设计了求解算法，结合算例分析对比了精确算法和设计算法的主要性能差异，以为物流包装租赁共享系统日常运营层面的库存路径问题的决策需求提供决策方法和依据。

1 问题描述及模型建立

1.1 物流包装租赁共享系统

物流包装租赁共享是指采用租赁的方式完成物流包装社会化的共享，从而达到优化社会资源配置，提高资源利用效率的一种共享经济形式。物流包装租赁共享系统是向生产企业等提供物流包装租赁、配送与回收、检查、清洗维护到最后报废等运营与管理服务的服务运作系统。该系统主要由物流包装租赁企业及其信息平台、租赁企业自有或加盟服务中心、有空包装租赁需求或回收需求的客户等组成。主要流程如图1所示。

图1 物流包装租赁共享系统运作流程Fig.1 Business flow of logistics package rental sharing system

1.2 物流包装租赁共享系统的配送库存路径问题

物流包装租赁共享系统一般由多个物流包装租赁服务中心和有空物流包装回收和配送需求的客户点组成。但考虑到现阶段我国物流包装种类较多，物流作业条件较差，回收的物流包装一般不能直接供客户使用，而是需要先回到服务中心进行检查和清洗，合格的才可以配送给需求客户，这就要求将整个物流包装回收和配送的过程分开进行考虑。这里只考虑从1 个租赁服务中心出发，给多个有空包装配送需求的客户点进行空包装的配送而产生的配送库存路径问题。

该问题具体描述如下：某个租赁企业下属的1个服务中心为多个有空包装租赁需求的客户点（如多个生产企业）提供空包装租赁及配送服务。各客户点都具有一定的空包装库存和一定的空包装库存能力。各客户点对空包装的需求有周期化的特征。为满足各个客户点的空包装租赁需求和使总配送运输和库存成本最低，该租赁服务中心以若干个客户需求周期为计划期，需要确定计划期里的各个周期每次配送服务的客户对象、配送数量，并针对每辆车的服务区域寻找最优的配送路径。具体如图2所示。

图2 物流包装租赁共享系统库存路径问题示意图Fig.2 Schematic diagram of IRP of logistics package rental sharing system

1.3 模型建立

1.3.1 模型假设及变量、参数定义

在借鉴文献[3，47]部分模型基础上，考虑一对多的二层级物流包装租赁共享服务系统，其包含1个物流包装租赁服务中心和多个有空包装租赁需求的客户点。初始周期车辆从租赁服务中心出发，为各个客户点配送空物流包装，当配送任务结束后返回租赁服务中心。依据物流包装租赁企业业务实际，做如下假设：

（1）租赁服务中心仅提供一种规格的物流包装。租赁数目为整数个（如以10 个为单位），这主要是考虑到物流包装的标准化趋势、低价值特性以及充分利用车辆的装载能力，也考虑到物流包装租赁共享企业的服务便利性。租赁服务中心初始库存有限，库存能力无限。这是因为为客户提供包装租赁服务的一般是物流包装租赁企业的各个区域或地区服务中心，所以其必然具有不同的包装初始库存。

（2）在所考虑的计划期开始时已确定各个客户点的空物流包装配送需求情况，这是基于较长时间的预测做的合理假设。

（3）每个客户点空物流包装库存能力有限制，这主要考虑到客户点的仓储场地等资源限制。每个周期配送给各个客户点的空物流包装数量不能大于其库存能力限制。

（4）已知租赁服务中心和客户点处的初始库存量。整个决策计划期间，为避免缺货，设定租赁服务中心和客户点处的库存量均不能为负值。

（5）各租赁服务中心具有的配送车辆车型、装载能力相同且数目有限制。在每个服务周期里派出的每辆配送车辆最多可实施一次空包装配送工作。

（6）每个服务周期内，每一个客户点最多可以送货1次。考虑到物流包装的低价值性和充分利用车容，假设每次配送时补充物流包装的数量必须达到库存能力的最大值（即补充数量等于库存能力－现有库存）。

（7）为方便分析考虑，将运输固定费用和仓储固定费用分摊到运输费率和库存持有费率中。因此本文考虑决策目标时只考虑变动运输成本和库存持有成本两个成本，这对于追求企业经济利益的物流包装租赁企业来说，该目标是合适的。考虑决策的变量包括每个服务周期内每辆车访问哪些客户点、给各个客户点配送的物流包装数量及车辆配送时的配送路线。

涉及的参数定义及决策变量如表1所示。

表1 主要参数和变量Table 1 Main parameters and variables

1.3.2 数学模型

在该模型中，式（1）是目标函数，表示最小化物流包装共享系统的空包装过程中整个计划期内所有成本，其中第1部分表示运输成本，第2部分表示库存成本。式（2）表示租赁服务中心的初始库存非负约束。约束（3）和（4）分别表示租赁服务中心、各个客户点的库存流量平衡约束，其中（3）表示服务中心第t期的库存等于其第t-1 期的库存减去第t期所有车辆给所有客户的送出包装量，约束（4）的含义类似，不同的是针对的是客户点。约束（5）表示各客户点的库存水平非负。式（6）表示每个周期结束时各个客户点的库存量不能大于其库存容量限制。约束条件（7）和（8）确保在时间段t交付给客户i的数量在客户服务时不会超过该客户的可用库存容量，否则将为0。约束（9）意味着空包装配送量不能超过车辆容量。约束（10）表示每个周期配送给客户点的空包装总量不能超过该客户最大库存能力。约束（11）前半边等式表示各顶点处进入车辆数目和离开车辆数目相等，后半边等式则表示车辆如果进入或离开某客户，则该客户必进行了配送服务。约束（12）表示每个周期每辆车从租赁服务中心出发配送至多一次。约束（13）表示每个周期每个客户至多接受配送服务一次。约束（14）表示每个车辆沿其行走路线进行送货的一致性约束并且消除子回路，即若车辆k在t周期时服务完客户i后紧接着服务客户j，则服务完i后已配送的包装总数量等于服务完客户j后已配送的包装总数量减去对客户j的送货量，否则服务完i后已配送的包装总数量必小于服务完客户j后已配送的包装总数量加上车辆容量。约束（15）表示周期t车辆k访问客户点i后的送货量取值约束。约束（16）和（17）是非负性和整数约束。

2 算法设计及算法性能对比

所建模型为混合整数规划模型，如果模型的数据规模较小，可直接采用一些已有的数学优化软件如GUROBI、CPLEX等进行求解。但稍大规模的问题则需要设计启发式算法求解。关于利用遗传算法（Genetic Algorithm，GA）求解库存路径问题（IRP），已有一些相关研究[53-54]。借鉴文献[53-54]的部分思路利用，本文设计利用带精英保留的改进遗传算法求解。算法的总体框架如图3所示。

图3 IRP模型遗传算法求解流程Fig.3 Genetic algorithm solution process of IRP model

图中，种群规模用Popsize表示；种群进化的最大代数用G表示；交叉概率用Pc表示；变异概率用Pm表示。

2.1 染色体的编码及空物流包装配送数量的计算

本文利用一个N（客户数）行T（周期数）列的0-1矩阵排列来组成一个染色体，染色体中的每个基因用来表示，该基因可取0或1，表示每个空物流包装配送客户i是否在周期t访问，若表示l染色体表示的租赁客户i在周期t进行了空包装的配送；同理，若，表示租赁客户i在周期t不进行空包装的配送。

若在周期t给租赁客户i处进行空物流包装的配送，则其配送的数量要看在其后的周期是否还对其进行配送。假设在之后的周期t′(t′＞t)再一次进行配送，那么周期t时给客户i处配送的物流包装数量至少是该客户i在周期[t,t′-1]之间对空物流包装的需求之和。

表2给出了包括7个包装租赁客户（客户1～客户7），4 个周期（T1～T4）的染色体编码矩阵、物流包装配送量矩阵及对应的库存量计算矩阵算例。

表2 染色体编码方式及配送量计算举例Table 2 Example of chromosome coding method and delivery quantity calculation

通过表2 可以看出，在第1 个周期时所有的客户都没有进行空包装的配送。对客户2来说，其分别在第2、3 周期进行了访问，配送包装量分别为8 件、16 件，最后客户2各周期末的库存量分别是0件、0件、8件、0件。

2.2 初始种群的产生

初始种群需要产生设置的种群数(Popsize)个染色体，每个染色体都由N×T个0或1的基因组成，其中N为客户点数，T为周期数。初始种群的产生具体步骤如下（以某个染色体l为例）。

构造完初始种群后，接着可计算每个染色体对应的物流包装配送数量矩阵。因为在构造初始染色体时有一些基因值是随机产生的，所以若全部根据上述的步骤计算物流包装配送数量矩阵，则有可能会产生不可行的解或者给某一个客户处配送的空包装容器超过车辆载重要求。故而这里对空包装配送量的计算方法进行如下调整：

2.3 适应度函数值和种群评价

适应度函数值是判断种群中染色体个体优良的指标，遗传算法通过适应度函数值的变化选择来找到最优解。本文采用经典的轮盘赌选择法，由于轮盘赌选择法需要适应度函数值非负，且适应度函数值的大小说明了染色体个体的优劣。

由于本文计算的目标函数是总成本，并不能将其直接作为适应度函数值，但是可以用一个足够大的数M（取M＝1 000）除去目标函数然后将其作为适应度函数，即并且为了方便对每个目标函数值的适应度值进行区分，加大选择的压力，本文还将对每个适应度函数进行15次乘方处理，即将F(x)＝f(x)15作为计算的适应度，从而扩大适应度的差异。

此外，本文利用精英保存策略将适应度最好的个体直接遗传给子代。即若某代种群中获得的最优染色体的适应度比上代染色体中的最优染色体适应度差，则将上代染色体中的最优染色体直接遗传给下一代种群中最优染色体。

关于各个周期每个车辆的路径成本，本文采用C-W节约算法[55]产生每个周期的路径并进行路径费用的计算。具体操作方法如下：

首先，找到每个染色体编码中各个周期t中需访问的客户点i，将所有需访问的客户点（设为m个）加上初始服务中心后形成一个由m＋1 顶点组成的集合。然后，添加已知的各个客户点的需求（服务中心需求设为0）及其相互间的距离矩阵，结合车辆容量Qk，利用C-W节约算法解决一个多车辆路径问题。最后，获得各个车辆访问的客户点顺序集并计算其总的运输距离及费用。

2.4 改进交叉算子

交叉表示将所选择的两个父代染色体的一部分基因进行互换，然后得到子代染色体的方法。交叉算子对遗传算法全局搜索能力有关键影响。本文的交叉算子采用如下交叉方式：针对某一代利用轮盘赌方法选中的两个父代染色体P1和P2，随机生成一个大小为N×1的由0和1组成的行向量如[1 0 0 1 0 0 1]，该行向量中的第i个值决定了其子代1 的每个客户i＝1,2,…,N相应周期的基因值的获得继承关系，即假如i位置取值为0，则子染色体C1中相应第i个客户相应行的基因值完全从父代1获得。假如i的位置取值为1，则子染色体C1中相应第i个客户相应行的基因值完全从父代2获得。反之，可以用相似的原理创建子代C2，即假如i位置取值为0，则子染色体C2中相应第i个客户相应行的基因值完全从父代2获得，假如i的位置取值为1，则子染色体C2中相应第i个客户相应行的基因值完全从父代1获得。

2.5 变异算子

为防止算法过早收敛，GA 一般通过变异算子来实现种群多样性。它一般是通过挑选某些染色体部分基因进行变异来具体实现，变异的方式有多种。本文采取基本位变异的形式，即随机选择某个染色体的某一位基因，将它的基因值由0变成1或者由1变成0。

原种群中的染色体在交叉和变异操作完后需要检查该染色体的可行性以免出现如不符合车辆装载容量限制和库存不足导致缺货的情况。采用如下方式调整：如果，则置；t＞1 且客户i在周期t以前都未进行过访问，则置；此外，在交叉和变异操作结束后再利用2.2节中的方法计算物流包装配送数量矩阵。当迭代次数达到G代时，算法结束。G的取值依据不同情况可进行调整，此处取值为100。

3 数值实验结果及与算法结果讨论

为比较精确算法和启发式算法的性能，本文采用文献[45]中稍小规模（7个客户）和稍大规模（20个客户）的两个算例进行数值实验分析。设某物流包装租赁企业在某区域内有1个服务中心服务7（20）个客户，考虑4个周期为1个计划期，每个决策周期内对各个客户点进行物流包装配送服务。其中0表示租赁服务中心，1～7（1～20）表示有空包装容器需求的客户点。服务中心有配送车3（4）辆，每一辆车最多装载25件空包装，单件空包装在租赁服务中心和客户点的单位周期保管费用分别为0.1 和0.3 欧元。单件物流包装单位距离的变动运输费用为0.04 欧元。需通过优化获得各客户点最优的服务策略及最合理的车辆运输线路以实现总费用最小。

将以上模型和数据编制程序，利用优化软件CPLEX 12.4在Intel Core i5-2450M CPU＠2.50 GHz，内存3 GB，Windows7操作系统环境下，采用CPLEX默认求解配置，稍小规模模型求解运行时间为208 s，总费用为75.88欧元，库存费45 欧元，运输费30.88 欧元。具体配送方案和库存变化情况如表3所示。

表3 小规模算例模型CPLEX求解结果Table 3 CPLEX solution of small-scale data model

采用本文设计的一般遗传算法编码进行求解，其中种群数为100，代数为50，交叉率Pc＝0.9,变异率Pm＝0.2，利用Matlab7.10编制程序，在Intel Core i5-2450M CPU＠2.50 GHz，内存3 GB，Windows7 操作系统环境下，模型的小规模算例的一般遗传算法（GA）求解结果如表4所示。

表4 小规模算例模型IGA求解结果Table 4 IGA solution of small-scale data model

从表4中可以看出，模型的小规模算例的一般遗传算法求解运行时间为36.13 s，总费用为77.44欧元，库存费49.6 欧元，运输费27.84 欧元，优化的送货路径为6条，共需派出6 个车次，最多在周期2 同时派出3 辆车，算法在第11代获得最优解。迭代过程如图4所示。

图4 小规模算例模型GA求解迭代过程Fig.4 Iterative process of GA to solve small-scale data model

模型的稍大规模算例的一般遗传算法求解结果和迭代图如图5和表5所示。

图5 稍大规模算例GA求解迭代过程Fig.5 Iterative process of GA to solve large-scale data model

从表5中可以看出，模型的稍大规模算例的一般遗传算法求解运行时间为183.19 s，总费用为101.38欧元，库存费63.2欧元，运输费38.18欧元，优化的送货路径为8条，共需派出8个车次，最多在周期2同时派出4辆车，算法在第35代获得最优解。

表5 稍大规模算例模型IGA求解结果Table 5 IGA solution of large-scale data model

针对较小（7个客户）和稍大规模（20个客户）算例，将一般遗传算法与CPLEX 精确算法进行比较，见表6所示，其中gap=（CPLEX求解上界－CPLEX求解下界）/CPLEX 求解上界，Gap=（启发式算法次优总费用－CPLEX最优解或上界）/CPLEX最优解或上界。

从表6 中可以看出，稍大规模下，CPLEX 在默认配置情况下，求解1 800 s，未获得最优解，只获得可行解，和本文设计的一般遗传算法比较，虽然设计算法求解的结果较CPLEX求解的结果稍差，但运行时间大大缩短，说明了本文设计的启发式算法的有效性。

表6 模型IGA与CPLEX求解比较Table 6 IGA solution comparison with CPLEX

另外，将本文设计的改进遗传算法（IGA）与文献[53]设计的遗传算法（GA）利用以上算例和参数，分别求解10次比较其平均值，见表7所示。

表7 模型IGA与GA求解结果比较Table 7 GA solution comparison with IGA

从表7中可以看出，论文设计的遗传算法和改进遗传算法小规模算例求解运行时间平均分别为50.32 s 和42.35 s，平均总费用分别为77.51 欧元和77.43 欧元，平均Gap 分别为2.1%和2.0%；稍大规模算例求解运行时间平均分别为153.2 s和107.0 s，平均总费用分别为102.7欧元和101.6欧元，平均Gap分别为8.1%和7.0%。总体来看，改进遗传算法求解迭代收敛更快，时间减少43%，优化效果更好。

4 结论与展望

本文结合物流包装租赁共享系统的空包装配送流程，建立了总成本费用最小的物流包装租赁共享系统库存路径问题优化模型。采用稍小和稍大规模的两个算例，利用CPLEX 软件和设计带精英保留的遗传算法进行了对比求解分析，验证了设计的启发式算法和模型的有效性。本文对模型和库存控制的研究只考虑了空包装的配送过程，没有考虑空包装的回收过程，后期将考虑对空包装的回收过程进行集成建模，并设计算法求解。