考虑客户满意度的低碳冷链车辆路径优化

任 腾，陈 玥，向迎春，邢立宁+，李思迪

(1.中南林业科技大学 物流与交通学院，湖南 长沙 410004; 2.中南林业科技大学 旅游学院，湖南 长沙 410004)

0 引言

随着社会经济的不断发展，人们生活水平不断提高，对于生鲜食品的需求量也逐渐增加，从而促进了冷链产业的迅速发展。根据中国物流与采购联合会发布的年度报告显示，2018年我国冷链物流市场规模已达到3 035亿元。在大规模冷链配送市场环境下，如何减缩冷链物流的配送距离、降低物流成本，成为至关重要的问题。

在冷链物流车辆配送问题上，国内外已有部分学者对此进行了研究，其中Pretorius等[1]基于联合分布的思想，通过建立联合分布节点来提高冷链物流终端配送能力；Zhang等[2]考虑到常见的冷链物流、第三方物流公司需要提供温敏食品零售商节点时间窗和弧时间窗，研究了复杂车辆路径问题(Vehicle Routing Problem, VRP)；Amorim等[3]考虑多个时间窗与多车型的约束，构建了车辆配送路径优化模型。近年来，“节能减排，绿色发展”成为社会提倡的核心理念，关于车辆的低碳配送优化问题也逐渐受到专家学者的广泛关注。在油耗对车辆碳排放的影响方面，Suzuki[5]建立了以最小化油耗为目标的车辆配送问题模型，并采用压缩退火算法进行求解；Kuo[6]以速度与载重量为约束，构建了以油耗最小为目标的模型，并与最短距离、最小运行时间目标下的车辆路径问题进行了对比；Kopfer[7]在考虑距离与载重量的因素下，根据不同类型的车辆燃油量不同这一理论，对多车型低碳车辆路径优化模型进行优化；Harris等[8]研究了运输耗电产生的二氧化碳排放与总物流成本之间的关系；肖超等[9]分析了冷链配送各环节的成本，考虑车辆载重、时间窗等约束，构建了总成最小的VRP模型；肖建华等[10]考虑到城市道路限行的问题，将配送车辆分为多种类型进行车辆路径优化。与此同时，顾客满意度对于物流配送服务的重要性也促使各国学者开始对其进行研究。受生鲜食品易腐性影响，冷链配送产品保质期短、时效性强，通过维持良好的生鲜产品品质，并在客户允许的时间范围内完成物流配送，能大幅提高客户满意度[11]。在此方面，Moghaddam[12]通过对车辆配置与配送路线的整体规划来提高不确定需求下物流配送的客户满意度；左文明等[13]通过构建客户满意度动态测量模型，发现通过改善当前B2C电子商务服务流程中的物流服务质量可以显著提升顾客满意度；陈萍等[14]在分析餐饮O2O外卖客户满意度特点的基础上，提出了适合餐饮O2O外卖配送的优化模型。

现阶段，学者们大多关注配送碳排放量的优化，在理论上研究低碳等多种因素在冷链配送问题中的影响，并运用启发式算法、精确算法等智能优化算法[15-17]来解决同类VRP问题[18-19]，也有大量学者进行了在普通配送、冷链配送、电商配送、外卖配送等多种情况下的客户满意度研究，但将两因素结合，对低碳冷链配送中的客户满意度的研究却较少。对于冷链物流企业而言，可通过对冷链车辆配送路径进行优化来降低碳排放，从而实现物流配送环节的节能减排。在降低经济生产的环境代价的同时，企业经济效益的维护也不可忽视。因此，在降低冷链配送碳排放量的前提下，通过最大化提高客户满意度来实现企业经济效益的提升是有意义的。基于此，本文在分析了客户允许时间、产品变质率、距离、载重量等影响因素后，考虑车辆自身碳排放量与制冷设备碳排放量，建立了在客户允许时间内以总成本最小为目标的低碳冷链车辆路径优化模型。同时，设计了改进型蚁群算法，得到最优的车辆配送路径。

1 问题描述与假设

1.1 问题描述

本文研究单一配送中心、同车型、多车辆、多需求点的VRP，考虑车辆最大行驶距离、最大载重量等因素，在客户允许服务时间范围内求配送总成本(碳排放成本、惩罚成本)最小时车辆的配送路径。假设每一次配送车辆的起点均为配送中心，配送任务完成后返回配送中心；客户时间窗、客户服务时间、开关车门时冷链车辆内部温度、配送点地理位置和配送点需求量已知；车辆配送的货物总量不超过每辆车的最大装载量；每个配送点都能得到服务且只能由一辆冷藏车完成配送；配送过程中的车辆速度已知；车辆配送过程中货物的总重量随卸货操作而变化；通过将客户满意度转化为软时间窗、货物变质率约束来体现物流配送时企业经济效益，达到冷链物流配送中企业环境成本与经济效益的综合优化。

1.2 符号和决策变量

本文出现符号和变量较多，模型符号如表1所示，部分变量在文中首次出现时进行定义说明。

表1 符号和决策变量

续表1

2 模型构建

2.1 车辆自身碳排放量

配送车辆行驶过程中，油耗与车速及载重存在着必然的关联[20]，而车辆的碳排放主要来源于车辆行驶时的燃油废气排放，因此碳排放量与车速存在着不可忽视的联系。车辆在行驶过程中碳排放量与车速的关系式为[21]：

(1)

车辆碳排放与车辆载重也存在密不可分的关系[22]，本文将车辆因载重所产生的碳排放表示为

(2)

2.2 车辆配送过程中制冷设备碳排放量

受技术条件影响，机械冷链车是国内冷链车中的主要车型，机械链车的制冷系统由汽车发动机负责驱动，因此汽油为冷链车制冷设备所消耗的主要能源。而影响制冷油耗的因素除距离、需求量、储存要求等因素外，还有外界温度、车体的传热系数等次要因素。由于本文已假设车辆型号相同、行驶过程中车门关闭、车辆内外部温度稳定不变，由温度等因素引起的碳排放量本文不予考虑，配送中制冷设备的碳排放计算借鉴相关研究[23]，公式为：

(3)

2.3 客户满意度成本

冷链物流VRP模型中，客户时间窗与产品质量是影响顾客满意度[24]的重要因素。通过对时间窗与产品质量分别赋予权重后相加，便可求得本次配送的客户总满意度。

2.3.1 时间窗惩罚成本的计算

针对冷链配送产品时效性强、易腐性高的特点，本文采用带软时间窗约束及惩罚函数的VRP模型来描述客户对于冷链车辆配送质量的满意度。在冷链配送中，企业需要在客户规定的时间窗内送达货物，过早或者过晚送货都会在一定程度上降低客户的满意度，只有在规定时间段内送达才能保证客户满意度最高[25]。如图1所示，车辆到达时间分为5种情况，分别表示不同含义的客户满意度。客户满意度最大在模型中转换为利用惩罚成本最小[26]表示，转化后惩罚成本函数示意图如图2所示。

对应的惩罚函数表示如下：

(4)

在客户规定的时间段[ei,li]内，客户满意度最大，惩罚成本为0；在阶段[Ei,ei]中，生鲜食品如果提前送达，车辆需要增加等待成本，提前时间越长，等待成本越大，u1为等待成本系数(单位：元/h)，此时惩罚成本随时间向后推移而减小；[li,Li]阶段，惩罚成本随时间的向后推移逐渐增大，u2为迟到成本系数(单位：元/h)；在顾客允许范围外的[0,Ei]和[Li,+∞]，惩罚成本为一个极大的实数M，目标模型无解。该惩罚成本数学表达式为：

(5)

2.3.2 货物变质成本

冷链货物储存条件严格，对环境变化敏感，时间和温度的变化对货物变质影响较大，配送时间的增加以及环境温度的升高会导致变质成本增加。变质成本与两者变化正相关。在物流配送中，卸货环节是造成车厢内温度变化从而引起货物变质的主要环节。本文采用阿伦尼乌斯公式计算由于气温变化下生鲜货物的变质成本[27]，公式通常形式为：

(6)

式中：K为反应速率常数；A为阿伦尼乌斯常数；Ea为活化能；T为绝对温度；R为气体常数。

运输环节的变质成本为：

lqm1×Wj(0)=[1-e-ψ1t1]×Wj(0);

(7)

(8)

其中Wj(t)为车辆在t时刻时从配送中心到配送点j整个过程中完好货物的数量。

卸货环节的变质成本为：

lqm2×Wj(t1)=[1-e-ψ2(tj-t1)]×e-ψ1t1×Wj(0);

(9)

总变质成本为：

(11)

2.4 模型建立

综上所述，考虑顾客满意度的低碳冷链车辆配送成本模型如下：

(12)

可简化表示如下：

minC=W{P0+P1+P2}+PT+PQ。

(13)

(14)

qk≤Q，k∈K;

(15)

(16)

(17)

(18)

(19)

(20)

其中：式(14)表示车辆k从i点到j点的0-1变量；式(15)表示每个用户的需求量小于每辆车的装载量；式(16)和式(17)表示每个配送点都会被服务到，且每个配送点只能被服务一次；式(18)表示车辆配送的货物总量以每辆车的最大装载量为限；式(19)表示进行服务的车辆数不得超过总车辆数；式(20)表示每辆车从配送中心出发、返回配送中心。

3 算法设计

本文研究以总成本最小为目标的车辆路径优化问题，该问题属于NP-hard问题，对于此类问题，启发式算法[28-39]被广泛地应用，其中蚁群算法采用分布式并行计算机制，有自组织性、正反馈性与较强的鲁棒性，可以使问题在较短的时间内找到较为满意的可行解。但其搜索时间长且算法容易早熟，从而导致结果陷入局部最优。因此，本文设计改进型蚁群算法，将传统蚁群算法与局部搜索算法相结合进行两元素化(2-optimization, 2-opt)操作，并赋予信息素浓度上下限，以防止算法由于早熟影响优化效果。

3.1 蚁群算法原理

蚁群算法是由意大利学者Dorigo[40]等于20世纪90年代初提出的一种模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为，基本蚁群算法流程如图3所示。

3.2 算法改进

基本蚁群算法存在搜索时间长、易陷入局部最优和出现停滞现象等缺陷。在进行全局信息素的更

新过程中，为避免搜索停滞和过早收敛于非全局最优解，将每条边的信息素浓度限制在[τmin,τmax]之内。小于τmin的信息素值赋值为τmin，大于τmax的信息素值赋值为τmax，可以有效避免由于某条路径的信息素浓度过大而吸引所有蚂蚁迅速聚集导致搜索停滞，进而提高搜索速度[41]，信息素上下限取值公式如下：

(21)

(22)

其中：σ为第t次迭代的最优解个数，C(t)为第t次迭代所得最优解的成本值。

对于所有蚂蚁遍历之后得到的单次最优解，使用2-opt局部领域搜索[42]进行调整优化，进一步优化已求得的最优解，扩大解的搜索空间，改善种群信息结构，帮助算法大概率跳出局部最优解，提高算法搜索能力。改进型蚁群算法流程如图4所示。

基于此，本文在传统蚁群算法中引入信息素上下限与邻域搜索机制后，算法改进步骤如下：

步骤1初始化参数。初始化客户时间窗数据，客户间距离dij，客户需求量Qi。迭代次数Nc=0，最大迭代次数Ncmax，客户数量n，确定蚂蚁数量m，以及参数α、β、ρ的取值。

步骤2创建禁忌表，将m只蚂蚁全部放置于配送中心。

步骤3在满足车辆载重限制和时间窗约束的前提下，每只蚂蚁根据以下公式计算的转移概率与碳排放量来选择下一个待访问客户，ηij=1/Z。Z为车辆的配送成本，包括车辆自身的碳排放成本、制冷设备的碳排放成本、违反客户时间窗所造成的惩罚成本。

(23)

步骤4在根据转移概率选择下一个客户点时采用轮盘赌选择策略[43]，避免选取选择概率最大客户点，有效避免在概率相近时忽略可能的最优解。引入随机可能性，有效防止过早收敛。

步骤5更新禁忌表，重复该过程，直至所有蚂蚁都遍历所有客户点并返回配送中心。禁忌表更新满足时间窗限制与车辆载重限制。

步骤6对单次最优路径及其成本C(0)使用2-opt方法进行邻域搜索，交叉得出路径所对应的成本C(t)。

步骤7判定C(t)是否小于C(t-1)，是则输出C(t)，否则输出C(t-1)，当t达到最大设定值时更新全局信息素，否则重回邻域搜索循环，t=t+1。

步骤8所有蚂蚁完成周转后，对信息素进行全局更新，同时为避免搜索停滞，把每条边的信息素浓度限制在[τmin,τmax]之内。信息素更新公式采用蚁周模型：

(24)

步骤9判断是否满足结束条件(连续5次不再产生更优的解或已达到蚁群算法规定的迭代上限)；若不满足，则返回步骤3开始新一轮循环，Nc=Nc+1。

步骤10收敛过程达到规定最大迭代次数后终止迭代，输出最优总成本及对应配送路径。

4 算例分析

4.1 已知条件

本文以长沙市某冷链中心作为配送中心，选取其10公里范围内的48个小区作为配送点。设配送中心编号为l0，48个配送点的编号分别为li，(i=1,2,…,48)。设定W为单位碳排放成本系数，W=0.04；固定值系数α0=1.576，α1=-17.6，α2=0.001 17，α3=36.067；β=0.075 1；θ=0.006 6；车辆行驶过程中车厢内温度为5℃，配送点进行卸货时车厢内温度升高0.7℃，利用公式T(K)=273.15+t(单位：℃)将摄氏温度转化为热力学温度，T1=278.15，T2=278.85；阿伦尼乌斯公式中Kmax=5×1 014(单位：s)，Ea=100(单位：kJ/mol)，R=8.314(单位：J/mol·K)。

如表2所示，选取其中10个配送点的坐标(需求点1为配送中心)以及每个配送点的需求量、服务时间、客户时间窗为例。每辆车的最大载重量为Q=15，车辆匀速行驶，速度为S=60 km/h。为了研究方便，本文以配送节点间的直线距离作为配送距离，并未考虑交通拥堵等路段实际因素。

表2 配送需求点及配送中心基本信息

4.2 运算结果

本文采用MATLAB R2014a编程软件进行求解，所用平台基本信息如表3所示。

表3 实验测试环境

编程语言为MATLAB语言。按照前文所描述的蚁群算法步骤进行编程，以碳排放量成本及满意度成本最低为目标，将已知的需求点坐标、需求量等代入程序，令信息素重要程度因子α=1，启发函数重要程度因子β=3，信息素全局挥发因子ρ=0.4，蚂蚁数量m=20，信息素释放总量Q=15，最大迭代次数为200。进行30次模拟仿真实验后，最优车辆路径如图5所示，总成本最优值收敛情况如图6所示。

传统蚁群算法以最短距离为目标输出车辆最优路径，改进型蚁群算法以碳排放成本与顾客满意度成本最低为目标输出车辆最优路径。二者对比情况如表4所示。

表4 改进前后路径结果对比

改进型蚁群算法下以最短距离为目标的最终结果，改进型蚁群算法下以考虑碳排放与顾客满意度成本为目标最终结果，横向对比情况如表5所示。传统蚁群算法以考虑碳排放与顾客满意度成本为目标最终结果，改进型蚁群算法下以考虑碳排放与顾客满意度成本为目标最终结果，纵向对比情况如表6所示。

表5 模型改进前后路程、成本、时间对比

表6 算法改进前后路程、成本、时间对比

4.3 结果分析

从对比表4可以看出，改进型蚁群算法下以考虑碳排放与顾客满意度成本为目标的车辆最优路径结果中，配送中心需要派遣7辆冷藏运输车对48个需求点进行配送，其路径安排与传统蚁群算法下以最短距离为目标模型相比有很大差别。

从对比表5可以看出，以最短距离为目标的模型与以考虑客户满意度时碳排放最低为目标的模型的出车总数相同。与此同时，未考虑碳排放成本的配送路径方案的总路程为103 250 m，考虑碳排放成本及满意度成本方案的最优车辆配送路径所对应的配送总路程为104 350 m，比未优化前增加1.1%。最短距离目标方案总路程并未明显优于考虑满意度及碳排放成本方案的总路程。7辆冷链运输车辆全勤时，以最小距离为目标，总的碳排放量及满意度相对成本为7 080 700，相比以碳排放成本最小为目标时的总成本5 435 902增加了30.3%，后者明显小于前者。最终方案总路程稍有增加，但配送总成本明显下降。

从对比表6可以看出，在程序运行时间上，传统蚁群算法耗时79.7 s，改进型蚁群算法耗时76.2 s，算法收敛时间减少3.5 s。总路程及碳排放满意度总成本都有所减少，2-opt帮助算法跳出局部最优解，再次对解进行了优化。测试算例达到预期效果，优化后的配送方案更符合低碳经济以及顾客满意度的要求。

4 结束语

当代社会低碳经济迅速发展，在物流企业降本增效的前提下，还需降低企业经济发展的环境代价，促进物流与生态文明的协调发展。本文在考虑碳排放与客户满意度的前提下，针对当前冷链配送过程中碳排放高而客户满意度低的问题，构建了带时间窗的冷链车辆配送模型，利用MATLAB编程求解模型。基于传统蚁群算法收敛速度慢、易于早熟的特点，引入了信息素上下限与邻域搜索操作，应用改进型蚁群算法对模型进行求解优化。实验结果表明，改进型蚁群算法具有更优的运算效率与优化效果。同时，以碳排放与客户满意度为目标的车辆路径优化中，降低企业经济成本与节能减排并不冲突，所得配送方案更符合低碳经济以及企业发展的要求。本文研究为冷链物流配送企业在降能增效的要求下制定车辆配送路径方案提供了参考，使得企业发展更符合打造绿色物流、发展绿色经济的要求。