基于最小生成树的城市物流配送路线算法优化研究

洪继程

摘 要：提出了一种基于最小生成树理论算法的物流配送路径优化方案，首先实现了物流配送复杂路径向最小生成树的转化方案，通过转移策略的建立，构造了最小生成树的算法，同时通过标记的方法实现了最优化路径设计，最后实现了物流配送的周转总量最小的目标。软件调试运行表明，研究中提出的算法切实有效，相对于传统的算法其复杂程度得到了有效降低。

关键词：最小生成树；物流配送；路径；优化；算法

中图分类号：TP301 文献标志码：A 文章编号：2095-2945（2017）31-0012-02

引言

现代物流管理已经成为一种先进的组织方式与管理技术，是物流企业降低物流消耗，提高劳动生产率的有销手段[1]。研究物流系统中路径的优化算法即采用计算机网络技术对物流中的货物、服务等要素进行高效流通与科学有序的控制。物流学的研究内容包含物流點的选址问题、物流车辆的调度路径以及物流库存控制问题。本研究主要侧重进行车辆的物流路径优化问题，研究要素主要包含配送中心、客户位置以及道路网络的情况等。物流路径的优化问题目前有精确算法、启发式算法以及元启发式算法[2]。精确算法主要有动态规划法与分支定界法等两个方面的内容，但是精确算法只能适用于小规模的车辆路线优化问题。元启发式算法求解路径优化问题是目前研究的热点，对应的算法有蚁群算法、遗传算法等。

遗传算法对于研究领域所需要的知识程度要求较低，对于空间等因素的要求不高，在模型求解方面具有较强的适应能力与通用性。蚁群算法采用的是正反馈机制，具有优良的分布式特征，遗传算法与蚁群算法在求解大规模路径优化问题时具有一定的优越性，但是也同时存在收敛性差等方面的问题[3]。利用最小生成树进行求解具有直接、有效、适应强的优势，是目前路径优化的研究热点。

1 提出问题

1.1 问题描述

物流的特征是多个车辆将货物从不同的配送中心送至不同空间位置客户，因此合理进行路径的安排能够使得总体配送费用成本最低是交通运输与物流企业关注的现实问题。在研究中，车辆都是具有一定实际容量的，为了简化问题，假设所有客户的需求都由一个配送中心满足，同时完成一次配送后，车辆需要回到配送中心后再次进行下一次配送。

1.2 研究思路

本研究中采用了最短路径寻优转移策略，不断进行可行解策略的构造以及信息更新，根据优化最小生成树的基本原则，根据配送范围进行交通路线图的绘制以及抽象，形成一颗或者多颗最小生成树（研究中设定这些树为子树），在子树的基础上进行合成就可以形成一颗最小生成树，合成以后的最小生成树就是路径优化的研究对象，采取这样的方案较为实用，并有效降低了算法的复杂度[4]。

2 路径优化策略与算法

2.1 优化策略

假设v0为物流系统的一个配送中心，需要向客户送货，客户定义为vi与vj，其中就涉及到三个距离，首先是物流配送中心到两个用户的距离，其次就是两个用户之间的距离，配送的方案有以下两种，如图1所示。

根据之前配送要求返回中心的假设，转移策略中第一种方案所需要的配送距离为2|voi|+2|voj|，第二种的配送距离为

|voi|+|voj|+|vij|，第二种方案与第一种方案距离的差值根据三角形的三边关系|voi|+|voj|-|vij|>0。根据这样的策略可以得出，如果物理配送中心向多个不同用户配送货物，车辆配送路线上客户密度越高，则路径更为优化合理。

2.2 算法

在交通网络中将其中的用户节点标注为vi（其中i=1，2.....9）。各个节点之间的链接如图2所示，节点之间的距离也不同，采用数字标记进行量度，任意确定其中的一个节点为配送中心，其算法构成过程包含有交通线链接抽象，最小子树构造，合成树构造以及路线确定等四个不同的阶段。

首先需要实现就是最小生成树的构造，确定配送中心为最小树的树根，在后续表达中简称为TRN，同时将配送中心节点定位为当前节点，并找出与当前节点具有连接关系的所有其他节点，并进行统计，寻找与当前节点最短的连接，并进行距离的存储，如果节点距离值变大则重新进行节点的选择，在此过程中可以采用三元向量组的方式对子树集合进行记录。对路径中的节点进行标记，并遍历所有的子树，删除路径中无法实现的孤立节点，完成对应子树的生成。

在完成子树的基础上根据子树的数目与节点的距离进行循环迭代运算，可以得到合并后的最小生成树，作为算法优化研究的对象。在距离计算过程中要能够实现有效距离的量度，科学规定节点之间实际的有效距离以及子树之间的距离。

3 算法优化与路径确定

3.1 算法优化

如果在实际过中配送中心向一个地点进行货物的配送，则只需要从树根的位置根据树的深度进行有限遍历算法进行配送目标的寻找，配送完成就按照原路返回，这样单点的模式下就可以保证是最佳的配送路线。根据OSDVRP的实际情况，可以在以上的算法基础上实现修正进行问题的求解。首先就是进行配送节点在最小生成树中的求解，其核心思路是对树根的子节点进行集合的定义，对子节点进行树根假定，并进行深度优先遍历，最终确定配送中心节点的分布。

同时需要进行相关路径必经节点的求解，对子集合中的所有节点都要能够通过深度优先的方式进行遍历查询，对最小生成树遍历获得的节点研究辨析，确定哪些节点处于同一路径，对于处在同一路径的节点进行标记并生成对应的子集，确定在路径中必经节点的分布[10]。

3.2 多点配送最佳路线的确定

要实现多点最佳配送路线的确定，首先需要进行的就是对子树合并以后树根岁对应的子集合进行实时判断，当对应的子集合为空集的时候，就删除这个集合，如果是非空集合，则多点配送算法有以下几个步骤。

S1：求解统计子集合的数量，并标记为n，如果n>1，则流程转到S4，如果n=1则转到步骤2，如果集合不存在，则转到S6。

S2：根据最小生成树的深度进行有限遍历到每一个配送点，并从原路返回到配送节点，遍历路径与返回路径即为所求解的最优化配送路径，同时进行集合的实时删除。

S3：对集合之间的互通链路进行检查，如果没有相互直接的连接，则转到S2。

S4：对其中每个集合进行直接互通线路集合的查询，将其中没有直接互通的节点构成的子集与节点本身进行删除。

S5：对所有子集合中进行交通连接图的有效还原，对其中算法生产的步骤进行迭代与重复，最后形成只有三角形以及直线方式的子树为止。

S6：确定子树之间的线路配送路径，同时对每个子树种的配送路径也进行确定，最终就可以得到多点配送过程中最优化的配送路径。

4 结束语

研究中采用了Jbuilder9对算法进行了仿真分析，结论表明，采用文中提出的算法能够以最快的速度实施货物的有效配送，同时也能够有效降低物流配送的成本，在过路费用、动力费用与人力成本方面都具有显著的改善，研究具有重要的理论意义与实践价值。

参考文献：

[1]张潜，高立群，胡祥培，等.物流配送路径多目标优化的聚类-改进遗传算法[J].控制与决策，2003（04）.

[2]崔雪丽，马良.有缺货限制的VRP蚂蚁算法研究[J].上海理工大学学报，2003（01）.

[3]张涛，王梦光.遗传算法和3-opt结合求解带有能力约束的VRP[J].东北大学学报，1999（03）.

[4]贺国光，胡学年，刘豹.用于公交线路优化设计的四步启发式算法[J].系统工程学报，1988（02）.

[5]韩艳，关宏志，赵红征.通勤班车出行线路优化研究[J].武汉理工大学学报（交通科学与工程版），2011（02）.endprint