基于改进teitz―bart算法的移动网络物流配送系统.docx

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

1 改进的 Teitz-Bart 算法Teitz-Bart 算法主要的计算是将需求点分配到其最邻近的供应点，并求总的加权距离这些距离正是用最短路径算法求得的采用类似动态数据结构――供应点数据串和需求点数据串数据串的长度常常可用实际应用中服务距离的最大值来限制，可以大大减少计算时间和内存从供应点的数据串中，可以非常容易找到哪些需求点是在该点的服务范围，而从需求点数据串中可以找出其相邻的供应点Teitz-Bart 算法虽然优点颇多，但是它的计算量颇大，计算时间长但是 Teitz-Bart 算法中是预先求得数据随时随用，以此来提高算法的效率结合它的这个特点在本系统中修改了其权值参数，用一个综合性的权值来考量W=K1*Time+K2vLength+K3*Demand+TurnCost；其中 Time 为时间，Length 为距离，Demand 为所需费用，TurnCost 为转向花费，当转向花费值为负数的时候一般为禁止转弯K1，K2，K3 为时间、距离和所需费用所占的比例图 1 中边所具有的数值为边权在寻求最优路径的时候，边权主要指代的是从起始点出发到终点的过程中所需要的花费，包括时间，费用，道路情况等。

边权值和越大，说明它并不是要选取的路径在地点确定了的情况下，边权值和越小，其路径最优本图中的边权就是经过此公式计算而得的路网的通达性与方向性对于路径的选择具有很重要的意义，有的路段只是单向路，因此在采用 Teitz-Bart 算法的时候要注意有向的路网及其通达性不通达的地方的用∞来表示，进而进行算法的实行，获取其最短路径图内点间可以用一个邻接矩阵 w 来表示这里存在方向性的问题，所以这个邻接矩阵的考虑条件就变了当为单向路的时，w[i，j]=w[i，j]且 w[j，i]=∞；当 i=j 时，w[i，j]=0；当为双向路的时候，w[i，j]=w[i，i]得到以下邻接矩阵：假设 V2，V7 是供应点，其他的为需求点，花费设为 S，则可以通过上面的算法得到 12 条配送路线这 12 种配送路线中只有第五种是最佳的路线其值为 36当需求点为一个的时候，按照算法也有且只有一个供应点对其供应，那么就是获取其最短路径即可2 路网数据模型路网数据模型由路网结点数据和弧段数据拓扑构网而成，利用属性表信息来表达网络的连通性，具体可以通过数据集一对一和一对多的 ID 关联值来表达逻辑模型和几何模型中弧段数据集和结点数据集的拓扑关系。

路网数据模型中由公交站点，设施点，交叉路口等点状物抽象为点成为结点，由道路等线状地物抽象为线段成为弧段所有的数据及路网的方向都存储在 SuperMap SDX+的网络数据集所在的数据源中3 应用实例在本实例中，通过指定 5 个顺丰快递点和 N 个配送目的地，采用 Teitz-Bart 算法来实现求得出一条配送花费达到最小或每个配送中心的花费达到最小本系�y 探讨了基于 SuperMap iClient for An-droid组件包的移动 GIS 软件平台的开发方法和原理，并在Android+Java+Eclipse 平台上，用 iClient 组件包设计实验与开发了一套移动网络分析物流配送系统基于 iClient的 networkAnalyst 接口，以 SuperMap 公司所发布的长春市区图数据为例，利用 Teitz-Bart 算法开发出一套物流配送系统由加粗部分代码可知此系统的权重名称是花费 cost，权重是 time，就是修改的权重参数，这个参数更具有计算价值，而且得到的路径也是最优路径系统实现如下图所示：4 结束语移动网络物流配送系统是以 Android 平台为基础，应用 JAVA 语言，基于 SuperMap iClient 的 networkAnalyst接口开发而成的。

考虑到道路的方向性与通达性，由此建立路网数据模型，采用改进后的 Teitz-Bart 算法，进行多旅行商分析，从而得出最优的配送路径通过应用实例可以看出该路径规划是可行的，只要获取了需求点和供应点，它就能快速的择选出最优路径，具有很好的实用价值，是一个非常方便快捷的应用程序。