生鲜食品冷链物流配送路径优化

张云川　邹婷

摘要：随着人们生活水平的提高，生鲜食品的新鲜度越来越受到重视，这就对生鲜食品冷链物流的配送提出了更高要求。因此，在现有第3方冷链物流配送路径优化研究的基础上，建立新的成本和约束模型，并给出采用模拟退火算法的优化方法。模型考虑了车辆行驶速度和载重量对运输能耗的影响，区分了车辆在途和装卸阶段的制冷能耗，用指数函数而不是常数来刻画食品的变质速率，运用模拟退火算法对算例进行求解。结果表明，更全面地考虑上述因素得到的配送路径与现有文献中给出的路径明显不同，前者的总成本可以减少约11%。

关键词：路径优化;冷链;生鲜食品;模拟退火算法

中图分类号： F252  文献标志码： A  文章编号：1002-1302（2019）03-0315-04

食品冷链是指将易腐食品从产地收购或捕捞后，经过产品加工、贮藏、运输、分销、零售环节，最后到消费者手中，其各个环节始终处于产品所必需的低温环境下，以保证食品质量安全，减少损耗，防止污染的特殊供应链系统[1]。冷链物流中重要的一环就是配送，在配送过程中为制冷会消耗大量的能源。因此，研究冷链配送的优化对降低企业的经济成本和社会的碳排放成本都具有重要意义。

关于国内外对冷链物流配送优化的研究主要总结了以下3个方面。

（1）冷链物流配送成本构成研究

杨珍花等在分析冷链物流配送成本构成的基础上构建冷藏车多车型混合配送调度优化模型，开发混合模拟算法，并对比分析了不同车型组合下配送成本的差异，但模型中对制冷成本的分析不够深入[1]。Kuo重点研究了车速随时间变化的车辆路径问题，将车速和载重作为能源消耗的影响因素[2];石兆等以运输、冷藏、货损和惩罚成本最小为目标，建立数学模型，在惩罚成本中考虑路况的实时变化，并运用二阶段混合遗传算法求解算例[3];缪小红等研究了第3方冷链物流配送路径的优化问题，以运输成本、货损成本、惩罚成本三者之和最小为目标构建冷链物流配送路径的基本模型，但对能耗考虑得比较粗略[4];王海丽等建立了以包括制冷成本、车辆固定成本和运输成本在内的总成本最小为目标函数的易腐食品冷藏配送模型，但模型中忽视了由于货物提前到达或延迟到达而付出的惩罚成本以及易腐食品的货损成本[5];吕俊杰等构建了基于冷藏车能耗成本分析的冷链物流配送路径优化模型，但模型中对惩罚成本的分析不足[6];李娜等构建了不确定需求下易腐产品的生产配送优化模型，解决了易腐产品的生产配送联合决策问题，但模型中将易腐产品的变质速度设为固定的常数，与现实情况不太相符[7]。李进等提出了以能耗、碳排放和租车总成本最小为目标的低碳路径问题（LCRP），并考虑了速度和载重对总能耗的影响[8]。

（2）食品质量损失研究

Rong等在计算货损成本时充分考虑了产品的质量水平，构建混合整数线性规划模型并进行求解[9];Zanoni等分析了生鲜产品质量下降率和制冷所需要的能量与产品温度的关系，研究发现产品质量、货损成本和供应链连续性与温度和库存时间密切相关[10];Yu等利用指数函数计算食品衰减量[11];Kuo等提出通过提高车辆利用率来保证产品质量和运输安全[12]。本研究将在已有研究的基础上对配送过程中的货损成本进行刻画。

（3）车辆路径优化模型求解方法研究

Brito等运用模糊方法和混合GRASP-VNS启发式算法进行配送优化[13];Zhang等通过实时动态地收集冷链配送过程中产品的信息，利用三阶段调度控制决策模型，做出更合理的决策[14];Zhang等将径向基函数神经网络、模糊控制和数据分析方法进行结合[15];Choi等研究了线路优化模型的求解算法，将不同的算法进行比较，得出较优算法[16-18]。

综上所述，现有文献已从不同的角度研究了冷链物流的优化问题，并取得了较多的成果。关于第1个方面的研究，现有文献提出的模型未能充分考虑不同阶段的能耗成本以及各阶段对其产生影响的因素，将车厢剩余货量和车厢面积等因素单独考虑，在实际配送过程中，影响配送路径选择的因素十分复杂，须要更加全面综合地考虑各因素。

本研究基于冷链配送的特性，考虑的成本因素包括运输能耗成本、货損成本、制冷能耗成本、惩罚成本，以这4项成本总和最小作为目标函数，与约束条件一起建立数学模型，求解目标最小值。其中，运输能耗成本主要考虑车辆在行驶过程中的油耗成本，利用指数函数来表示食品随时间变化的货损成本，在计算制冷能耗成本时，充分考虑不同阶段的影响因素。

1 模型建立

1.1 问题描述

问题的实质是第3方冷链配送企业的一个配送中心对多个食品零售商的配送问题。已知客户数量、地理位置、需求量和时间窗，在满足所有客户需求量和时间窗的前提下，合理优化配送路径，达到考虑冷链特征的物流配送系统总成本最小的目标。车辆配送过程可分为车辆在途阶段和装卸阶段（图1）。

1.2 模型假设

建立的数学模型基于以下假设条件。

（1）单一配送中心，配送中心的总货量大于所有零售商的需求量;（2）车辆从配送中心出发，完成任务后返回配送中心;（3）已知零售商数量、需求量、地理位置及时间窗;（4）配送中心对零售商的服务都采取整车配送的策略，每个零售商仅由1辆车服务1次，所有零售商都能得到服务;（5）车辆只负责送货，即单向物品流向;（6）所有零售商所需商品都由配送中心供给，零售商之间不存在相互调剂的情况;（7）配送车辆的车型相同，即单一车型配送，且每条线路上的送货任务只由一辆车承担;（8）运输路线上客户的总需求量小于单车的容量;（9）各零售商的需求量确定，并在一定时期内相对稳定。

1.3 符号说明

1.3.1 参数

G表示配送网络，G=（V，E）;V表示节点集，V={0，1，2，…，n}，0表示配送中心，其余节点表示客户;E表示弧集，E={（i，j）|i，j∈V，i≠j};Rkr表示第r条路径上第k个客户的编号，例如第2条路径为0-1-3-7-0，则R22=1;m表示配送中心拥有的冷藏车数量，{1，2，…，u，…，m}为冷藏车的集合;λ表示单位油耗的费用，元/L;Du表示冷藏车辆u的载重量，t;vij表示车辆从客户i到客户j的行驶速度，km/h;dij表示任意2个客户i、j之间的距离，km;P表示食品的平均单价，元/t;qi表示客户i的需求量，t;Li表示客户i的卸货效率;tij表示车辆从客户i到客户j的行驶时间，h;si 表示车辆在客户i处的卸货时间，h;a表示冷藏车早于客户要求的时间窗上限（但不早于可接受的时间窗上限）到达时，单位时间的惩罚系数;b表示冷藏车晚于客户要求的时间窗下限（但不晚于可接受的时间窗下限）到达时，单位时间的惩罚系数。

1.3.2 状态变量

tit表示u到达客户i的时刻;tju表示车辆u到达客户j的时刻;t0表示车辆u从配送中心出发的时刻。

1.3.3 决策变量

1.4 冷链配送成本构成分析

本研究考虑的成本因素除了常规的运输能耗成本，还包括食品配送过程中因其变质而造成的货损成本，因车辆到达时间超出客户要求的时间窗而付出的惩罚成本，以及冷藏车制冷机组运转而产生的制冷能耗成本。

1.4.1 运输能耗成本  运输能耗成本主要考虑配送车辆油耗成本，暂不考虑其他成本因素。目前大多数研究中将运输能耗成本描述成与车辆行驶里程数成正比的函数，考虑的因素不够全面。其实行驶速度和车辆载重也对能源消耗有着很大的影响，本研究参考文献[2，8]，将行驶里程、车辆行驶速度和载重量都纳入考虑的范围。

若额外载重量W带来油耗的增加率为p1，那么当该车辆从节点i到节点j的载重为Hij时，行驶该路段的实际油耗FCij为

式中：单位时间的油耗LPHij=vijKPLij，KPLij为一辆空载车辆从节点i到节点j的单位燃油行驶里程，Hij为车辆从节点i到节点j的载重量。因此，总的运输能耗成本C1为

1.4.2 货损成本 冷链食品腐败的主要原因是微生物的繁殖，随着腐败量的积累，腐败部分与正常部分的接触面积会越来越大，其腐败速度也随之加快，将其腐败速率设为常数不够准确[1]。文献[1]利用指数函数来刻画冷链食品腐败量随时间的变化，本研究采用相同的原则，将货损成本B（i）表示为

1.4.3 惩罚成本 本研究假设冷藏车到达客户处即开始卸货，不存在等待卸货时间。存在2个时间窗，即客户可接受的时间窗[ti1，ti2]和客户要求的时间窗[ti3，ti4]，冷藏车在ti1之前到达或者ti2之后到达，将付出较高的惩罚成本M（M为足够大的正数）;到达时间在[ti3，ti4]内，惩罚成本为0;到达时间在[ti1，ti3]内，单位时间的惩罚系数为a;到达时间在[ti4，ti2]内，单位时间的惩罚系数为b，则车辆u在tiu时刻到达客户i所付出的惩罚成本F（tiu）的函数图像见图2。

1.4.4 制冷能耗成本 杨珍花等令制冷能耗成本与车厢内剩余货量成正相关进行求解，但未对装卸过程中产生的制冷能耗成本的影响因素进行细致深入的分析[1]，王海丽等分析了车辆行驶途中和打开车门时消耗的制冷成本，未考虑车厢内剩余货量这一因素[5]。本研究整合文献[1]和[5]提出的模型，考虑2个阶段的制冷能耗成本，即车辆在途阶段和装卸阶段。

式中：Hu表示第r条路径中客户的总数;Qr表示第r条路径中所有客户需求总量;Ak′表示该路径中前往第k′客户时，车上剩余载货量。因此，这一阶段的制冷能耗成本C21可以表示为

式中：G表示制冷剂消耗量;c1为常数;R为热传导系数，W/（m·K）;S为车厢平均表面积，m2;ΔT=Tw-T0为外界温度Tw与车厢内温度T0之差，K;决策变量xijh描述当车辆完成配送任务返回配送中心的路途中不需要开启制冷设备的情景;p2表示车辆在单位时间，载有单位质量时消耗的制冷成本。

（2）装卸阶段

在这一阶段，主要考虑车门开启时车厢内外热交换带来的制冷能耗成本，可将这一阶段的制冷能耗成本C22表示为

式（4）表示同一个客户只能由同一辆冷藏车服务;式（5）表示不能重复服务同一客户;式（6）表示冷藏车所载货物的质量不超过其载重量;式（7）表示到达连续服务的2个客户时刻的递推关系;式（8）保证冷藏车到达客户u的时刻满足客户可接受的时间窗;式（9）表示每条路径的出发点和终点均为配送中心。

2 算法设计

根据模型特点，本研究采用模拟退火算法進行求解。设置算法的初始温度T0为1 000，终止温度为0.001，降温速率δ为0.9，各温度下的迭代次数为500，算法步骤如下。

第1步：初始化各项算法参数，随机产生一个初始解;第2步：计算迭代次数，初始化目标值矩阵及每代的最优路线矩阵;第3步：更新迭代次数，产生新解;第4步：根据梅特罗波利斯（Metropolis）法则判断是否接受新解，若目标函数增量Δt′<0，则接受当前新解，反之以概率exp（-Δt′/T）接受新的当前解;第5步：记录每次迭代过程的最优路线，找出当前温度下最优路线，如果当前温度下最优路线所得成本小于上一路线的成本则记录当前路线，反之则记录上一路线;第6步：降温，T0逐渐减少，返回第3步;第7步：如果满足终止条件，则输出当前解作为最优解，算法结束。一般取连续若干个新解都没有被接受时终止算法。

3 算例分析

3.1 算例验证

为验证算法的有效性，本研究给出10个客户数的算例进行分析，模型中的相关参数及取值见表1，配送中的速度类型比见表2，各速度类型的速度值见表3，各零售商之间的距离及需求量见表4，时间窗约束和服务时间见表5。优化的目标是在满足客户需求量和时间窗以及车辆载重量约束的前提下，合理安排配送路线，达到配送系统总成本最小。

3.2 结果分析

通过计算，得到的较优配送方案为安排3辆车进行配送，3辆车访问客户的顺序分别是0-4-6-5-0;0-2-7-10-8-0;0-9-1-3-0。缪小红等给出的较优配送方案为安排2辆车进行配送，客户的访问顺序分别为0-9-1-3-4-2-0，0-8-6-7-10-5-0，其给出的总配送成本仅为2 762元，主要原因是将货损系数设为固定常数，并且没有充分考虑制冷带来的能耗成本，导致其对总成本的估计与现实相差甚远[4]。按照本研究模型计算的2种配送方案下的相应成本见表6。从2种配送方案的总成本进行分析，前者比后者的总成本降低约11%。

4 结束语

本研究分析了冷链配送成本的构成，并在此基础上建立了相关成本函数，包括运输能耗成本、货损成本、惩罚成本、制冷能耗成本，以这4项成本之和最小为目标建立了考虑制冷能耗成本的冷链物流配送路径优化模型，设计了模拟退火算法进行求解。通过一个算例验证了算法的可行性，将结果与此前文献提出的最优路径相对比，发现减少了实际配送成本。虽然算例只是一个特例，不能证明在一般情况下成本减少的幅度，但从原理上可以保证本研究提出的模型和算法找到的路径是较优的。

后续研究将关注不同变质速率食品混合、使用多种车型配送等更接近实际的情形;蓄冷式配送的成本构成和温度变化特征与制冷式配送不同，也值得研究。

参考文献：

[1]杨珍花，赖平仲，汤 洋，等. 冷藏车多车型混合配送调度优化[J]. 系统工程，2015（10）：28-36.

[2]Kuo Y. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem[J]. Computers & Industrial Engineering，2010，59（1）：157-165.

[3]石 兆，符 卓. 时变网络条件下带时间窗的食品冷链配送定位——运输路径优化问题[J]. 计算机应用研究，2013，30（1）：183-188.

[4]缪小红，周新年，林 森，等. 第3方冷链物流配送路径优化研究[J]. 运筹与管理，2011，20（4）：32-38.

[5]王海丽，王 勇，曾永长. 带时间窗的易腐食品冷藏车辆配送问题[J]. 工业工程，2008，11（3）：127-130.

[6]吕俊杰，孙双双. 基于鲜活农产品冷链物流配送的车辆路径优化研究[J]. 广东农业科学，2013，40（9）：178-181.

[7]李 娜，王首彬. 不確定需求下易腐产品的生产配送优化模型[J]. 计算机应用研究，2011，28（3）：927-929.

[8]李 进，傅培华，李修琳，等. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学，2015，23（10）：98-106.

[9]Rong A，Akkerman R，Grunow M. An optimization approach for

managing fresh food quality throughout the supply chain[J]. International Journal of Production Economics，2011，131（1）：421-429.

[10]Zanoni S，Zavanella L. Chilled or frozen？ Decision strategies for sustainable food supply chains[J]. International Journal of Production Economics，2012，140（2）：731-736.

[11]Yu M，Nagurney A. Competitive food supply chain networks with application to fresh produce[J]. European Journal of Operational Research，2013，224（2）：273-282.

[12]Kuo J C，Chen M C . Developing an advanced Multi-Temperature Joint Distribution System for the food cold chain[J]. Food Control，2010，21（4）：559-566.

[13]Brito J，Martinez F J，Moreno J A，et al. Fuzzy optimization for distribution of frozen food with imprecise times[J]. Fuzzy Optimization & Decision Making，2012，11（3）：337-349.

[14]Zhang J，Shi J，Lou E P，et al. Optimizing distribution strategy for perishable foods using RFID and sensor technologies[J]. Journal of Business & Industrial Marketing，2010，25（8）：596-606.

[15]Zhang K，Chai Y，Yang S X，et al. Pre-warning analysis and application in traceability systems for food production supply chains[J]. Expert Systems with Applications，2011，38（3）：2500-2507.

[16]Choi E，Tcha D W. A column generation approach to the heterogeneous fleet vehicle routing problem[J]. Computers & Operations Research，2007，34（7）：2080-2095.

[17]Leung S C H，Zhang Z，Zhang D，et al. A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints[J]. European Journal of Operational Research，2013，225（2）：199-210.

[18]Subramanian A，Penna P H V，Uchoa E，et al. A hybrid algorithm for the heterogeneous fleet vehicle routing problem[J]. European Journal of Operational Research，2012，221（2）：285-295. 李佳欣，杨庆媛. 长江经济带2005—2015年土地利用效益及耦合协调发展[J]. 江苏农业科学，2019，47（3）：319-326.