张亚明，李艳明，刘海鸥

（燕山大学 经济管理学院，河北 秦皇岛 066004）

0 引言

目前,针对冷链物流VRP调度优化方面的研究[1-9]仍然处于初级阶段，主要集中在优化VRP模型或改进求解算法方面。在优化模型上：一方面，关于多车型冷链VRP模型目标成本构成分析不够全面，少有文献考虑多车型冷链VRP问题；另一方面，基于冷链物流特性，顾客满意度主要由配送时间及品质两因素约束，而文献大多集中在时间窗的考虑，少有文献在构建多车型模型时将时间与品质同时考虑进顾客满意度约束中。在改进算法上，传统遗传算法的寻优效率也劣于单亲遗传算法。因此，本文在模型上，根据阿伦尼乌斯方程推导货损成本，利用冷藏车制冷及操作原理计算能源成本，运用投入产出法计算碳排放成本，并得到时间及品质的满意度函数作为约束条件之一，建立更加贴近实际的多车型冷链VRP模型；在算法优化上，采用改进的基于局部精英保留策略的单亲遗传算法进行求解，量化分析单车型配送和多车型配送时的成本差异，以探究多车型在冷链调度中的优势，同时得到顾客满意度在成本优化过程中的变化趋势，为企业寻求成本和满意度均衡提供理论参考。

1 满意度约束冷链物流VRP模型构建

1.1 问题描述及假设

首先，满意度约束冷链物流VRP问题旨在保证顾客满意度不低于一定水平的情况下，寻求最优综合成本，允许牺牲一定的成本来提高满意度。VRP问题中影响顾客满意度的主要因素是配送准时性与产品品质；其次，顾客对生鲜品的需求差异较大（如对瓜果、蔬菜的需求量较大，而对肉、蛋、奶、海鲜的需求量较小），若运用单一车型完成配送，极有可能使其非满载运行，导致配送成本上升[10]。因此，模型选择多车型配送模式是可行的；最后，冷链物流是整个物流系统中能源消耗与碳排放量都极高的产业，这与当前主张“低碳经济”的宗旨发生冲突。因此，在模型中加入低碳因素是大势所趋。综上所述，模型构建需要解决的问题是：如何在多车型模式中合理调度车辆，规划路径，在最大程度满足顾客情况下，使总配送成本最低。问题假设如下：

（1）一个配送中心且货源足够，多辆不同型号的冷藏车；

（2）顾客需求量总和不超出车载容量限制；

（3）冷藏车行驶速度均为匀速；

（4）配送任务只涉及货物的配送，即单向流向；

（5）配送车辆要求必须从配送中心发出并返回；

（6）客户均被服务且仅接受一次服务，已知所有客户的地理位置、需求量、接受服务时间范围并固定不变；

（7）冷藏货物的品质仅与温度及配送时间有关；

（8）员工工资计入调用每辆冷藏车的固定费用中；

（9）卸货速度均相同且为匀速。

1.2 符号描述

（1）标号

N{n|n=1,2,…,N}为顾客集合；K{k|k=1,2,…,K}为配送车辆集合；L{l|l=1,2,…,L}为配送车型集合。

（2）参数

Q为车辆最大载重；qi为顾客的需求量；v为车辆平均行驶速度；dij为顾客i到j之间的距离；pf为每辆车的固定费用；pc为车辆每公里运输费用；c1、c2分别为单位时间车辆等待和迟到产生的成本；[EETi,LETi]为顾客最大接受服务的时间范围；[ETi,LTi]为顾客期望被服务的时间范围；Hti为车辆在顾客i的卸货时间；ce为单位制冷成本；C为消耗每单位CO2排放量的环境成本；u为柴油的CO2排放系数；f为每公里燃油消耗量；P为损失货物的单位惩罚成本；ω1、ω2分别为时间满意度和品质满意度的权重；l为顾客满意度的最低值；m为l型车辆为l型车辆的第m辆服务的顾客数量为l型车辆的第m辆服务的第j个顾客。

（3）变量

ti为车辆到达顾客i的时间；L(tj)为顾客j对送货时间的满意度；Dtj、Htj、Wtj分别表示车辆到达客户 j时的累积运输时间、处理时间、等待时间；s1、s2表示顾客的平均时间满意度和平均品质满意度；s表示顾客总体满意度。

1.3 冷链物流成本

总成本包括车辆固定、运输、时间、货损、能源与碳排放成本，此处只分析货损、能源与碳排放成本。

1.3.1 货损成本

冷链物流的货损成本主要受时间和温度两个因素影响。一方面，生鲜品随时间积累而腐坏变质；另一方面，由于对温度的高度敏感，装卸过程中的温度变化，使得生鲜品腐坏变质。

根据化学家阿伦尼乌斯提出的反应速率常数与温度之间关系的方程推导得出未变质率货损成本DC可表示为：

1.3.2 能源成本

能耗成本主要指制冷机组工作所需的油耗及其在正常工作中的不可逆损失。卸货过程中，根据冷藏车运输操作流程，以及吕宁等人的研究结论（开门过程中，制冷机组对冷藏车内空气温升的抑制作用不大[12]）可知，制冷机组需关闭，因此卸货过程不计能耗；运输过程中，为保持车厢内适宜温度，制冷机组开启，产生能耗成本。本文研究中长距离运输，宜使用独立式制冷机组，即等待过程虽然冷藏车发动机熄火但制冷机组仍保持工作，产生能耗。综上，能源成本EC可表示为：

1.3.3 碳排放成本

计算温室气体排放首要指标即对CO2排放量进行计算，这一指标即为冷链物流配送过程中的平均温室气体排放量。CO2排放量计算基本原理是按照生命周期定义进行演变，本文根据冷链物流VRP模型的特点，由刘宇等人的研究方法（投入产出法计算CO2排放量[13］），CEC计算公式为：

1.4 满意度分析

顾客满意度的限制约束有两个，即时间满意度和品质满意度。首先，建立时间满意度函数。车辆须在顾客期望时间范围内进行配送任务；超出期望时间且在最大接收服务时间范围内进行配送任务时，时间满意度与时间呈负相关；超出最大接收服务时间时，顾客拒绝服务。基于混合时间窗的时间满意度（见图1）。品质满意度影响因素主要由变质率决定。顾客的总体满意度是对两个约束因素赋予一定权重相加得到。

图1 基于混合时间窗的时间满意度

则顾客满意度可表示为：

2 单车型与多车型冷链VRP模型构建

2.1 单车型

由以上分析可得单车型冷链VRP模型：

其中：式（5）表示冷链VRP总成本，各项分别为冷藏车调度成本、运输成本、货损成本、能源成本、碳排放成本、早到的等待成本与晚到的惩罚成本；式（6）为车辆载重限制；式（7）为配送中心车辆数限制；式（8）为前序节点唯一；式（9）为后序节点唯一；式（10）为顾客仅由一辆车服务一次；式（11）为每个顾客均被服务；式（12）为配送车辆只能在最大接受服务时间段内到达；式（13）为抵达客户i的时间即抵达i时的累积行驶与累积等待和累积卸货三个时间之和；式（14）表示客户对时间和品质的整体满意度不低于λ。

2.2 多车型

多车型配送成本与单车型的成本构成相同，模型表示为：

模型除需满足式（12）至式（14）外，还需满足：

其中：式（15）表示冷链多车型VRP总成本，为目标函数表示总成本最小；式（16）为车辆载重限制；式（17）确保车辆从配送点发出并返回；式（18）为每个顾客均被某种车型的车服务；式（19）为车流量守恒式，即对于每个顾客点进入的车辆一定要离开。

3 改进单亲遗传算法求解模型

在传统遗传算法TGA（Traditional Genetic Algorithm）中，其交叉算子为双亲，求解复杂模型时效率较低，并且具有“早熟收敛”的特点。单亲遗传算法PGA（Partheno Genetic Algorithm）是传统遗传算法的变形，在繁殖方式上为单亲繁殖，即在单条染色体上进行繁殖，改变了传统遗传算法的双亲式繁殖，采用自身内部进行染色体进化的方式，初始群体质量要求降低，较易生成初始解，不再采用交叉算子，优化了传统GA的弊端，加快了运行速度。

求解单车型VRP模型的遗传算法设计同文献[9]。多车型VRP求解涉及车型载重限制，问题复杂，进行染色体编码及种群初始化需考虑车型最大载重约束及顾客时间窗约束。

3.1 染色体编码

本文选用“先路径，后客户”原理进行染色体编码，即以第一条路径的首个访问顾客点作为染色体的首个基因，之后对所有染色体编码X=(x1,x2,…,xn)，均按照顾客访问顺序执行。多车型冷链VRP模型单亲遗传算法染色体编码的具体操作步骤为：

第一步：随机选取一个顾客作为第k条染色体X的首个基因，X每更新一次，k+1。标记车辆抵达第一个顾客时的时间以及所载货物重量，从左向右依次将符合车载约束、顾客接受配送时间窗约束的顾客添加到当前染色体中，并同步更新冷藏车的载重量及行驶时间；

第二步：对所有客户按照上述约束条件进行添加，构成一条完整的满足车载容量限制及时间窗约束的路径k；

第三步：染色体X的顾客访问顺序保持不变，去除顾客点对应基因，得到新的基因排列串Y，命为X；

第四步：对新的染色体X执行第一步，产生第k+1条染色体。经过多次循环操作，直到全部顾客点基因安排完毕，产生全部路径。

3.2 种群初始化

初始种群作为种群进化的初始步骤，是关键环节，选择恰当的种群初始化方法有助于完成高速度收敛、高效率运行的算法操作。针对多车型VRP模型，算法的种群初始化具体如下：

第一步：根据车型匹配约束对全部顾客进行分类排列。例如顾客点2、顾客点4均可由车型A完成配送任务，则将顾客点2及顾客点4排列一队；当顾客点能够同时由多车型完成配送，则将该顾客点随机分配在其所匹配车型队列中；

第二步：生成初始种群首条染色体。按照时间窗下界的早晚顺序依次排列，当两个顾客[EETi,ELTi]下界ELTi相同，则对其按照EETi早晚次序依次排序；

第三步：随机生成剩余染色体。即顾客点随机排列。

通过车型、顾客需求及时间窗的约束对顾客进行访问顺序排列，从而得到一条较好的染色体，有助于算法在进化初始有一个良好的起点。且剩余染色体采用随机生成的方法能够使初始种群的基因分布较为均匀，避免了解的偶然性。

3.3 适应度函数

在GA求解中，适应度f越大的染色体，保留的可能性越大，目标函数值Z则应越小，因此适应度f和总成本Z的关系呈负相关。本文将Zi代表第i条子路径所产生的总成本，用fi=1/Zi作为适应度。

3.4 遗传算子设计

本文采用局部精英策略的单亲遗传算法算子设计，操作步骤同单车型。不涉及交叉算子及变异算子的概率，并且交叉和变异的基因位置为随机抽取。操作流程为将局部最优染色体先后分别进行三种双基因段交叉操作、单基因段变异操作、变异与交叉操作，从而得到7个子代。

4 实证分析

4.1 基本数据

设有30个客户信息如表1所示，3种车型基本信息见表2。假设配送路程均使用直线距离，模型中参数设置为：v=60km/h，柴油价格为6.48元/升。u=2.68，C=0.25元。ce=50元/h；P=2000元/t。λ=0.6，ω1=ω2=0.5，c1=100元/h，c2=400元/h。

4.2 单车型冷链VRP求解

选用车型B完成配送服务。顾客总需求量为29.7吨，由于装卸货物复杂程度较高，取α=0.5，初始车辆k=11。经试验，融合概率merging_prob=0.4，种群规模pop_size=400，最大进化代数num_iter=400时达到最优，超载惩罚系数为1000，满意度惩罚系数为10。

算法运行总时间为253.74s，最优解首次出现在178代，平均满意度为0.77。结果见图2至图4。

图2 单车型冷链VRP结果图

图3 冷链VRP染色体进化图

表1 客户信息

表2 3种冷藏车车型参数

图4 冷链VRP满意度曲线

4.3 多车型冷链VRP求解

由于车型由单车型增加到3种车型，种群规模也要随之增加，经试验，融合概率merging_prob=0.4，种群规模pop_size=600，最大迭代次数num_iter=600时达到最优。算法运行总时间为295.63s，最优解首次出现在186代，平均满意度为0.72。结果见下页图5至图7。

图5 多车型冷链VRP结果图

图6 多车型VRP染色体进化图

图7 多车型VRP满意度曲线

4.4 结果分析

由图2及图3看出，算法取得了较为满意解，且收敛速度较快。图4显示，顾客满意度总体趋势为先升后降最终趋于较优而非最优，意味着企业在实际冷链配送过程中不能一味追求低成本而忽略顾客满意度。

由图5和图6看出，算法在求解多车型冷链VRP也取得了较为满意的结果，并具有较好的收敛性。图7顾客满意度曲线变化趋势符合算法优化过程。通过对比单车型和多车型求解结果（见表3），可以看出多车型目标成本更低，虽然满意度稍低，但已达到约束要求，且结果更加稳定。由单车型和多车型各项成本对比发现，多车型较单车型除运输成本稍高外，其他各项成本均明显低于单车型，尤其是占据总成本比例最高的货损和能源成本明显有较大程度降低，建议企业面对大规模配送问题采用多车型配送模式。

5 结论

针对冷链配送特殊性，本文考虑基于时间和品质因素的满意度函数的约束条件以及选择混合时间窗和具有多车型VRP问题进行研究，建立了更加符合冷链物流特性的VRP模型，详细分析了货损成本、能源成本和碳排放成本。设计局部精英单亲遗传算法求解，验证了该算法在求解VRP问题上具有一定的优越性，量化分析了多车型冷链配送成本的优势，为企业在多车型配送模式的决策提供理论参考。同时，揭示了顾客满意度在成本优化过程中的变化趋势，启示企业在实际冷链配送过程中不能盲目追求低成本而忽略顾客满意度，为后续深入研究成本与顾客满意度的权衡提供参考价值。

表3 单车型和多车型结果对比