考虑碳排放的易腐品供应链选址-路径-库存联合优化

王梦梦　韩晓龙

摘要：

為优化易腐品供应链运作，降低总成本和碳排放，建立易腐品损坏函数，将多配送中心选址、车辆路径和库存管理策略相结合，提出考虑客户随机需求的易腐品供应链选址-路径-库存联合优化模型。设计两阶段启发式算法求解这个大规模问题。对单位碳排放价格变动和服从正态分布的客户随机需求波动进行灵敏度分析。对模型和算法进行算例分析，并与相关文献对比，结果表明，模型和算法具有良好的适用性。

关键词：

选址-路径-库存联合优化; 易腐品; 碳排放; 两阶段启发式算法

中图分类号：F252

文献标志码：A

收稿日期： 2018-11-07

修回日期： 2019-03-15

基金项目： 上海市科学技术委员会创新项目（16DZ1201402，16040501500）

作者简介：

王梦梦（1993—），女，河南焦作人，硕士研究生，研究方向为供应链过程一体化，（E-mail）1277090884@qq.com;

韩晓龙（1978—），男，山东潍坊人，副教授，博士，研究方向为物流与供应链管理，（E-mail）superhxl@163.com

Location-routing-inventory joint optimization of perishable product supply chain considering carbon emission

WANG Mengmeng， HAN Xiaolong

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

In order to optimize the supply chain operation of perishable products and reduce the total cost and carbon emission， a perishable product damage function is established， the multi-distribution center location is combined with the vehicle routing and the inventory management strategy， and a model of location-routing-inventory joint optimization for perishable product supply chains is proposed considering the randomness of customer demand. A two-stage heuristic algorithm is designed to solve the large-scale problem.The sensitivity analysis is carried out on the variation of unit carbon emission price and the fluctuation of customer demand obeying normal distribution. The case analysis is carried out on the model and the algorithm. The comparison with relevant literatures shows that the model and algorithm are of good applicability.

Key words：

location-routing-inventory joint optimization; perishable product; carbon emission; two-stage heuristic algorithm

0 引 言

在实际生活中，由于客户需求的随机性和不可预测性，常常会引发一些问题，如配送中心因不能及时满足客户需求而导致客户流失。易腐品“易变质”特性使其库存成本很高，因此易腐品配送中心的库存管理直接影响供应链成本，需要引起重视。同时，由于客户需求的不确定性，开放的配送中心的数量和规模也有很大不同，需要通过配送中心选址达到优化成本的目标。配送路径成本在总成本中所占的比重较大，因此配送路径优化也一直是研究的重点和热点。在实际配送过程中，水果、蔬菜、肉禽蛋、水产品等生鲜农产品易腐品所占比重较大，然而由于配送中心选址、路径规划、库存管理的不完备，常常导致大量的浪费，使得易腐品配送成本居高不下。

初期供应链优化模型仅考虑路径优化，如：XIA等[1]针对低碳供应链建立了双目标模型进行路径优化;夏扬坤等[2]研究了一种带工作时间和软时间窗的车辆路径问题，建立了相应的双目标数学模型，并设计自适应禁忌搜索算法进行求解;秦进等[3]提出了拥堵情形下的行驶时间计算模型，建立了污染路径问题的线性规划模型，并提出了基于节点时间窗变换以及速度和出发时间优化的求解算法。实际上，选址、路径、库存是相互依赖的，逐渐有学者开始关注选址、路径和库存的联合优化：PRINS等[4]将选址和路径决策同时进行优化，取得了比较好的优化效果;戢守峰等[5]提出了选址-路径-库存联合优化的目标模型，将限速和拥堵情况考虑进去，使用标准正规化方法求解问题;GUERRERO等[6]研究了确定需求下的选址-路径-库存联合优化问题;ZHANG等[7]提出了考虑逆向物流的闭环供应链中的选址-库存联合优化。

此外，学者们还对不同情形下的供应链联合优化问题进行了深入研究：DIABAT等[8]同时考虑了需求和提前期不确定的选址-库存优化问题，并运用模拟退火算法和直接搜索方法进行求解;ZHALECHIAN等[9]研究了随机需求情况下闭环供应链的选址-路径-库存联合优化问题;SOYSAL等[10]研究了考虑横向合作的易腐品供应链优化，以减少易腐品的损坏。

针对以上研究，本文将选址、路径、库存三者联合起来，研究考虑碳排放和客户随机需求的易腐品供应链优化问题。首先，在客户随机需求情况下建立多品类易腐品供应链选址-路径-库存联合优化模型，建立易腐品损失函数，使之更贴近实际情況和注重供应链的整体优化效果;其次，将环境因素考虑进去，在进行供应链设计时考虑碳排放的影响，通过单位碳排放价格将碳排放量转化为成本，形成总成本最小的单目标模型;最后，在灵敏度分析部分考虑单位碳排放价格和客户需求波动对总成本的影响。

1 问题描述与假设

本文将配送中心选址、车辆路径优化和库存管理策略相结合，研究多品类易腐品的物流网络优化问题。研究目标为总成本最小。配送网络设计如图1所示，是一个包含多配送中心（用DC表示）和多客户需求点（用C表示）的二级供应链网络。引入易腐品损失函数衡量损失成本的大小[11]。

采用周期盘点的库存管理策略，即每个周期对库存量进行一次检查并订货。假定订货提前期为零，即每个周期期末订货，产品在期初就能到货。

假设：（1）运输成本和碳排放量只与车辆行驶里程有关，不考虑其他因素;（2）客户位置已知，客户需求相互独立且服从正态分布;（3）不考虑缺货成本;（4）各客户间的距离满足三角不等式;（5）从多个备选配送中心（地点和规模是确定的）中选择开放的配送中心及其开放的规模等级;（6）所有配送车辆都是同车型的，最大容量为c;（7）整个运输过程中车辆匀速行驶。

2 模型构建

2.1 符号说明

集合：客户集合Vc={1，2，…，Vc}，i∈Vc;同一辆车服务的客户集合V（1）c;配送中心集合Vd={1，2，…，Vd}，j∈Vd;配送中心规模等级集合Lj，l∈Lj;易腐品种类集合P={1，2，…，P}，p∈P。

参数：o（l）j为开放规模等级为l的配送中心j的固定成本;g（p）j为配送中心j的产品p的每次固定订货成本;h（p）j为配送中心j的产品p的单位库存成本;s（p）j为每个周期末配送中心j产品p的持有量;rp为产品p的单位损坏成本;α为考虑库存限制而预先设定的客户满意度水平;c为车辆的最大容量约束;βp为把产品p运输单位距离的腐坏率;b（p）j为每个周期初从供应商运往配送中心j的产品p的量;q（p）j，i为每个周期初从配送中心j运往客户i的产品p的量;d（p）i为客户i对产品p的需求量，服从正态分布，d（p）i～N（μi，p，δ2i，p）;ai，j为客户i与配送中心j之间的距离;f为车辆单位距离燃料成本;（l）j为开放规模等级为l的配送中心j对应的固定碳排放量;ep为产品p腐坏产生的单位碳排放量;kp为产品p的腐坏量;（p）j为配送中心j对单位产品p的库存制冷而产生的碳排放量;m（p）i，j为产品p在客户i与配送中心j之间运输而产生的单位距离碳排放量;v为车辆行驶速度;w为由配送车辆制冷而产生的单位距离碳排放量;λ为单位碳排放量的价格。

决策变量：X（p）j，i∈{0，1}，若产品p从配送中心j运往客户i，则X（p）j，i=1，否则为0;D（l）j∈{0，1}，若开放规模等级为l的配送中心j，则D（l）j=1，否则为0。

2.2 模型

除有特殊说明外，模型中出现的下标i∈Vc，j∈Vd，p∈P，l∈Lj。

式（1）是关于成本最小的目标函数，成本由4部分组成：配送中心选址成本、库存成本、损坏成本（易腐品在配送过程中损坏产生的成本）和路径成本（车辆从配送中心行驶到客户需求点产生的成本）。式（2）是关于碳排放量最小的目标函数，碳排放量由4部分组成：配送中心选址碳排放量（指开放不同规模等级的配送中心产生的碳排放量）、存货产生的碳排放量、腐坏产品产生的碳排放量和配送路径上产生的碳排放量（包括车辆行驶一定距离产生的碳排放量和冷链运输过程中制冷产生的碳排放量）。式（3）是以将碳排放量通过单位碳排放价格转化为成本[12]后的总成本最小为目标的函数。

式（4）为配送中心选址阶段规模限制。式（5）是库存约束，是对每个周期末服务水平的限制。式（6）～（9）为路径决策约束，其中式（6）保证每个周期到达与出发的车辆数守恒，式（7）保证在每个周期一辆车最多在一条路线上行驶，式（8）为车辆容量约束，式（9）为配送中心期初运出量约束。式（10）和（11）为决策变量约束。

3 两阶段启发式算法

研究问题属于大规模NP难问题，难以运用精确算法进行求解，因此本文采用两阶段启发式算法[13-14]。

3.1 第一阶段启发式算法

第一阶段启发式算法用来确定配送中心是否开放以及开放的规模等级，确定每个配送中心所服务的客户以及最佳配送路径，形成初始解。

步骤1 初始化参数。初始化客户位置（X，Y）， 备选配送中心位置（x，y），随机生成的客户对每种易腐品的需求量d（p）i（客户需求服从正态分布）。

步骤2 确定第一阶段初始种群。使用自然数编码。比如：在某供应链网络中有5个备选配送中心和20个客户需求点，给这25个节点编号，其中1到20分别是20个客户需求点的编号，21到25分别是5个备选配送中心的编号;染色体{21，7，8，12，15，21，16，17，22，2，3，6，22，4，5，10，22，1，13}中有5个子串，分别是（21，7，8，12，15）、（21，16，17）、（22，2，3，6）、（22，4，5，10）、（22，1，13）;这5个子串中只有配送中心21、22出现，即配送中心21、22为选中的配送中心;客户需求点7、8、12、15、16、17被分派给配送中心21，客户需求点1～6、10、13被分派给配送中心22;子串（21，16，17）表示配送车辆从编号为21的配送中心发出，先后经过客户需求点16、17，最后返回到原配送中心，即路线为21→16→17→21。

步骤3 计算种群的适应度。种群的适应度函数是评估种群个体优劣的重要参考，个体的适应度越大，其被选择到下一代的概率越大。本文中目标函数是使总成本最小，因此以目标函数的倒数作为适应度函数，即fi=1/zi，其中fi表示个体i对应的适应度，zi表示个体i对应的目标函数值。

步骤4 对种群个体进行选择、交叉、变异操作以形成新的种群。

（1）选择操作。选用锦标赛策略进行选择操作。通常取k=2（k是竞赛的规模），先将每代种群中适应度最大的个体直接复制到下一代，然后采用锦标赛策略产生下一代其余的个体。

（2）交叉操作。采用循环交叉法进行交叉重组，具体操作见图2。

（3）变异操作。采用倒位变异和变换变异操作。倒位变异如图3所示：在编码串上随机选取两个点，将这两个点之间的基因按照相反的顺序插到原来的位置上。变换变异如图4所示：将个体基因上的任意两个基因进行位置互换形成新的染色体。

步骤5 选用最大迭代次数为5 000。当达到最大迭代次数时，第一阶段算法结束。

步骤6 计算将产品从配送中心送至客户需求点的总成本z，形成初始方案。

3.2 第二阶段启发式算法

第二阶段启发式算法主要通过不断开放与关闭配送中心对第一阶段形成的初始解进行改进。

步骤7 计算已经开放的配送中心的数量Vd。

步骤8 以计算总成本最小为目标关闭一个配送中心（Vd=Vd-1），按照距离最小的原则对客户需求点重新分组，执行步骤1～6，得到关闭配送中心后的系统总成本z′。

步骤9 比较z与z′的大小：如果z′

步骤10 以获得总成本最小为目标不断开放与关闭配送中心，计算系统总成本。

步骤11 判断Vd是否为1：如果为1，则至步骤12;否则返回步骤8。

步驟12 比较各种情况下系统总成本，得出最低总成本和最优解集。算法结束。

在配送中心不断开放与关闭的情况下，本文算法会首先进行配送中心规模等级判断，判断当前开放的配送中心的数量、规模是否充分满足客户的需求;如果当前配送中心的数量、规模不满足客户需求，则否决当前的配送中心开放方案。对于车辆容量问题，本文所用方法与配送中心的选址方法是类似的，若当前配送方案中的车辆容量不足以满足其对应路线上的客户需求，则在该路线上增加配送车辆。

随着客户数量Vc的增加，迭代次数会急剧增加，导致计算量大大增加，求解速度显著减缓。因此，本文采用线性函数方法设置最大迭代次数，同时设定基数为3 000，这样可以灵活适应不同规模问题的求解。对于中小规模的问题，迭代次数不会过少，不会出现算法过早收敛导致搜索不到最优解的现象;对于大规模问题，不会因为客户点的增多而迅速膨胀。通过大量实验，选取最大迭代次数为3 000+20Vc。

4 算例分析

4.1 数据来源

为证明模型和算法的有效性，选取数据[15-16]进行算例分析。共选取100个客户需求点（C）和5个备选的配送中心（DC），其位置坐标是随机生成的;部分客户需求见表1;配送中心坐标、规模、相关费用和碳排放参数见表2和表3。牛肉、苹果的单位损坏成本分别为2.3、0.6元/kg，牛肉、苹果的固定订货成本分别为500、300元，牛肉、苹果的腐坏率分别为0.000 10、0.000 08，客户对牛肉、苹果的需求分别服从正态分布N（50，252）、N（100，492）。车辆每千米燃料成本为1.067元，客户满意度水平为97%，车辆的最大容量为16.370 t，车辆行驶速度为50km/h。每千克产品腐坏产生的碳排放量为41.21 g，每千米碳排放量（包括制冷和运输碳排放量）为438.421 g，碳排放成本为0.000 4元/g。

4.2 計算结果

使用MATLAB实现两阶段启发式算法的求解。算法参数设置如下：种群数300，交叉概率0.95，变异概率0.08，最大迭代次数5 000，单位碳排放成本为0.000 4元/g。

图5为得出的每辆车的最优配送路径，较少出现路径交叉情况，这表明优化效果比较明显。开放的配送中心为5，规模等级为3。车辆在节点之间的行驶顺序为DC5→70→100→41→26→69→54→77→21→32→90→49→85→93→20→67→92→95→8→59→22→66→34→12→28→96→62→43→84→78→53→68→99→88→94→86→97→50→71→29→46→74→87→11→17→81→31→30→57→25→19→40→52→60→18→89→13→64→37→15→45→55→14→33→23→56→5→76→44→2→98→10→6→3→61→83→48→1→9→35→79→73→42→72→39→82→80→47→58→27→91→24→65→4→38→63→75→51→7→16→36→DC5。由开放配送中心的数量、规模等级和最优配送路径规划可计算出，碳排放量为2 364.97 kg，最终总成本为29 019元。

图5 考虑碳排放的车辆路径规划

图6为启发式算法迭代过程中每代个体适应度的最优、平均和最差值的对比，由图6可以看出算法在迭代到第1 230次时开始收敛，接近最优值。

图6 考虑碳排放的启发式算法迭代过程中每代个体适应度的最优、平均和最差值对比

5 灵敏度分析

为进一步验证模型和算法，从单位碳排放价格和客户随机需求的变化来进行灵敏度分析。

5.1 单位碳排放价格的影响

为观察单位碳排放价格对总成本的影响，保持其他参数不变，只改变单位碳排放价格，计算结果见表4。

从表4中可知，随着单位碳排放价格的增加，碳排放成本占总成本比例越来越大。单位碳排放价格与总成本呈正相关关系，且几乎呈直线上升状态，这说明单位碳排放价格的变动会对总成本造成很大影响，而且随着人们低碳意识的不断增强，单位碳排放价格会持续上升。如果企业不采取有效的降低碳排放的措施，未来利润空间会不断遭受挤压，因此发展低碳技术已成为企业的必经之路。

5.2 客户随机需求的影响

在其他参数不变的情况下，设置客户对牛肉、苹果的不同的需求方差，计算结果见表5。

由表5可知，随着客户随机需求波动的逐渐增大，碳排放呈上升趋势，且增速越来越快，原因如下：客户随机需求波动增大时，开放的配送中心的数量会相应增加，开放的配送中心的规模等级也会相应提高，从而产生更多的碳排放;在路径规划阶段，随着客户随机需求波动增大，路径优化结果相对不太理想，路径复杂度较高，碳排放也会相对增加;配送中心库存量也会随着客户随机需求波动量的增大而增加，使得库存阶段碳排放逐渐增加。需求的不确定性对碳排放量产生了较大影响，为响应国家环保号召以及迎合消费者的低碳偏好，应尽量减少客户随机需求波动。企业可以通过各种优惠政策鼓励客户进行预订，减少客户随机需求波动，降低不确定性，从而达到降低碳排放的目的。

5.3 算法对比分析

将本文采用的两阶段启发式算法与文献[17]采用的蚁群算法进行对比，结果见表6。从表6可知：相比于蚁群算法，用两阶段启发式算法得到的总成本更低;本文只使用了2辆运输车，配送相对集中，导致货损成本稍高于文献[17]中计算得到的货损成本，但本文中碳排放成本、运输成本均低于文献[17]的计算结果，更加符合低碳低成本的物流需求，也进一步说明了本文算法的有效性。

6 结论与建议

本文针对考虑碳排放的多品类易腐品供应链优化问题，提出了供应链选址-路径-库存联合优化模型，设计了两阶段启发式算法进行求解。通过算例说明了算法的可行性和模型的有效性。通过灵敏度分析得出了单位碳排放价格变动对总成本影响较大的结论，因此建议企业在实际运作过程中大力发展低碳技术提高利润空间。本文还考虑了客户随机需求波动对碳排放的影响，结果表明，随机需求波动越大，碳排放越多，因此建议企业采取鼓励客户提前预定等各种措施来降低客户的随机需求波动，建立更为绿色且经济的供应链。

本文未考虑包含供应商在内的三级供应链选址-路径-库存联合优化问题，未考虑多周期产品的供应问题，这将是进一步研究的方向。

参考文献：

[1]XIA Yangkun， FU Zhuo， TSAI Sang-Bing， et al. A new TS algorithm for solving low-carbon logistics vehicle routing problem with split deliveries by backpack—from a green operation perspective[J]. International Journal of Environmental Research and Public Health， 2018， 15（5）： 1-12. DOI：10.3390/ijerph15050949.

[2]夏揚坤， 符卓. 带软时间窗的连锁超市配送车辆路径问题[J]. 信息与控制， 2018， 47（5）： 599-605. DOI： 10.13976/j.cnki.xk.2018.7307.

[3]秦进， 刘致远. 考虑拥堵情形的污染路径问题及其求解算法[J]. 工业工程与管理， 2018， 23（2）： 23-32. DOI： 10.19495/j.cnki.1007-5429.2018.02.004.

[4]PRINS C， PRODHON C， CALVO R W. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking[J]. 4OR： A Quarterly Journal of Operations Research， 2006， 4： 221-238.

[5]戢守峰， 唐金环， 蓝海燕， 等. 考虑选址-路径-库存联合优化的碳排放多目标模型与算法[J]. 管理工程学报， 2016， 30（3）： 224-231. DOI： 10.13587/j.cnki.jieem.2016.03.028.

[6]GUERRERO W， PRODHON C， VELASCO N， et al. Hybrid heuristic for the inventory location-routing problem with deterministic demand[J]. International Journal of Production Economics， 2013， 146： 359-370.

[7]ZHANG Zhihai， UNNIKRISHNAN A. A coordinated location-inventory problem in closed-loop supply chain[J]. Transportation Research Part B， 2016， 89： 127-148.

[8]DIABAT A， DEHGHANI E， JABBARZADEH A. Incorporating location and inventory decisions into a supply chain design problem with uncertain demands and lead times[J]. Journal of Manufacturing Systems， 2017， 43： 139-149.

[9]ZHALECHIAN M， TAVAKKOLI-MOGHADDAM R， ZAHIRI B， et al. Sustainable design of a closed-loop location-routing-inventory supply chain network under mixed uncertainty[J]. Transportation Research Part E， 2016， 89： 182-214.

[10]SOYSAL M， BLOEMHOF-RUWAARD J M， HAIJEMA R， et al. Modeling a green inventory routing problem for perishable products with horizontal collaboration[J]. Computers and Operations Research， 2018， 89： 168-182.

[11]钱光宇. 考虑碳排放的生鲜农产品冷链配送路径优化研究[D]. 北京： 北京交通大学， 2016.

[12]杨蓓， 汪方军， 黄侃. 适应低碳经济的企业碳排放成本模型[J]. 西安交通大学学报（社会科学版）， 2011， 31（1）： 44-49. DOI： 10.3969/j.issn.1008-245X.2011.01.009.

[13]WANG Jiahai， WENG Taiyao， ZHANG Qingfu. A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows[J]. IEEE Transactions on Cybernetics， 2018： 1-7.

[14]LIU Shu-Chu， LEE Shun-Pin. A heuristic method for the combined location routing and inventory problem[J]. International Journal of Advanced Manufacturing Technology， 2005， 26（4）： 372-381.

[15]劉倩晨. 考虑碳排放的冷链物流研究[D]. 北京： 清华大学， 2010.

[16]章添霞， 李慧. 考虑运输速度和碳排放的易腐食品供应链网络优化研究[J]. 工业工程， 2016， 19（4）： 83-89. DOI： 10.3969/j.issn.1007-7375.2016.04.013.

[17]潘茜茜， 干宏程. 考虑碳排放的冷链物流配送路径优化研究[J]. 数学的实践与认识， 2016， 46（2）：62-68.

（编辑 赵勉）