基于节约里程法的防疫物资配送路径优化研究

基于节约里程法的防疫物资配送路径优化研究

朱康林

中国地质大学（北京）信息工程学院 北京 100083

摘要：在防疫工作中，防疫物资的及时送达是影响防疫进程的重要一环。本文介绍了三种时间基本算法，并简单比较了其优缺点，最后以节约里程法为模型分析了某市某快递公司给周边8个社区配送防疫物资的问题，得出了最优路径。

关键词：物资配送，节约里程法，路径优化

在抗疫过程中，抗疫物资的及时分发是阻碍疫情发展的有效办法之一，但春节期间，物流公司人手不足，抗疫物资配送路径选择影响到物流公司人员的调度。

一、疫情期间物流公司行业现状

1、物流公司人手压力巨大。由于新冠疫情明确了可以人传人的情况，而且可以通过接触，飞沫等方式传播，同时无症状感染者也具有一定传染能力，因此按照相关部门要求，不能有大规模的配送人员上班工作，而抗疫物资又必须及时送到社区等防疫一线，因此人员调度压力巨大。

2、配送路径选择不合理。由于配送路径没有得到很好的规划，配送线路冗杂，重复的现象时有发生，这不仅浪费了人力资源，而且会导致配送时间的浪费以及物流公司的运输成本增加。配送效率的低下也就意味着有部分人得不到及时医学的防护，进而导致感染，影响整个抗疫形式的变化。

二、几种优化算法的简介及优缺点比较

目前对于路径优化的算法主要有遗传算法，蚁群算法，节约里程法等算法。每个算法都有各自的特点和使用条件，在合适的条件下使用锲合度高的算法更有利于得出最优解。

1、遗传算法。遗传算法（Genetic Algorithms,简称GA）。遗传算法主要是依据达尔文的“物竞天择，适者生存”的自然法则演变而来，将待优化的问题模拟为生物界代与代之间“染色体”的遗传问题，通过每一代种群染色体的遗传，变异，交叉操作，在自然的选择下，种群繁殖若干代以后，最终得到能适应环境的个体，从而得到我们需求的最优解。

2、蚁群算法。蚁群算法（Ant Colony Optimization,简称ACO）。该算法主要从蚂蚁寻找食物的规律之中演变而来，每一只蚂蚁行走过程中都会遗留下信息素，而之后的蚂蚁则会更倾向于向信息素浓度高的地方行走，由于蚁群数量庞大，通过不断的信息反馈，待若干蚂蚁行走后，将会得到两点之间信息素浓度最高的一条路径，及最短路径。因此蚁群算法常用于求解两个主体之间的优化问题。

3、节约里程法。该算法主要是用于求解运输车辆数目不确定的问题的最有名的经典启发式算法。它以两个目标为起始条件，在满足基本约束条件下，通过不断形成回路的方式来达到节约路径的目的，因此又称为节约算法或节约法。该算法在面向多个目标配送点时，可以通过不断的寻找，判断一条线路是否还能继续增加配送点，直至达到车辆的最大容量或行驶距离限制。一条配送路径确定以后，再开始下一个车辆的路径优化，直至配送路径包含完所有的待配送点，除此以外，该算法还可以用并行方式或串行方式来优化（表1）。

表1 三种算法的优缺点比较

三、节约里程算法基本原理介绍

节约里程法的核心思想是依次将运输问题中的两个回路合并为一个回路，达到节约里程的目的。同时要求每次合并后的总运输距离减小的幅度达到最大。假设O为物流配送中心，A和B分别为两个收货点，OA为配送中心与收货点A点的最短距离，OB为配送中心与收货点B点的最短距离，AB为收货点A与收货点B点的最短距离，现有两种配送方案如下图1和图2所示：

方案一、为配送车辆先配送A后返回配送中心再配送B，总路程为2（OA+OB）；方案二配送车辆配送A后直接配送B，之后再返回配送中心，总路程之和为（OA+OB+AB）；方案一与方案二总路程只差为（OA+OB-AB）。由于配送中心O与收货点A，收货点B形成一个三角形，由三角形几何性质可知，三角形两边之和一定大于第三边，因此恒有OA+OB-AB>0，即节约里程恒为正。由此可知方案二更加优于方案一，共节里程OA+OB-AB。这种分析问题的思想，就是节约里程法基本原理。因此两点之间节约里程用公式表示为LAB=OA+OB-AB。

四、基于实例的路径优化分析

假设某市某快递公司配送中心需要及时有效的向周围8个社区配送防疫物资，运输完物资后，配送车辆需要返回快递公司配送中心，将快递公司配送中心编号为0，其余8个社区依次编号为1-8号。配送中心配有运载能力分别为3t和5t的小货车若干辆，要求每辆车行驶距离不得超过30公里。节约里程法解题步骤如下：

第一步：根据配送中心与各社区之间地理位置计算出配送中心与8个社区之间可通行的最短距离以及各社区之间可相互通行的最短距离（km）（见表2）。

表2 配送中心与各社区之间可通行最短距离

第二步：根据各社区实际情况，列出各社区的防疫物资需求质量表（表3）。

表3 各社区的防疫物资需求表

第三步：根据各社区的实际可通行最短距离计算出任意两社区的节约里程，并按从高到低的顺序排列形成节约里程表（表4）

表4 节约里程排序表

第四步：依据节约里程排序表进行运输线路的组合连接，连接时每一条线路需要满足防疫物资需求总质量不得超过车辆最大载重量，同时每辆车行驶里程不得超过规定最远里程。首先确定第一条线路，从依据节约里程排序表可知6-7项排在了第一位，节约17公里。所以首先考虑，线路0-6-7-0总里程长2+4+9=25公里，需求物资为3.4+1.1=4.5t，符合载重为5t车辆的运输要求，由于车厢剩余容量仅剩0.6t，因此此条配送线路无法再加入其他社区。计算第二条线路时，需要将上述排序表中的与社区6和7相关项去掉以后，形成新的节约里程排序表，在新的排序表中，2-3项排在第一位，节约12公里。同理首先考虑线路0-2-3-0是否满足运输要求。该线路里程数为8+3+7=18公里符合要求，载货量0.8+1.4=2.2t选择载重量为3t的车也没问题。接下来与2-3项排列最为紧密的是3-4项，节约10公里，因此考虑把社区4加入此条配送线路，此时里程数为8+3+4+7=22公里符合要求，载货量0.8+1.4+2.7=4.9t也满足5t车辆运输要求。由于车厢容量仅剩0.1t，无法再将其他社区加入此条配送线路。第三条线路需在第二条线路基础上，将与社区2,3,4有关系的项去除后对剩余节约里程进行排序，此时第一项为5-8项，节约3公里。同理首先考虑线路0-5-8-0是否满足运输要求，里程数6+13+10=29公里符合要求，载货量1.8+0.5=2.3t选用载重量为3t的车也没问题。不过因车辆里程只剩余1公里，因此此条线路无法再加入其他社区。最后仅剩社区1还未进行配送，因此选择运载3t的车单独往返配送社区1所需防疫物资。其运载里程为5+5=10公里。至此配送线路优化结束（表5）.

表5 配送线路具体情况说明

五、总结

线路未优化之前，共需要从快递网点公司派出7辆3t的车和1辆5t的车来满足配送需求，行驶路程共为128公里，平均满载率仅为0.51，效率较低。在运用节约里程法优化以后仅需要2辆5t的车和2辆3t的车就能满足要求，行驶路程共为86公里，共节约了42公里，平均满载率提高了0.31达到了0.82。优化以后车辆使用数量只有之前的一半，总路程节约42公里，意味着配送成本的大幅度降低，同时车辆的平均满载率也达到了较高水平。实践表明，合理规划配送路径，可使快递公司良好有序运营，促进运送效率提高。

参考文献：

[1]朱锦程.基于节约里程法的校园生鲜配送路径优化[J].产业创新研究,2019(11):297-298.

[2]蔺士文等.基于节约里程法的物流配送低碳路径优化[J].物流工程与管理,2019,41(04):80-82.

[3]张永强等.基于遗传算法的末端配送路径优化研究[J].物流工程与管理,2019,41(11):110-112.

【作者简介】朱康林（1998.06-），男，汉族，四川眉山市人，中国地质大学（北京）本科在读，主要研究方向：电气工程及其自动化。

6