基于改进C-W算法的冷鲜肉配送路径的解决方案

戚正清，许仁礼，靖培星

(安徽科技学院 管理学院，安徽 蚌埠 233000)

0 引言

冷鲜肉是将生猪屠宰后迅速冷却，并在随后的流通加工及销售过程中一直保持在0—4℃的鲜肉.过去，消费者以购买常温鲜肉为主.近年来，随着人们对生活品质要求的日益提升和冷链技术的迅猛发展，冷鲜肉因其新鲜、安全等优点，受到消费者的青睐.据统计，目前在大中型城市中，冷鲜肉已经占到生肉市场的60%以上，市场潜力仍然很大.但冷鲜肉保鲜期较短，对所处环境要求也较高，因此在其冷链配送的时效上提出了更高的要求.合理规划冷链配送路径，对企业来说，可以减少配送在途时间，降低其配送成本.对于客户来说，既可以满足客户对于配送时效的要求，又可以保障冷鲜肉的质量安全.

在物流领域，车辆路径优化是指已知需求点的地理坐标、需求量，配送中心以其有限的资源(车辆、时间等)，以短距离、低成本和高服务质量等指标为目标，高效合理地安排车辆完成所有配送任务的问题[1]，其已广泛运用于冷链物流配送的研究.目前国内关于冷链物流配送路径优化及算法的研究已有一些理论成果.武佳佳等[2]针对医药物流路径优化问题，建立了增加软时间窗约束的车辆调度模型.宋志兰等[3]从有时间窗约束角度构建了满足客户时间窗约束的逆向物流配送成本模型，并运用节约里程法得出最优解.范立南等[4]将配送过程中产生的碳排放成本计入总成本，并采用改进遗传算法进行求解.林峰等[5]将库存决策与路径决策问题进行结合，通过构建数学模型以最小化供应链总成本，并采用改进的C-W算法对问题进行了求解.陈梦等[6]根据生鲜农产品的配送特性，在传统路径优化模型的基础上在总成本函数中增加了货损成本和制冷成本.

但以上文献大多局限于理论模型，未能在企业中得到应用，且在冷鲜肉领域的研究尚少.本文提出一种在时间窗约束下改进的C-W 算法，该算法在对冷鲜肉配送具体情况进行分析的基础上，构建相应的配送成本函数，并通过实际企业案例分析来规划合理的物流配送路径，可以在一定程度上拓展冷鲜肉配送问题的实践性研究.

1 问题描述和假设

1.1 问题描述

本文研究的冷鲜肉配送系统由单一配送中心和多个需求点组成.配送中心利用冷藏车将冷鲜肉配送到各个需求点，每个需求点对冷鲜肉的需求量已知且相对固定，各需求点对货物的到达时间有一定要求.在满足各个需求点要求(货物质量良好、送达时间合理等)和不超过配送中心资源限制(冷藏车数量等)的前提下，综合考虑各项成本，合理安排车辆完成所有配送任务[7]，最大限度地降低综合物流成本.基于冷鲜肉配送的特性，在配送成本优化模型中进行了如下假设.

1.2 基本假设

(1)冷藏车的最大荷载是固定的；

(2)各需求点的地理坐标和冷鲜肉的需求量已知；

(3)冷鲜肉的配送只是一个单向过程，冷藏车单程有载；

(4)冷藏车必须从配送中心出发，完成配送任务后最终回到配送中心；

(5)需满足所有需求点的要货需求，每个需求点的冷鲜肉只能由一辆冷藏车运送；

(6)冷鲜肉必须在指定的时间内交货，若在客户要求的时间外送达，将施加一定的时间窗成本.

(7)冷鲜肉需要保持在一定的温度内以保证品质和价值.

1.3 符号假设

c0表示单位运输成本；xij表示0—1变量，若冷藏车完成客户i到客户j的配送，则xij=1，否则xij=0；冷藏车由客户i驶向客户j的载重量为Lij；客户i、j之间的距离为Dij；冷鲜肉单价为P；客户j的需求量为Qj；冷藏车从配送中心到客户j的行驶时间为T0j；冷藏车从客户i到达客户j的时间为Tij；冷藏车在客户j的装卸货时间为Tj；j客户要求的最早配送时间为Ej；j客户要求的最晚配送时间为Lj；运输过程中的冷鲜肉货损系数为θ1；装卸过程中的冷鲜肉货损系数为θ2；运输过程中的冷鲜肉制冷成本系数为θ3；装卸过程中的冷鲜肉制冷成本系数为θ4；车内温度为T；车内外温度差为ΔT；单位碳成本为p0；碳排放系数为r；单位距离碳的排放量为Eij.

2 优化模型构建

模型构建以综合配送成本最低作为目标，分析各项成本，构造总成本函数，并计算运输成本、时间窗成本、制冷成本、货损成本和碳排放成本[8].

(1)运输成本

冷藏车的运输成本与车辆行驶距离、行驶时间成正比关系[9].计算公式如下：

(2)时间窗成本

在实际生活中，需求点通常会要求配送中心在规定时间内送达货物，但由于配送中心的车辆调度失误或配送路线不合理，无法在客户限定的时间内送达货物，此时需求点会根据超出限定时间的长短对配送中心施加一定的时间窗成本，计算公式如下：

(3)货损成本

货损成本主要产生于两个阶段：一是运输过程，假定在运输过程中不考虑其他的影响因素，随着运输时间积累冷鲜肉腐烂而产生的货物损失；二是装卸阶段，外界热空气进入车厢，加速冷鲜肉的损耗.计算公式为：

(4)制冷成本

冷鲜肉在配送过程中需保持在0—4℃，制冷成本可分为如下两部分：其一，随着冷藏车配送里程数、配送时间和车内外温度的变化，制冷成本增加；其二，装卸货物时，车外热空气进入车厢，导致温度迅速上升，为保证车厢内的恒温条件而增加的制冷成本.计算公式为：

(5)碳排放成本

冷鲜肉配送过程中产生的碳排放主要来源于车辆油耗[10]，计算公式如下：

因此总配送成本，即配送优化模型的目标函数和约束如下：

3 算例分析

3.1 算例背景

以合肥市肥东县安徽汇汇食品有限公司(简称H公司)为例，通过走访调研，得知各需求点到该公司的距离和服务时间窗分布，并通过对2018年全年冷鲜肉需求量的分析得出各需求点的日平均需求量，冷鲜肉需求点分布情况如表1所示.

为研究方便起见，将公司所在位置标注为点O，并将表1所示的需求点依次标注为点A、B、C、D、E、F、G、H、I、J.则公司配送需求点分布情况和公司各需求点需求量情况如图1所示.

图1 需求点及需求量分布情况

表1 冷鲜肉需求点分布情况

已知该企业车辆的平均行驶速度为60 km/h，产品单价为20000元/吨，单位距离运费为2.5元/吨公里，θ1=0.2%，θ2=0.4%，θ3=0.3%，θ4=0.6%，运输过程制冷耗能成本为12元/时，由温差引起的制冷成本为2.5元/℃·h.单位碳成本=0.13kg/L，碳排放系数=2.7kg/L，各需求点的停留时间(min)为需求量(t)的10倍，考虑到客户的需求和装卸货物所耗费时间，冷藏车单次配送的最长距离为40 km.

3.2 优化过程

在保证基本假设和时间窗要求的前提下，找出各种可行配送方案，计算不同配送路线中配送节点的各项成本节约值，得到总成本最小的配送路线.改进的C-W算法步骤为：①将各需求点按收货时间先后顺序依次排列；②以H公司为起点，安排有最先时间窗要求的需求点为第一配送点，计算各项成本节约值，按照节约总成本最大的原则找到下一配送点；③删除已选定的需求点，在剩下的需求点中重复步骤②，直至加入下一配送点后超出车辆荷载和时间窗限制；④重复上述步骤，直到满足所有需求点的要货需求.

因此根据算法步骤，具体优化过程如下：

(1)将各需求点按收货时间先后顺序依次排列，如表2所示.

表2 需求点收货时间的先后顺序表

(2)计算配送点i、j(i、j=A、B、C、D、E、F、G、H、I、J)之间的距离节约值，如表3所示.

表3 各配送点之间的距离节约值(km)

(3)从公司出发，有最早时间窗要求的A为第一配送点.在A列中找到非0配送点，计算各项成本节约值，如表4所示.

表4 A列非0配送点各项成本节约值(元)

由计算结果可知需求点B总成本节约效果最显著，且满足总荷载低于4t和时间窗要求的限制，故确定B为第二配送点.

(4)在表3的B列中找到非0配送点并计算各项节约成本，计算结果如表5所示.

表5 B列非0配送点各项成本节约值(元)

因此，将需求点C添加到配送路线中，作为第三配送点.下一个配送点选择依据如表6所示.

由表6可确定D为第一条线路的第四个配送点，由于A、B、C、D的总需求量为0.7+1.5+0.8+0.4=3.4t，距离G、I、J点较远，如继续配送会导致配送路径长度超过冷藏车单次配送的最长距离40 km，因此无法增加任何配送点.故第一条配送路线为北京华联生活超市(望湖城店)—满天星睦邻超市(亳州路店)—肥东县城关中学—凤阳路集贸市场.配送路程为32 km，车辆装载量为3.4t.

表6 C列非0配送点各项成本节约值(元)

同理，用MATLAB工具软件编程实现剩余配送路径规划，由运行结果可知：第二条配送路线为庐阳区白水坝菜市场—华联超市—肥东第二中学.配送路程为24 km，车辆装载量为3.5t.第三条配送路线为合肥市第十中学—百大购物中心—贸林路农贸市场.配送路程为28 km，车辆装载量为1.9t.

(5)从而计算出H公司冷鲜肉配送优化前后的各项成本，如表7所示.

表7 路径优化前后各项成本(元)

通过上述过程数据分析，可知优化后配送路径成本与现行配送路径成本相比，各项成本均有所下降，尤其是时间窗成本为0.由路径优化前后的各项成本数据可以得出，H公司冷鲜肉完成单次配送原总成本约为1353元，优化后的配送总成本约为1036元，降低了约23.43%，大大减少了物流配送成本.路径优化前后各项成本对比如图2所示.

图2 路径优化前后各项成本对比(单位：元)

4 结论

在实际的冷鲜肉配送过程中，为降低成本，配送中心往往按照最短路径规则安排车辆进行配送，未体现各需求点时间窗的差异性，常导致冷鲜肉送达时间超出需求点的满意时间窗，时间窗成本居高不下，且影响客户服务体验，大大降低了顾客满意度，存在客户流失的风险.

笔者建议采用考虑需求点服务时间窗的改进C-W算法规划配送路径，并把时间成本考虑在配送成本核算目录内.基于时间窗约束，可以大大降低时间窗成本，其余各项成本也有相应程度的降低.该改进算法可行有效，其可以提升冷链物流总体效益.