基于节约里程法的车辆配送路径优化研究

王智灵 周蔷 王情香

摘 要：为提高快递公司的配送效率，缩短配送的路程，降低物流配送成本，文章通过对A快递公司向其下级网点配送快递的实例研究，运用节约里程法优化设计车辆配送路径。结果表明：优化后的配送路径更短、消耗的配送时间更少、车辆平均装载率更高，能够为车辆配送路径规划提供思路和参考。

关键词：节约里程法；车辆配送路径；优化；快递公司

中图分类号：F426；F252文献标志码：ADOI：10.13714/j.cnki.1002-3100.2023.12.004

Abstract： In order to improve the delivery efficiency of express delivery companies， shorten the delivery distance， and reduce logistics delivery costs， the paper uses the mileage saving method to optimize the design of vehicle delivery paths through a case study of A Express Delivery Company delivering express to its subordinate branches. The results indicate that the optimized delivery path is shorter， consumes less delivery time， and has a higher average vehicle loading rate， which can provide ideas and references for vehicle delivery path planning.

Key words： mileage saving method; vehicle distribution route; optimization; express company

0    引    言

物流作为现代商业活动的生命线，随着我国经济和科学技术的发展，已成为国民经济的支柱产业，为解决不断增长的快递量所提出的优化车辆配送路径问题已成为现阶段企业降低配送成本的一个重要途径。因此，在优化车辆配送路径的问题上，众多学者已展开了大量研究。1964年，Clarke和Wright首次提出节约里程法，并将其用于解决运输车辆在向多个目的地配送货物的过程中经过多条运输路线的最优路径问题。2011年，张颖敏基于节约里程法对物流配送线路进行优化，并运用一组测试数据验证了节约里程法的可行性，最后提出了将节约里程法和聚类分析法相结合可以较好解决大型复杂配送网络中模型的改进方法[1]。2018年，有学者等研究了需求和旅行时间不确定条件下具有硬时间窗的车辆路径问题，并设计了一种基于改进的自适应可变邻域搜索启发式两阶段算法。2020年，孙艺婕基于对多中心配送路径问题和时间窗问题的详细描述确定以配送总成本最小化为优化目标，分析优化目标的成本构成并引入必要的条件约束，最终建立带时间窗的多中心配送路径优化模型[2]。2016年，汤齐等针对生鲜产品配送对车辆路径优化选择进行研究，综合考虑运输成本、制冷成本及惩罚成本，结合时间约束建立模型，运用节约里程法优化生鲜产品配送路径[3]。通常快递公司在收到快递后会先把分属不同区域的快递分拣好，然后配送给相应的下级快递配送网点。A快递公司从上一级快递配送节点收到属地为A公司的快递后，把要发往不同下级快递配送网点的快递分拣出来，最后将分拣好的快递配送到下级配送网点。然而A公司在向其下级配送网点配送快递的过程中存在着没有统筹安排配送路径、没有统一调度配送车辆和配送总成本高等问题，导致该公司在配送质量和配送效率方面没有竞争优势，不利于企业的长期发展。因此，本文运用节约里程法来优化该公司向其下级网点配送快递的车辆路径，从而提高配送效率，降低物流配送成本，为该公司车辆配送路径规划提供思路和参考。

1    节约里程法概述

1.1    节约里程法的核心思想

节约里程法又称节约算法，在1964年由Clarke和Wright提出，是解决运输车辆数目不确定条件下VRP问题的最有名的启发式算法，可以同时确定配送过程中所需的最少车辆数和车辆行驶的路径[3]。节约里程法的核心思想是在满足约束条件的前提下依次将运输问题中的两个回路合并为一个回路，使每次合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时再进行下一辆车的配送路径优化，以此类推，直到把所有客户的货物配送完毕。

1.2    节约里程法的基本原理

集散中心P为A、B两家网点提供配送服务，P到网点A的最短距离为S1、P到网点B的最短距离为S2，网点A、B之间的最短距离为S3，网点A、B的快递配送量分别为Q1、Q2，（Q1+Q2）之和不能超过配送车辆的最大载重量Q。

若集散中心P用两辆车分别为A、B网点配送货物，当货物配送到网点后，配送车辆再原路返回集散中心P，如图1所示，则配送车辆的总行驶距离为：

如果将上述配送方案改为在网点A、B两家的快递配送量之和不超过配送车辆的最大载重量的前提下，用一辆配送车为网点A、B配送货物；只有把货物配送完毕后，配送车才能返回集散中心P，如图2所示，则配送车辆的总行驶距离为：

对比第一种配送方案，采用第二种配送方案节约的行驶里程为：

根据几何学中的三角形定理：两边之和大于第三边，可得出：S1+S2-S3＞0。

所以，如果集散中心P采用第二種配送方案，既可以少使用一辆配送车，又可以缩短配送车辆的行驶总里程，这样不仅减少了配送时间，还降低了配送成本。集散中心在为多个网点配送货物时，可以在不超过一辆配送车最大装载限制的基础上安排一辆配送车为节约里程量最多的网点群依次送货。当所需配送的货物量超过一辆配送车的最大装载限制时就安排下一辆配送车配送货物，若遇到快递无法整装的情况，就以节约量安排配送路径；然后用相同的办法来安排其余网点的配送路径，直到把全部网点的快递配送完毕。

1.3    节约里程法的主要步骤

1.3.1    收集A快递公司各网点的地理位置信息

收集A快递公司各网点的地理位置信息，利用互联网、高德地图工具测量A快递公司至各网点和各网点之间的最短距离，制作出最短距离表。

1.3.2    编制节约里程表

根据最短距离表，使用节约里程量的计算公式3计算各网点之间的节约里程量。例如，由同一辆配送车从A快递公司出发完成网点i和网点j的快递配送任务，使用节约里程法得到的结果与初始配送方案相比就可以得到节约的里程数Z（i，j）。

1.3.3    编制节约里程排序表

按照节约里程数的大小排列节约里程表中的节约里程数，若节约里程数相同则并列排序，最终得出节约里程排序表。

1.3.4    制定配送路线

按照节约里程排序表中数据从大到小的顺序及有关约束条件计算几个网点之间能否用一辆配送车进行快递的配送，若能，就连接A快递公司的集散中心P与网点形成配送路线回路。若在一个依次由集散中心P到网点i再到网点j最后返回P的配送路线组成的回路中，可以由一辆配送车同时完成i点、j点的快递配送任务，且不超过该配送车的最大装载限制，则这个配送路线回路的合并是可行的。再合并其他网点的配送路线以不断形成新的配送路线回路，直到没有可以合并的符合约束条件的新回路，即得到最优解。

2    当前配送概况

2.1    配送范围

A快递公司只为广汉市城区内距离超过一公里远的韵达快递网点及与韵达有合作的菜鸟驿站配送快递，共有14个配送网点，地理位置如图3所示，其中P代表A快递公司，P1至P14代表客户网点。

2.2    现有配送路径

A快递公司现有最大载重量为500千克、800千克的快递配送车各2辆，在快递体积小、重量轻且体积分布均匀的情况下，最大载重量为500千克的配送车一次最多可装载600件快递，最大载重量为800千克的配送车一次最多可装载1 000件快递。为了减少配送时间和配送成本，公司规定每辆车的单次配送最大行驶距离不得超过15公里。

目前，A快递公司的配送路径不固定，配送员都是根据自己的经验选择配送路线。通过实际调查该快递公司的配送员，得到这14个网点配送最常行驶的配送路径分别如下。

配送路径一：P→P1→P2→P3→P4→P；

配送路径二：P→P5→P6→P7→P；

配送路径三：P→P8→P14→P13→P12→P；

配送路径四：P→P9→P10→P11→P。

2.3    配送路径现存问题

A快递公司在向其下级配送网点配送快递的过程中，管理人员按照配送范围内的快递网点所处位置为配送员划分其所需负责配送的快递网点区域，然后配送员根据自己所需配送的快递网点位置随机选择配送路径，无法统筹安排配送路径。配送员根据自己的经验来选择配送路线和配送车辆，在配送过程中容易出现车辆装载率低、车辆配置多、车辆行驶总里程偏高的现象，從而导致车辆成本和配送员工资成本偏高，最终使配送总成本偏高，导致该公司的客户满意度、物流配送效率与其竞争对手相比偏低，不利于企业的长期发展。

3    基于节约里程法车辆配送路径优化

选取配送范围内的14个网点，这些网点位于居民小区内或小区周边，客户群体较稳定，除了大型的网络购物活动，如淘宝双11、618等时间段外，每日代收的快递量波动不大，而且大部分快递体积小、重量轻，14家网点的地址和各个需求点的快递量如表1所示。各网点间距离及A快递公司与网点间的距离以高德地图导航的方式获取，如表2所示。

根据各网点之间及A快递公司与网点之间的距离，利用公式3计算各网点间的节约里程，按照节约里程大小，从大到小进行排列，若节约里程数相同则并列排序，最终得出节约里程排序表，如表3所示。

从节约里程最多的路段P12—P13开始规划路线，首先考虑将网点P12和P13的快递使用一辆车进行配送，这两点的快递数量之和为140+100=240件，两点间距离为1.6公里，均没有超过约束条件的限制，此路线可行，可以继续合并下一个客户需求点。连接节约里程处在第二位的P12—P14，但是从这三个客户需求点与A快递公司的地理位置来看，P12不适合与P14连接，因此放弃合并网点P12、P14。接下来，两点间节约里程最大的是P13—P14，把网点P14加入P12—P13这条配送路线中，三点的快递数量之和为240+150=390，行驶里程为1.6+1.6=3.2公里，均未超过约束条件的限制，此路线①：P12→P13→P14可行，进行下一步合并。

确定了配送路线①后，接下来，节约里程最大的是P9—P10，这两点的快递数量之和为135+200=335件，两点间车辆行驶里程为0.1公里，均未超过约束条件的限制，这两点的快递可由一辆车进行配送。然后是P9—P11，因为P9、P10、P11三个网点的快递数量之和为335+180=515件，路线②：P10→P9→P11的车辆行驶里程为0.1+0.8=0.9公里，均未超过约束条件的限制，因此此路线可行。

接下来，节约里程最大的是P11—P12，将网点P11合并到路线①中，这四个网点的快递数量之和为390+180=570件，行驶里程为3.2+4.2=7.4公里，均未超过约束条件的限制，此路线③：P11→P12→P13→P14可行。此时将路线②和路线③合并，合并后的快递数量之和为515+570-180=905件，行驶里程为0.9+7.4=8.3公里，均未超过约束条件的限制，此路线可行，形成配送路线④：P9→P10→P11→P12→P13→P14。

接下来是路段P2-P3，两点快递数量之和为190+200=390件，行驶里程为0.7公里，路线可行。然后是路段P3—P4，因为P2、P3、P4的快递数量之和为390+130=520件，行驶里程为0.7+0.5=1.2公里，此线路可行，所以可形成配送路线⑤：P2→P3→P4。不断重复上面的过程，最后得到优化后的配送路径方案，如表4所示。

优化后的配送路径方案中，A快递公司完成所有客户需求点的快递配送任务共需要使用2辆最大装载量为1000件快递的配送车，车辆行驶总里程为24.3公里。

4    结果分析

优化前，完成这14个网点的所有配送任务共需要使用4辆配送车。其中，路径一和路径四使用最大装载量为1 000件快递的配送车，路径二和路径三使用最大装载量为600件快递的配送车，车辆行驶总里程为32.3公里，如表5所示。

运用节约里程法对配送路径进行优化后，车辆总里程节约了8公里、平均装载率提高了36.46%，如表6所示。

使用节约里程法对A快递公司的车辆配送路径进行优化后，只需要2辆配送车就能完成这14个网点的所有配送任务，减少了车辆在配送快递过程中的行驶总里程，还能降低车辆成本和配送人员的工资成本。同时车辆平均装载率提高，可以充分利用配送車辆，合理配置资源以减少浪费，提高企业的配送质量并缩短配送总时间，从而增加企业的核心竞争力。

5    结    论

车辆配送路径优化是降低企业物流配送成本的关键环节之一，本文采用节约里程法对A快递公司的车辆配送路径进行优化，减少了车辆配送总里程、提高了车辆平均装载率、降低了配送总成本。优化后的结果表明，运用节约里程法对A快递公司配送路径进行优化是可行的，为该公司车辆配送路径规划提供了思路和参考。

参考文献：

[1] 张颖敏．基于节约里程法的物流配送线路优化与改进研究[J]．物流科技，2011，34（4）：113-115.

[2] 孙艺婕．带时间窗的城市物流多中心配送路径优化研究[D]．舟山：浙江海洋大学，2020.

[3] 汤齐，张亚丽．基于时间约束的生鲜产品配送路径优化[J]．铁道运输与经济，2016，38（6）：40-43.