基于改进Teitz—Bart算法的移动网络物流配送系统

宋金萍+侯英姿+方雄

引言

物流配送的重点在于配和送两个方面，配即是主体客户，送即是货物运输。配送中心分配不合理，配送率低，配送路径选择不合理等等，都会导致物流成本大幅度增加。物流配送问题可以抽象为多旅行商问题，常用一些启发式算法来逼近或求最佳结果，常用的算法有遗传算法，粒子群算法，蚁群算法，禁忌搜索算法和模拟退火算法等。遗传算法计算量较大，问题越复杂，计算时间越长，稳定性也较差。粒子群算法的网络权重编码和遗传算子的选择时间比较麻烦，计算时间也较太长，而且要求所有的蚂蚁选择同一路线（即所求的最优线路），在实际计算中，在给定一定循环数的条件下很难达到这种情况。模拟退火算法的收敛速度慢，执行时间长，算法性能与初始值有关，而且参数敏感。上述算法有的计算时间过长，有的计算中极值早熟，影响优化配送路径的速度和最优路径的选择。TeitZ-Ban算法将需求点分配到其最邻近的供应点，并求总的加权距离，可有效优化配送路径合理选择，不会出现极值早熟现象，应用起来也较为简便，本系统将进一步改进Teitz-Bart算法的权重计算，设计开发一套路径规划更优的移动网络物流配送系统。

1改进的Teitz-Bart算法

Teitz-Bart算法主要的计算是将需求点分配到其最邻近的供应点，并求总的加权距离。这些距离正是用最短路径算法求得的。采用类似动态数据结构——供应点数据串和需求点数据串。数据串的长度常常可用实际应用中服务距离的最大值来限制，可以大大减少计算时间和内存。从供应点的数据串中，可以非常容易找到哪些需求点是在该点的服务范围，而从需求点数据串中可以找出其相邻的供应点。

Teitz-Bart算法虽然优点颇多，但是它的计算量颇大，计算时间长。但是Teitz-Bart算法中是预先求得数据随时随用，以此来提高算法的效率。结合它的这个特点在本系统中修改了其权值参数，用一个综合性的权值（w）来考量。

W=K1*Time+K2vLength+K3*Demand+TurnCost；

其中Time为时间，Length为距离，Demand为所需费用，TurnCost为转向花费，当转向花费值为负数的时候一般为禁止转弯。K1，K2，K3为时间、距离和所需费用所占的比例。

图1中边所具有的数值为边权。在寻求最优路径的时候，边权主要指代的是从起始点出发到终点的过程中所需要的花费，包括时间，费用，道路情况等。边权值和越大，说明它并不是要选取的路径。在地点确定了的情况下，边权值和越小，其路径最优。本图中的边权就是经过此公式计算而得的。路网的通达性与方向性对于路径的选择具有很重要的意义，有的路段只是单向路，因此在采用Teitz-Bart算法的时候要注意有向的路网及其通达性。不通达的地方的用∞来表示，进而进行算法的实行，获取其最短路径。图内点间可以用一个邻接矩阵w来表示。这里存在方向性的问题，所以这个邻接矩阵的考虑条件就变了。当为单向路的时，w[i，j]=w[i，j]（i≠j）且w[j，i]=∞；当i=j时，w[i，j]=0；当为双向路的时候，w[i，j]=w[i，i]（i≠j）。得到以下邻接矩阵：假设V2，V7是供应点，其他的为需求点，花费设为S，则可以通过上面的算法得到12条配送路线。这12种配送路线中只有第五种是最佳的路线其值为36。当需求点为一个的时候，按照算法也有且只有一个供应点对其供应，那么就是获取其最短路径即可。

2路网数据模型

路网数据模型由路网结点数据和弧段数据拓扑构网而成，利用属性表信息来表达网络的连通性，具体可以通过数据集一对一和一对多的ID关联值来表达逻辑模型和几何模型中弧段（Edge）数据集和结点（Node）数据集的拓扑关系。路网数据模型中由公交站点，设施点，交叉路口等点状物抽象为点成为结点，由道路等线状地物抽象为线段成为弧段。所有的数据及路网的方向都存储在SuperMap SDX+的网络数据集所在的数据源中。

3应用实例

在本实例中，通过指定5个顺丰快递点和N个配送目的地，采用Teitz-Bart算法来实现求得出一条配送花费达到最小或每个配送中心的花费达到最小。

本系統探讨了基于SuperMap iClient for An-droid（以下均简称为iClient）组件包的移动GIS软件平台的开发方法和原理，并在Android+Java+Eclipse平台上，用iClient组件包设计实验与开发了一套移动网络分析物流配送系统。基于iClient的networkAnalyst接口，以SuperMap公司所发布的长春市区图数据为例，利用Teitz-Bart算法开发出一套物流配送系统。

由加粗部分代码可知此系统的权重名称是花费cost，权重是time，就是修改的权重参数，这个参数更具有计算价值，而且得到的路径也是最优路径。

系统实现如下图所示：

4结束语

移动网络物流配送系统是以Android平台为基础，应用JAVA语言，基于SuperMap iClient的networkAnalyst接口开发而成的。考虑到道路的方向性与通达性，由此建立路网数据模型，采用改进后的Teitz-Bart算法，进行多旅行商分析，从而得出最优的配送路径。通过应用实例可以看出该路径规划是可行的，只要获取了需求点和供应点，它就能快速的择选出最优路径，具有很好的实用价值，是一个非常方便快捷的应用程序。endprint