基于节约里程法的连锁便利店配送路径优化

2022-10-08朱成娟刘恋王忠昶

大连交通大学学报 2022年4期

朱成娟，刘恋，王忠昶

(1.大连交通大学交通运输工程学院，辽宁大连 116028; 2.北京京港地铁有限公司，北京 100068)

现如今许多连锁超市企业为追求多元化的经营模式，在拥有大卖场经营模式的同时发展社区便利店，以创造更多的利润增长点[1-2].连锁超市的仓储中心既要满足大卖场配送需要，同时也需要满足小型便利店的配送需求.如何提高配送水平来服务不同规模的门店成为对配送中心的一种考验[3-4].因此，寻求一种更高效优质的优化算法对于便利店物流配送路径的选择具有很强的现实意义.

配送路径问题属于车辆路径问题(the Vehicle Routing Problem, VRP).在求解车辆路径问题时由于问题的复杂性，学者们常使用智能优化算法[5-6].在众多优化算法中，节约里程算法对于小规模配送问题具有较强的实用性和易操作性，且可同时实现多种车辆类型的配置[7].宋赛凤等[8]利用节约里程法得出配送路线优化方案，并通过一次实际配送验证了其可行性.王志峰[9]研究了连锁超市物流配送模式，提出了优化配送体系的两个策略，并强调对于运输车辆进行优化调度可以使物流配送经济效益和科学性同时得到提高.蔺士文等[10]对物流配送低碳路径优化问题进行了研究，利用节约里程法得到优化方案可降低碳排放成本约 86元，实现了节能减排.目前，对于上述问题的研究很少考虑多类型车辆的配送问题.本文采用智能算法中的节约里程法为某便利店配送中心的实际案例规划了一套优质的使用不同类型车辆的配送方案.对比原有的按照司机经验所走的路径，运用节约里程法安排更合理的配送路径能够在配送过程中减少总里程，以更环保的方式达到提高配送效率的目的.

1 节约里程法原理及步骤

1.1 节约里程法的基本原理

假设有两个目的地A和B以及一个配送中心O，配送中心对两个目的地分别派车进行送货而且空车回程，此时若从配送中心O派一辆车先到达A 再到达B最后回到O，把这两个位置进行联合配送，根据三角形基本性质任意两边之和大于第三边，可知联合配送的方案优于单独配送的方案.

C=2CAO+2CBO

(1)

C′=COA+CAB+COB

(2)

ΔC=C′=CAO+CBO-CAB

(3)

式(1)为总共运输里程，式(2)为运输里程，式(3)为节约里程量.节约里程法原理图如图1所示.

图1 节约里程法的基本原理

1.2 节约里程法步骤

节约里程法基本步骤如下：

步骤1：确定各门店之间路程和配送中心到门店的路程；

步骤2：计算各门店之间节约里程量ΔC，并降序排列节约里程量；

步骤3：将节约里程量最大的路径标记为i，取含有该路径门店的其他路径中节约里程量最大的路径；

步骤4：判断这些门店的需求量之和是否满足车辆的最大载重要求，若满足则可加入到路径i中，若不满足则按照节约里程顺序取下一个路径返回步骤4，直至路径i的车辆载重量达到不能容纳任何一家门店的需求量时生成完整的路线i；

步骤5：删除节约里程顺序表中路线i包含的门店，i=i+1，转步骤3；

步骤6：确保每一个门店都在路径中，得到最终路径方案.

2 算法优化实例

本文以某连锁便利店在太原市内的10家门店为例，表1为10家门店的地址和各个门店的货物需求量.已知该企业为了较高的堆叠货物、增加车辆满载率，采用笼车进行拣选和配送，笼车不仅能够较高的堆叠货物，也具有保护零散商品的作用.在配送过程中使用能够承载15辆笼车的厢式货车和能够承载18辆笼车的保温货车.图2为配送中心与门店间的路程以及各门店之间的路程，这些路程是根据百度地图上的路程标注的.通过这些已知的信息从减少车辆运输成本的角度利用节约里程法规划优化配送路线.

表1 门店地址及货物需求

图2 门店间的路程(km)

2.1 现有配送路线

根据实际调查，现有配送方案要求车辆尽可能满载，门店配送路线往往是根据货物装载情况和司机的经验而定，忽视了路径规划在整个配送路径中的作用.在车辆尽可能满载的情况下，这10家门店的货物需要由四辆厢式货车和一辆保温货车配送，路线分别为：O-F-H-O、O-C-B-O、O-G-I-O、O-E-J-O、O-D-A-O，总里程为496.2 km.

2.2 配送路线优化

把配送中心作为起点，选取两个门店构成三角形，配送中心到两个门店的路程之和减去两个门店之间的路程ΔC=CAO+CBO-CAB，即为节约里程量.例如，配送中心到A店和B店的节约里程量为 46+35.2-15= 66.2 km，以此类推，计算所有门店与门店、门店与配送中心间的节约里程量ΔC.对节约里程量ΔC做降序排列得到节约里程量顺序表(表2)，从表中可知门店A到门店G的节约里程量最大，门店E到门店H的节约里程量最小.

表2 节约里程量顺序表

从节约里程量ΔC最大的路段A-G开始安排路线，合并门店A、G的需求量总共是6笼车，处在配送车辆的最大载重范围内，两家门店合并到同一个配送路线上，设为路线①.连接节约里程量处在第二位的门店D、F，此时路线①总的货物需求量是24笼车，不符合车辆的最大载重量，所以D-F这段路径不能够合并在路线①中.节约里程量排在第三位的两家门店中的门店G在路线①上，另一家门店F的货物需求量是11笼车，合并到路线①中总的货物需求量是17笼车，此时配送路线①总的节约里程量为92.9+84.3=117.2 km,可以使用载重量为18笼车的货车.

确定了配送路线①，把节约里程顺序表中涉及到A、G、F这三家门店的路段进行标记，再安排其他七家门店的配送路径.从节约里程量在第七位的D、E两家门店所在的路段开始合并路径，由于车辆载重量限制D、E两家门店无法安排在同一路径.接着把节约里程量在第十九位的B、C两家门店合并在一条配送路径上，这两家门店总的配送量为15笼车，把这条路段作为配送路线②，其节约里程量为64.2 km，使用载重量为15笼车的货车.

确定了①②两条路线后，在节约里程顺序表中把涉及到门店B、C的路段进行标记，再安排其他五家门店的配送路径.把节约里程量在第二十九位的D、I两家门店所在的路段开始合并，由于车辆载重量限制，D、I两家门店无法安排在同一路线.接着把节约里程量在第三十六位的H、J两家门店合并在一条配送路径上，这两家门店总的配送量为13笼车，这两家门店作为配送路线③节约里程量为58.5 km，使用载重量为15笼车的货车进行配送.

确定了①②③三条路线后，在节约里程顺序表中把涉及到J、H这两家门店的配送量作标记，再安排其他三家门店的配送路径.所剩下的D、E、I三家门店的需求量分别为13、9、8笼车.将E、I两家门店合并为配送路径④，D单独作为配送路径⑤.配送路径④的节约里程量为51 km，使用载重量为15笼车的货车进行配送.配送路径⑤的节约里程量为0，使用载重量为15笼车的货车进行配送.到此所有门店均在配送路径中.

最终得到优化配送方案如表3所示，优化配送方案路线如图3所示.在实例研究中现有路线设计方案要求货车尽可能满载，使用1辆保温货车和4辆厢式货车，配送总里程为496.2 km；经过优化后的路线虽然所使用同类型的车辆数与现有配送路线相同，但配送总里程为458.8 km.通过对比可以看出节约里程法进行配送路线优化相较于现有配送模式节约了配送成本，得到了比现有方案更短、耗时更少、运输成本更低、更加绿色的路径选择，有效地提升了其配送运输效率，控制运输成本，对连锁便利店配送中心的货物配送提供了决策参考，对其实际运营管理具有较大的现实意义.