文档介绍：------------------------------------------------------------------------------------------------ ——————————————————————————————————————物流配送路线规划中的最短路径研究《农业网络信息》2007年第5期网络与电子商务/政务王俊珺1,夏华丽2,田源1 (1 . 河南商业高等专科学校计算机系, 河南郑州450004 ; 2. 中国矿业大学( 北京) 机电与信息工程学院, 北京100083 ) 摘要: 本文通过对Dijkstra算法、 A*算法和Floyd 算法等最短路径算法的分析研究, 选择Dijkstra算法作为物流配送路线规划的核心算法;并且针对原始Dijkstra算法的不足, 分别对原始Dijkstra算法的数据存储方式、执行效率和数据结构提出了优化的方法。关键字: 配送路线; 最短路径; Dijkstra算法;A×算法;Floyd算法中图分类号:F760 文献标识码:B 文章编号: 1672-6251 ( 2007 ) 05-0060- 03 Thestudyofshortestpathinlog isticsandrouteplan WANGJun-jun1 , XIAHua-li2 , TIAN ------------------------------------------------------------------------------------------------ —————————————————————————————————————— Yuan1 (1 . HenanBusinessCollege , Zhen gzhou450004 , China ;2. ChinaUnive rsityofMining&Technology , Beiji ng100083,China) Abstract : InthispapertheDijks traalgorithmisselectedastheke yalgorithmoflogisticsandthetr ansitrouteplanafterresearchof Dijkstraalgorithm , A*algorithma ndFloydalgorithm , asforthedefic iencyofDijkstraalgorithm , thisp aperalsogivesmodifiedmethodsf orDijkstraalgorithminpackingo fdatamanner , executionefficienc yanddatastructureseparately . Ke ywords:Logistics;Shortestpath ; Dijkstraalgorithm;A*algorithm ; Floydalgorithm 1引言[1] 配送运输是物流系统中最重要的组成部分之一, 前公认的求解最短路问题高效的经典算法之一。Dijk- ------------------------------------------------------------------------------------------------ ——————————————————————————————————————正是通过配送运输, 配送中心才得以最终完成货物从生产商到用户的转移。由于配送中心每次配送活动一般都面对多个非固定用户, 并且这些用户坐落地点各不相同, 所以对于它们的配送时间和配送数量也都不尽相同。如果配送中心不进行运输路线的合理规划, 往往会出现不合理运输现象, 不仅造成运输成本上升, 而且导致配送服务水平难以提高, 因此经常对配送路线进行规划调整是大多数配送中心的一项重要工作。在配送中心进行运输路线规划时, 除了两点之间最短路问题外, 多点之间最短路问题也是最常见的问题,如: 旅行商问题和中国邮递员问题,但它们的核心算法也都可以是最短路径算法。 stra算法的基本思路是:假设每个点都有一对标号(dj , pj ) ,其中dj是从起始点s到终点j的最短路径的长度;p j则是从s到j的最短路径中j点的前一点。求解从起始点s到点j 的最短路径算法的基本过程如下: (1 ) 初始化。起始点设置为:① ds=0 , ps , 为空;②所有其他点: di= ∞, pi=? ;③标记起始点s , 记k=s , 其他所有点设为未标记的。(2)检验从所有已标记的点到其直接连接的未标记的点的距离,并设置: 2最短路径算法研究最短路径算法是计算机科学与地理信息科学等领 dj=min[dj,dk+lk