改进的dijkstra算法在物流配送运输路线规划中的应用

《改进的dijkstra算法在物流配送运输路线规划中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、改进的Dijkstra算法在物流配送运输路线规划中的应用夏华丽1王俊珺21中国矿业大学（北京）机电与信息工程学院1000832河南商业高等专科学校计算机应用系450045特点，结合物流配送运输路线规划的Dijkstra算法的基本思路是:假设摘要实际情况，将该地理网络模型由下列每个点都有一对标号(d,p)，其中d是本文结合物流配送运输路线规划的实际情jjj地理网络元素组成：网络边从起始点s到终点j的最短路径的长况，将现实世界的地理网络抽象为便于计算机实现的物流配送运输路线规划地理网络模（NetWorkArcs），

2、网络结点度；pj则是从s到j的最短路径中j点型；选择Dijkstra算法做为该网络模型分析算（NetWorkNodes），拐向设置的前一点。求解从起始点s到点j的最法的基础，并对其进行优化，将优化后的算（Turns）和阻断（Breaks）等。短路径算法的基本过程如下:法利用VC++语言进行仿真实现，给出具体1)初始化。起始点设置为:①d=0，s实现的数据结构。3.算法的选择与优化p为空；②所有其他点：s关键字现实世界的地理网络现象经过一系；③标记起始点s，记物流配送;地理网络;最短路径;Dijkstra算法列的

3、抽象和近似模拟，形成了便于计k=s，其他所有点设为未标记的。算机实现的物流配送运输路线规划地理2)检验从所有已标记的点k到其网络模型。如何根据已形成的地理网直接连接的未标记的点j的距离，并设络模型选择最短路径分析算法就成为物置:流配送运输路线规划分析的重点。1.引言3.1算法的选择式中，l是从点k到j的直接连接kj目前对配送路线进行经常性规划调目前提出的基于图论的最短路径的距离。整是大多数配送中心的一项重要工作，算法大致有17种，经专家测试，其3)选取下一个点，从所有未标记由于在配送运输路线规划上，基本问题中有

4、3种效果比较好，它们分别是：的结点中，选取d中最小的一个i:j就是求最优路线，最优路线的核心算法TQQ、DKA以及DKD，其中TQQ算[d,所有未标记的点j]就是最短路径算法。所以对于物流配送法的基础是图增长理论，后两种算法j点i就被选为最短路径中的一点，运输路线规划的分析要涉及到两方面问则是基于Dijkstra的算法。Dijkstra并设为已标记的。题：一是要建立适合物流配送运输路线算法是经典的最短路径算法,目前多数4)找到点i的前一点。从已标记规划的地理网络模型；二是要选择合适系统解决最短路径问题采用了Di

5、jkstra的点中找到直接连接到点i的点，作的最短路径分析算法在该网络模型上进算法为理论基础,只是不同系统对行实现。Dijkstra算法采用了不同的实现方法为前一点,设置:[1]5)标记点i。如果目标点已标记。Dijkstra算法一般用于计算一个2.地理网络模型的表示源结点到所有其他结点的最小代价路或者所有点已标记，则算法完全退出，否则，记k=i，转到2)再继续。将图论中网络概念引入到地理空间径，并且能够适应网络拓扑的变化，从上面可以看出，在实现Dijkstra中，描述和表达面向网络的地理目性能稳定，所以我们把

6、Dijkstra的算算法的过程中，核心步骤就是从未标标，就产生了地理网络。物流配送运法作为物流运输路线选择的分析算法基记的点中选择一个权值最小的弧段。输路线规划地理网络作为空间实体的地础。[2]这是一个循环比较的过程，如果将未理网络与图论中的网络相比较有其自身3.2Dijkstra算法描述-103-交通运输中国科技信息2006年第22期CHINASCIENCEANDTECHNOLOGYINFORMATIONNov.2006标记点以无序的形式存放在一个链表或intiCode2;右多边形码；floatfValues

7、;属性项,表示结点数组中，那么要选择一个权值最小的intiLineType;线特征1.折线2.阻值;弧段就必须把所有的点都扫描一遍。光滑曲线3.Breize曲线；}在大数据量的情况下，这将会影响计}5）、地理网络本身也是一种空间对算速度。2）、网络结点象，可以用一个类来表示。设计如下：3.3Dijkstra算法的改进网络结点有坐标信息和属性信息。calssCnetWork:publicCobject对Dijkstra算法的改进有多种方设计如下：{法，由于我们是应用在物流配送运输路classCNetNode:pu

8、blicCPOINTpublic:线规划的地理网络中，结合实际情况，{intiNetId;网络标识码；我们选择堆排序对未标记结点进行排序public:intiUsId;网络用户标识码；来提高算法的执行效率。选择堆排序方intiInterId;内部号；CNetArcs*m_pNetArc;弧段指法，将结点最短路径值作为堆排序的关intiUsid;用户编码；针；键字，有如下依据[3]:in