考虑满意度的团购两级混合冷链低碳路径优化

戚淳浩，朱 琳

上海海事大学 物流研究中心，上海 201306

生鲜品社区团购作为新零售模式的衍生，因其能够在疫情当下更好地满足消费者需求而快速发展[1]。社区团购是指运营商在各区域安排若干团长，由团长发布商品清单并收集客户购买意向汇总交付给运营商，由运营商安排车辆将货物由城市仓配送到中转仓，再通过中转仓转运到各团长处，最后由客户自提，完成交付任务。该模式中，团长的引入实现了顾客需求在时间和空间上的聚集[2]，提升企业效益的同时也导致社区团购生鲜品需求量的短时爆发，对运营商运输交付能力提出更高要求，运力资源重要性凸显[3]。生鲜品冷链运输过程有易腐易损、新鲜度衰减快等特点，研究表明产品的新鲜程度是影响满意度的主要因素之一[4]。因此，如何缓解因商品在途品质损失对满意度造成的负面影响，同时改善运力不足的问题，成为当前提高生鲜品社区团购模式效益的关键。

国内外学者针对冷链运输过程中产品品质衰减的问题做了大量研究，Wu等[5]表明了产品新鲜程度对顾客满意度的决定性作用，并据此设计出一种考虑顾客满意度和碳排放的综合冷链车辆路径问题优化模型，采用改进的自适应混沌蚁群算法对模型进行计算实验，证明其可行性。Chen 等[6]考虑了冷链配送过程商品新鲜度劣化和碳排放等因素，提出一种新型路线优化模型，采用蚁群算法与禁忌搜索算法求解该模型。Crama等[7]解决了产品品质变化和随机需求的路径规划问题。通过比较产品新鲜度、利润及服务水平证明其可行性。Wang等[8]构造了一种考虑时间窗和产品品质的多目标VRP优化模型，该模型以生鲜产品配送成本最小和新鲜度最大化为目标，使用可变邻域搜索方法和遗传算法组成的启发式算法来求解此模型。方文婷等[9]建立以货损成本，制冷成本，时间窗惩罚成本等总成本最小为研究目标的冷链物流路径优化数学模型，采用混合蚁群算法进行求解。Chen 等[10]讨论了一个考虑带时间窗和客户随机需求的生鲜食品生产调度和冷藏车路径的非线性数学模型。将城市仓的收入与客户对产品品质的满意度相联系，采用启发式算法求解这一问题。Song等[11]研究了一类冷藏车的生鲜品运输路径问题，目标是产品的新鲜度最大化使客户满意度的总水平最高，通过数值算例和灵敏度分析，验证了该模型的有效性。Wang 等[12]将顾客满意度从新鲜度和时间窗口两个方面来定义。提出了基于客户满意度的优先级函数，建立了易腐产品多目标冷藏车调度优化模型。针对该模型，设计了基于优先级的遗传算法进行求解。

目前，许多学者都致力于运力不足问题的研究，Huang等[13]为确保服务质量提出了一种基于任务粒度的时空众包自适应聚类的角色感知方法来缓解运输压力。刘春玲等[14]将众包模式应用于冷链运输，利用社会闲散运输资源来保证冷链配送的时效性。Zhang等[15]基于商品需求的短时爆炸性增长，提出了两级车辆路径规划来解决，产品首先从中央仓库被运输至转运卫星，然后从转运卫星交付给客户，并采用混合烟花算法来求解模型。Sadrani 等[16]研究了以瞬态需求量最大情况下减少平均乘客等待时间为目标的混合车队车辆调度问题，开发了SA 算法与蒙特卡洛仿真框架相结合，求解随机行程的真实实例。Haddad 等[17]在传统时间依赖的车辆路径模型基础上，考虑了路径最短和大量客户快速交货的诉求，运用一种基于空间搜索的框架解决此问题。

但是，上述学者鲜有将这两种因素结合研究，即对运营商与团长双方的实际需求匹配分析。对于社区团购运营商来说，可以考虑将众包模式引入两级冷链规划，通过利用社会闲置运输资源来缓解企业运输压力，同时提高物流末端交付任务的时效性[18]，优化满意度。

本文研究了一种基于众包模式的软时间窗两级开闭混合冷链车辆路径问题，同时考虑团长对产品满意度的要求，提出一个依赖产品质量下降程度的价格折扣函数[19]。由于冷链运输过程有较多的油耗和碳排放量，对环境负面影响压力大，贯彻绿色物流理念，将环境保护成本作为碳排放成本纳入总成本考虑。此外，以总成本最小且满意度最大为目标构建数学模型。针对该模型的特点设计了一种IALNS算法，该算法在ALNS算法[20]破坏-修复-选择算子部分融入SA算法[21]的思想，利用其易跳出局部最优的特性，提高解的质量。通过与其他经典算法运行实例作对比，验证模型的有效性和算法的可行性。

1 问题定义

1.1 问题描述及基本假设

本文根据实际生鲜品社区团购模式的特点，设计了一种包含众包的两级开闭混合车辆路径规划模型。该模型中，企业冷藏车只能从城市仓出发且完成到中转仓的一级配送任务后需返回城市仓，形成闭环运输，众包冷藏车只能从中转仓出发且完成到团长的二级配送任务后不需要返回中转仓，形成开环运输。两级开闭混合冷链运输模式具体如图1 所示。图中0 点表示城市仓，A～C表示各企业冷藏车，a～f表示各众包冷藏车，实线为企业冷藏车辆闭环路线，虚线为众包冷藏车开环路线，编号1～6表示各中转仓，编号7～15表示各团长。

图1 众包模式下的两级开闭混合车辆路径示意图Fig.1 Path diagram of two-level open and closed hybrid vehicle path in crowdsourcing mode

考虑生鲜品的时变衰减特性，结合实际提出一种时间依赖惩罚策略[22]，对于交付延迟导致产品劣化影响了满意度的情况，需要接受惩罚。团长有软时间窗要求，商品交付时间早于或晚于时间窗都需要接受惩罚。将运输过程中产生的碳排放对环境造成的污染成本转换成碳排放成本。基于总成本最低且满意度最大的条件，根据已知资源，在产品新鲜期、团长需求量和交付时间窗的各条件限制下，形成一种运输策略，使得两级冷链路线中各团长需求被满足。具体假设如下：

（1）有足够多的企业冷藏车和众包冷藏车来满足团长生鲜产品配送需求，并且各冷藏车载重固定，每次运输任务均不超载；

（2）各中转仓和团长的位置、各团长对生鲜品需求量、约定配送时间以及产品新鲜期已知；

（3）每一个中转仓和团长分别只能安排一辆企业冷藏车和众包冷藏车进行配送，且保证其能够提供满足各点需求的服务，同一辆车可配送多个点但每一个点只允许一辆车出发和到达一次；

（4）若该生鲜品配送到团长时刻大于其品质下降时刻，运营商将支付罚金；若超过其质变期，运营商将退还团长一定比例的生鲜品单价（商品新鲜期从城市仓发出时起计）；

（5）企业冷藏车与众包冷藏车保鲜能力相同。

1.2 模型符号

两级开闭混合冷链物流路径优化模型已知参数如表1所示。

表1 相关参数及符号Table 1 Related parameters and symbols

决策变量为：

1.3 成本变量分析

（1）固定成本

启用并完成各自配送任务的企业冷藏车和众包冷藏车都需要一定的车辆固定费用，通常由冷藏车的保养费、折旧费、制冷成本、驾驶员工资等费用组成，这部分费用与启用冷藏车数量有关。

（2）违反时间窗惩罚成本

通常在冷链配送中，运营商会与团长i约定一个其所能接受配送生鲜品的最早和最晚到达时间窗(Ei,Ui)，提前或逾期送达都会影响满意度而产生相应的惩罚成本。只有在规定时间段内送达才能保证满意度最高[23]。团长点i的交付时间与时间窗满意度Gi的函数关系如图2所示，其对应的时间窗惩罚成本函数如图3所示。

图2 交付时间窗时变满意度函数Fig.2 Time-varying satisfaction function of delivery time window

图3 满意度转化惩罚成本函数Fig.3 Conversion of satisfaction to penalty cost function

时间窗惩罚函数如式：

生鲜品送达在规定时间窗(Ei,Ui)阶段满意度最大，惩罚成本为0；若提前送达在(ei,Ei)阶段车辆将承担等待成本θ1，此时惩罚成本随时间增大而减小；若延迟到达在(Ui,ui)阶段车辆将承担迟到成本θ2，此时惩罚成本随时间增大而增大；则违反时间窗惩罚成本如式（3）所示：

（3）产品新鲜程度相关满意度惩罚成本

因为生鲜产品的特殊性，本文除考虑时间窗对满意度的影响外，还考虑送达产品品质变化对满意度的影响。产品在途新鲜度衰减主要与配送方式、配送时间、配送过程中的保护措施有关，因本文所研究运输方式为企业车辆与众包车辆混合的两级冷链运输，所以仅考虑产品品质随时间推移而逐渐降低的情况。产品品质变化主要分为三个时期，分别为新鲜期、新鲜度衰减期和质变期。如图4 所示，从城市仓发出产品时起计，当送达时间0 ＜t≤P时，团长对产品品质满意度Lt=1，t为产品在途时间，P为产品品质开始下降时刻；当送达时间P＜t＜E时，团长对产品品质满意度，E为产品即将质变时刻；当送达时间t≥E时产品质变，团长对产品品质满意度Lt=0。

图4 产品时变品质满意度函数Fig.4 Product time-varying quality satisfaction function

当送达团时间0 ＜t≤P时，无惩罚成本；当送达团长时间t≥E，惩罚成本如式：

其中，Cp为惩罚系数，C为商品单价。

当P＜t＜E时送达货物，需要受到随时间增加而增加的惩罚成本，则惩罚成本如式：

（4）碳排放成本

本文所研究碳排放成本分为油耗成本与碳排放所造成的环境污染成本。油耗分为制冷油耗和行驶油耗，行驶油耗采用负载估计法计算[24]，单位路程行驶油耗随载重的变化而变化呈一定线性关系，单位路程制冷油耗始终恒定。假设企业冷藏车k和众包冷藏车b满载单位路程油耗分别为ρkα和ρbα，企业冷藏车k和众包冷藏车b空载单位路程油耗分别为ρkβ和ρbβ，当载货量为S时，企业冷藏车单位路程油耗与众包冷藏车单位路程油耗如下：

则企业冷藏车完成对所有中转仓配送服务时，整个配送过程的油耗如式：

同理，众包冷藏车完成对所有团长的配送服务时，整个配送过程的油耗如式：

其中，ρk(Sij)为载重Sij的企业冷藏车辆从中转仓i到中转仓j的单位距离油耗，ρb(Sij)为载重Sij的众包冷藏车辆从团长i到团长j的单位距离油耗，dij为i到j的距离。

由Ottmar[25]研究可得油耗量与碳排放量呈一定的线性关系，δ为排放系数，γ为碳税，故环境污染成本如式：

整个配送过程的油耗量与油耗成本及环境污染成本呈一定线性关系，σ为油价，碳排放成本如式（12）所示：

2 模型建立

根据以上描述，以生鲜品配送过程中的固定成本、碳排放成本、违反时间窗惩罚成本、产品品质相关满意度惩罚成本的总成本最小及满意度最大为目标函数，构建基于众包模式的冷链运输两级开闭混合车辆低碳路径规划模型，如式（13）（14），式（15）表示权衡成本和满意度之间均衡的目标值。

2.1 目标函数

2.2 约束条件

式（16）表示配送网络货物流量守恒；式（17）表示中转仓被企业冷藏车服务后才能开始提供货物；式（18）表示企业冷藏车服务中转仓后必须离开，以保证配送网络连贯性；式（19）表示众包冷藏车仅从一个中转仓出发一次；式（20）表示一位团长仅由一辆众包冷藏车服务且只服务一次；式（21）表示众包冷藏车完成配送任务后在团长处停止；式（22）～（23）表示消除两级配送网络车辆子回路，|S1|、|S2|分别表示中转仓集合M及团长集合N中顶点的数量；式（24）～（25）表示各冷藏车均不超载；式（26）表示一个中转仓仅由一辆企业冷藏车服务且只服务一次；式（27）表示企业冷藏车从城市仓出发后回到城市仓；式（28）表示完成两级配送的车辆数不能超过最大可调度车辆数；式（29）表示企业冷藏车到达下一个中转仓的时间；式（30）表示众包冷藏车到达下一个团长的时间。

3 求解算法

大邻域搜索算法（large neighborhood search，LNS）[26]是启发式算法的一种，因其求解效率高效果好，常被应用于优化车辆路径方面的问题。ALNS 算法是LNS 算法的拓展。其在LNS算法破坏与修复等原则的基础上，对各算子的作用效果做了更好的衡量，使算法对解的摧毁与重建性能更优，从而增大得到局部最优解的几率。ALNS算法可以根据问题的特点，通过移除与插入算子的操作，灵活地设计邻域搜索算子的自适应能力，可拓展性更好，求解能力更强。

3.1 改进的ALNS算法

ALNS算法在局部寻优方面能力更强，有较高的概率探索到更优解，但这也导致算法容易陷入局部最优。由于本文所建模型中不仅考虑碳排放成本、路程成本，同时还需考虑时间窗惩罚成本、产品满意度惩罚成本等，所以模型求解复杂度较高。因此本文所用ALNS算法中的算子主要围绕以上几个特点进行设计。同时，引入自适应大领域算法中高效的搜索方法，如随机算子、贪婪算子、遗憾准则、轮盘赌策略来提高解的质量，并在接受新解方面创造性地加入SA 算法的思想，更好地避免局部最优。本文使用了5种破坏（移除）算子和2种修复（插入）算子。

3.1.1 初始路径生成

在每个初始解构造阶段采用贪婪插入的策略：第一步初始化一条不包含任何团长节点和中转仓节点的路径；第二步将中转仓节点在满足企业车辆载重约束的条件下，采用距离城市仓最近贪婪插入的方式将中转仓节点依次插入；第三步将所有团长节点按左时间窗升序排列，并将其中距离左时间窗最近的团长节点作为第一个点插入到路径中；第四步若当前还有未插入的节点则转到第五步，否则算法终止；第五步在满足众包车辆容量约束和团长节点时间窗约束的前提下，将所有未插入到线路中的团长节点选择一个路径成本增加最少的插入到当前线路并转到第四步，否则转到第三步。

3.1.2 破坏算子

（1）相似度移除[27]

将团长节点之间的相似度作为评判标准进行移除操作，团长节点i和j的相似度根据时间窗要求、距离和需求量计算，权重分别用α、β、ε来表示，计算公式如下：

dij表示团长节点i、j之间的距离表示团长节点i、j之间服务时间的差异，表示团长节点i、j之间需求量的差异，α、β、ε分别代表距离、时间窗、需求的权重系数本文中分别取值为4、5、6，R(i,j)的值越小则表示两节点间的关联度越高。重复移除关联度高的点直到删除若干个团长节点。

（2）最违背时间窗移除

本文考虑团长节点软时间窗和产品新鲜程度的双重时间约束要求，时间惩罚成本为超过时间窗的惩罚与超过商品质变期的惩罚，因此需要保证冷藏车抵达时间尽可能地靠近时间窗。重复移除冷藏车抵达时间对于时间窗延迟最大的团长节点。

（3）最大成本移除

重复移除对路径成本影响最大的若干团长节点，更新路径并计算路程成本，以控制成本。

（4）随机移除

从解中随机选取若干团长节点移除，来保证解的随机性。

（5）随机回路路径移除

随机选择解中总成本最大若干条路径删除路径上的若干团长节点，并更新路径，旨在保证路径的随机因素。

3.1.3 修复算子

（1）随机插入

在满足算法初始解生成的插入条件的基础上将移除的团长节点逐个插入到破坏后解的任意位置。

（2）贪婪插入

每个团长节点的插入位置由贪婪法得到，即选择此次插入位置使增加路程最小或增加时间最短。

3.1.4 动态调整权重并选择

算法迭代过程中采用轮盘赌与权重的方式进行算子破坏与修复工作。更新权重后，采用轮盘赌的思想对算子进行选择，使算子被选中的概率与其权重表现成正比。起初所有算子均具有相同的权重和分值。而在迭代过程中分数随着算子的不同表现而给分，得分愈高说明算子表现良好。设定以下4种加分情况：

1）破坏/修复后得到新的当前最优解，+2分。

2）破坏/修复后没有得到当前最优解：

（1）尚未接受过的但比当前解好，+1分；

（2）尚未接受过的且比当前解差：

①在一定标准下接受劣解，+0.5分；

②不满足接受准则的劣解，+0.3分。

算子权重更新：

式中，Wi为算子权重，Di为算子分数，Zi为算子的使用次数，ω为权重更新系数，将算子权重与以往表现挂钩。

3.2 模拟退火算法

模拟退火算法的是基于Monte Carlo 思想设计的近似寻优算法。基本原理是模拟热力学中固体退火的过程来求得最优解。算法通常从某一较高温度T0开始迭代，由Metropolis 准则在邻域内随机搜索并以一定概率接受劣解，粒子在温度T时趋于平衡的概率为exp(-ΔE(kT))，其中E为温度T时的内能，ΔE为其改变数，k为Boltzmann常数。Metropolis准则表示为：

其中，xo为旧时刻；xn为新时刻；E(xo)为xo时刻内能；E(xn)为xn时刻内能；T表示当前时刻温度。

模拟退火中从初始温度T0开始，温度按一定方式下降，直至达到截止温度Tf结束，降温方式为：

其中，H为冷却率，通常为小于1的数；t为迭代次数。

3.3 改进的ALNS算法伪代码

IALNS算法

4 实验结果与分析

4.1 实验算例与参数设置

本文选取山东省烟台市一家冷链物流企业的实际数据进行仿真分析，该物流企业主要从事于社区团购冷链商品的运输工作，选取该物流公司近一季度的服务数据进行采集取平均值。该物流公司的企业冷藏车载重为1 900 kg，车速为60 km/h，包括冷藏油耗、损耗折旧等每次启用冷藏车固定费用为100 元。众包冷藏车载重为500 kg，车速为40 km/h，冷藏车固定费用为60 元，企业冷藏车与众包冷藏车空载和满载正常行驶耗油分别为0.1 L/km 和0.2 L/km，0.06 L/km 和0.1 L/km，柴油单价为5.41 元/L，碳排放量为2.669 kg/L，碳税为30 元/t。早于时间窗惩罚为20 元/h，晚于时间窗的惩罚30 元/h，超过商品质变期的惩罚系数为0.8，各团长与中转仓的卸载时间统一为0.5 h。方便起见，中转仓设定3个固定坐标，分别为（66，43），（42，24），（5，51）。

改进的自适应大领域算法的参数设置为：因子得分增量φ1、φ2和φ3分别为3、4 和2，权重惯性因子ω=0.5，初温T0为1 000 ℃，冷却率H为0.95，终温Tf为0.001，同一温度下的迭代次数为10次。

4.1.1 IALNS算法迭代次数分析

针对上述实例参数，选取Solomon 基准算例C类中c101的数据进行适度调整，设计出包括10、20和30个团长节点的实验算例各10 个，针对30 个小规模算例进行IALNS 算法迭代次数分别为100 次、200 次和300 次的实验，实验结果如表2所示。t表示求解时长，b表示运行15次程序的最优解。

表2 IALNS算法参数实验结果Table 2 Experimental results of IALNS algorithm parameters

从表2 可以看出，IALNS 算法迭代100 次无法得出最优解，迭代200次解的质量与运行时间最佳，迭代300次耗时较长。

4.1.2 小规模数据算法对比与分析

分别采用ALNS算法、SA算法、GA算法、PSO算法和IALNS 算法对30 个企业实例数据进行10 次仿真实验，各算法最优值、平均值以及最优路径如表3所示。

表3 实例仿真算法对比Table 3 Comparison of simulation algorithms for example

由表3 可知，IALNS 算法对小规模真实算例的求解效果要优于ALNS 算法、SA 算法、GA 算法和PSO算法，求解最优值效果分别提升了5.4%、7.4%、7.0%和8.0%。

4.1.3 大规模数据算法对比与分析

为比较各算法的运算能力，分别选取并改编Solomon基准算例C 类中c101～c105、R 类中r101～r105、RC 类中rc101～rc105 共3 类15 组数据，各取前50 个节点进行对比实验，其中C 类算例节点分布形态为集群式分布，R类算例节点分布形态为随机分布，RC 类算例节点分布形态结合C 类分布和R 类分布的特征，分别采用ALNS算法、SA算法、GA算法、PSO算法和IALNS算法对以上数据进行10次仿真实验，分别记录最优值V1与平均值V2，如表4所示。各算法运行时间ts，如表5所示。

表4 各算法仿真结果对比Table 4 Comparison of simulation results of each algorithm 单位：元

表5 各算法运行时间对比Table 5 Comparison of running time of each algorithm 单位：s

从表4 和表5 可看出对于50 个节点规模的数据求解效果，IALNS 算法可以解决本文所提出的数学模型，且求解性能较为良好。在算法表现方面，IALNS算法能充分发挥搜索算子的邻域寻优能力，所得平均值和最优值都略优于其他四种经典启发式算法所求值。在求解时间方面，虽然IALNS的运行时间较长收敛较慢，但相较于另外四种传统启发式算法还是有较为突出的优越性。

综上所知，ALNS 算法相较于SA 算法、GA 算法和PSO 算法有更快的收敛时间和更良好的寻优能力，而融入SA算法思想的IALNS算法，在求解精确度和求解时间方面，相较于前四者有更好的表现。IALNS 算法求解各算例最优解所对应最优车辆路线运行图，如图5所示。

图5 IALNS算法求解各算例最优路线运行图Fig.5 Optimal vehicle running diagram of each example solved by IALNS algorithm

4.2 配送模式分析

为表明本文所提出的两级开闭混合冷链物流运输模式，在提高效率优化成本及低碳减排方面的能力，使用IALNS 算法以Solomon 数据库中C101 前30 个节点数据信息为例运行10 次取最优值，分析不同配送模式下的各项成本以及服务延迟情况，如表6所示。

表6 不同配送模式下IALNS算法优化结果Table 6 Optimization results of IALNS algorithm under different distribution modes

从表6 可以看出两级开闭混合的运输模式相较于其他三种两级闭环模式，总成本分别减少10.12%、33.03%和36.64%。在总时间方面分别减少12.07%、6.28%和17.84%。说明两级开闭混合配送在节约配送成本，降低在途时间，减少碳排放方面有积极作用。众包车辆两级闭环运输模式虽然在满足时间窗，提高满意度方面表现良好，但配送成本增加显著，不利于企业长远发展。综上，众包模式下的两级开闭混合配送策略，可以提高满意度，降低企业运输成本，同时有效缓解需求井喷环境下的物流配送压力。

5 结语

本文针对当前生鲜品社区团购冷链配送过程中，出现运力不足和满意度低的问题，提出基于众包模式的两级开闭混合冷链车辆配送策略，并考虑满意度的要求，建立以固定成本、碳排放成本、时间窗惩罚成本、满意度惩罚成本的总成本最小为目标函数的混合整数规划模型。基于传统ALNS 算法接受新解阶段容易陷入局部最优的问题，创造性地加入SA算法的思想，提出了一种IALNS 算法，提高算法全局搜索能力。通过将IALNS算法与ALNS算法、SA算法、GA算法、PSO算法以不同规模实验算例对比，表明IALNS 算法可有效缩短运算时间，提升求解质量。通过不同运输模式对比分析，验证了所提策略的合理性和有效性。未来可以将考虑客户随机需求和生鲜品多温共配的问题作为今后研究的重点。