配送车辆路径规划研究

孙畅 宋佩馨

【摘  要】随着经济的快速增长和人们消费水平的提高，消费者对快递服务的质量提出了更高的要求。快递企业在电子商务中面临着更大、更严峻的挑战。为了解决送快递慢、送快递难的问题，使快递行业更好的服务于大众，Dijkstra算法和最小生成树理论可以对快递行业的配送路径进行优化，从而提高快递效率、降低快递行业成本。通过采用Dijkstra算法和破圈法，系统地研究了ZT速递服务公司的车辆配送路径优化问题，得出了该公司快递配送路径总距离最短及服务成本最小的优化方案。

【关键词】路径规划;Dijkstra算法;破圈法;最短配送路线

Research on Vehicle Route of Delivery of Express——Exemplified on ZT Express Company

1前言

随着经济的发展和消费水平的提高，人们对快递服务的质量也提出了更高的要求。快递业务在将物品送到客户手中的同时，还要保证能够在时间上满足客户的需求，更好、更快成为客户对快递公司的要求。本文以ZT快递公司为研究对象，对其快递配送路径优化问题进行研究。

本文将从ZT公司快递基站现状、位置、配送路线进行分析，利用最短路模型针对速递配送中的问题提出解决方法，对其发展提出合理化建议。具体思路方法即先根据Dijkstra算法确定两个主要目标基站之间的最优线路，以此线路作为干路，再利用最小生成树原理，通过破圈法把其余各点有序地连接成各个支路，与干路相连，达到线路最优解以提高运输效率。

2相关理论

2.1 Dijkstra算法

戴克斯特拉算法（Dijkstra algorithm，又称双标号法）。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体;戴克斯特拉的原始版本找到两个顶点之间的最短路径，但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径，产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

Dijkstra算法的思路：Dijkstra算法采用的是一种贪心的策略，声明一个数组来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始时，原点s的路径权重被赋为0。若对于顶点 s 存在能直接到达的边（s，m），则把数组设为w（s，m），同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。最开始时，集合T只有顶点s。然后，在挑选出数值最小的点，那么这个点就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，这个时候就又多了一个已知点，随后，需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在数组中的值。然后，继续挑选数值最小的点，重复以上计算，直到T中包含了图的所有顶点，此时所有的顶点均已经有了自己的标号，从而推得最短路线。

2.2破圈法

破圈法是求最短生成树问题的一个相对简单的算法。这里讲的树，就是一个无圈的连通图，是图论里面的一个重要的概念，这里所说的最小生成树就是在一个赋权的连通图的无向图找出一个生成树，并使这个生成树的所有边的权数之和为最小。

破圈法即求最小生成树的一个比较简单的算法，破圈算法的具体步骤如下：

（1）在给定的赋权的连通图上任找一个圈

（2）在所找的圈中去掉一条权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条。

（3）如果所余下的圖已不含圈，则计算结束，所余下的图即为最小生成树，否则返回步骤（1）。

经过若干次地循环上述步骤得到一个最小生成树，就是所求方案。

3 ZT速递配送问题分析

3.1快递基站现状

下图是通过腾讯地图以及实际走访调查搜索到的基站地址。其中此公司有两处仓储物流中心，即集散地A和B，均在图中有标示。

公司目前拥有2辆载重2吨的货车，5辆载重1吨的货车，还有若干量快递电瓶车供快递员使用。在快递最繁忙的时间点，若大型车辆使用欠缺时，还会进行租赁车辆的使用。各基站与公司总部的货物交流多是单独运输，即各基站负责自己的货物的派送以及收取，对其他基站的货物不进行操作，这一过程必然会造成大量的人力和物力的浪费。快递人员对于路线优化能力和时间分配能力不足，导致在一定程度上影响了服务质量。

3.2 分析过程

3.2.1基本假设

根据实际情况，基于快递车辆路径优化问题的Dijkstra算法可以描述为：起点为集散地A或B。然后，根据公司的要求去其它各基站进行快递的分发以及收取。为合理安排车辆的快递路线，使快递车辆总距离最短，建立相关的物流模型，现作出假设：

（1）负责干路的车辆容积是无限大，可以一次性地将各个支路汇集上来的货物一次性地运抵次配送中心;

（2）各个基站的货物数量权重是一样的，无大小多少之分;

（3）不考虑道路的拥堵情况以及突发情况的发生。

（4）各点之间的路径为直线

（5）两个集散地A、B权重远远大于其它基站

3.2.2最短配送路线的求解

已知公司总部（集散地A）位置以及另一个次配送中心（集散地B）位置，即起点和终点位置，即可建立快递路径优化问题的数学模型。

Dijkstra算法的基本思想是，在快递车辆分布的最短路径问题描述的路径网络图中为每个节点分配一个标号（an，bn），路径网络图中的每个节点表示快递公司每个基站的位置或快递公司自己的配送中心的位置。从起点s到节点n的快递车辆最短配送路径长度将被记作an，从起点s到节点n的最短快递配送路径中n点的前一点会被记为bn，一个节点到其自身的最短路径长度设为0，若两节点之间不存在车辆行驶路径，则其距离设为inf（即无穷大）。

在MATLAB计算程序中，集散地A设置为起点s。各基站都编上相应号码，其中集散地A为2号，集散地B为20号。其次，根据图1建立距离矩阵。然后在程序中编制相应的参数。最后，代码运行后的解决方案结果如下所示：

Start id=2;

Finish id=20;

Distance=40.35

Path=[2 16 12 11 20];

Computing time=4;

即通过该算法在Matlab中的程序实现结果可得，起点为基站2即集散地A，终点为基站20即为集散地B，两个集散地间距离为40.35km。分别经过基站2、16、12、11、20。

如上结果所示，如果该快递车辆配送路径网络图中基站数越多，则相应的算法循环次数越多，所以计算时间会相应增加。Dijkstra算法的执行过程会产生以s为顶点的一棵树，同时伴随着算法的进一步执行该树会向四面八方延伸，直至最后到达终点为止，通過该算法可以准确的在快递车辆配送路径网络图中寻找出从起始点s到其他所有基站的最短路径。利用Dijkstra算法可以迅速的对现有的快递基站实施广范围的、最优化的配送路线的求解。

现在已知由集散地A到集散地B的行驶轨迹，已经确定了干路的路径2-16-12-11-20。下一步将各个基站之间随机连接起来，此时出现了若干个由基站组成的连通图，利用破圈法，逐步去掉权数最大的边，得到最小生成树，如下图

根据以上最小生成树，可以发现所有基站都是通过2-16-12-11-20这条干路链接起来的，以派送快递为例，外地送来以及要送到外地的包裹通过一辆经过基站2-16-12-11-20的大车依次分发和收集，所以派遣一辆大车专门负责集散地A和B之间的运输，期间有其它专门车辆负责支路的运输。这两个集散地拥有同等的地位，车辆在配送过程中同时也负责包裹收取的工作，也就是说一辆车从集散地A到集散地B的过程中不仅进行了快递的分发，同时也将各个基站收取上来的包裹运达集散地B。外发快件可以从集散地A和B出发，运至上级处理中心。

4结论

通过对ZT速递服务公司配送路径的现状分析研究，构建出配送路径优化的最佳模型，提出适合本企业现状的送路径优化方案，进而使中通快递公司配送系统得到了规范化提升。现有工作快递员有23名，采用快递配送路线优化之后可以减少10人，人员成本节约了78%，快递车辆数目也得到节约。

参考文献：

[1]李建军，沈啸林，陈明贺，刘硕，陈舒研.基于最小生成树算法的怀柔区快递站点选址问题研究[J].南方农机，2019，50（01）：91-93.

[2]黄杭.浅谈Dijkstra算法与Floyd算法[J].中国新通信，2019，21（03）：162-163.

[3]白玉凤.共同配送下区域速递配送中心选址和配送路径优化[D].北京邮电大学，2016.

[4]郑琰，孟晓露，伍佩琪，何雨飞.电子商务企业物流配送路径优化研究[J].物流工程与管理，2018，40（06）：111-113

[5]都雪静，孙菲菲，王云浩.小件快递配送路径优化研究[J].物流技术，2018，37（04）：29-35+40.

[6]丁浩，苌道方.基于Dijkstra算法的快递车辆配送路径优化[J].价值工程，2014，33（03）：15-18.

[7]刘艳红.物流企业商品配送路径规划与优化分析[J].山西农经，2019（01）：159-160.

[8]郭仪，梁微，苏相清，王晖.柳州融水电子商务物流配送路径优化[J].价值工程，2018，37（16）：91-94

[9]都雪静，孙菲菲，王云浩.小件快递配送路径优化研究[J].物流技术，2018，37（04）：29-35+40.

[10]孙苏文.基于C2B2F模式的生鲜电商车辆路径规划研究[D].江苏科技大学，2018.

[11]张欣.B2C电子商务下物流配送优化研究[D].江西财经大学，2017.

（作者单位：1保定理工学院（原中国地质大学长城学院）;2保定理工学院（原中国地质大学长城学院））