基于gis优化dijkstra算法在物流中心选址中的研究new

《基于gis优化dijkstra算法在物流中心选址中的研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第24卷第8期计算机应用研究Vo1．24No．82007年8月ApplicationResearchofComputersAug．2007基于GIS优化Dijkstra算法在物流中心选址中的研究球万莉，黄挚雄，李志勇(中南大学信息科学与工程学院，长沙410075)摘要：基于传统的Dijkstra算法，提出了一种采用二叉堆结构和网络边存储模型的优化Dijkstra算法。实验结果表明：优化后的算法是切实有效的，将其应用到物流中心选址中得到了较满意的选址方案。关键词：地理信息系统；最短路径；迪克斯特

2、拉算法；二叉堆；优先级队列；物流中心中图分类号：TP311．5文献标志码：A文章编号：1001-3695(2007)08-0289．03ResearchofoptimalDijkstraalgorithminlogisticcenterlocationbasedonGISWANLi，HUANGZhi-xiong，LIZhi—yong(SchoolofInformationScience＆Engtneering，CentralSomhUniversity，Changsha410075，China)Abstract：Thispaperpropo

3、sedanoptimalDijkstraalgorithmwhichadoptedthestructureofbinaryheapandnetworksidestor-agestructuremode1．Theexperimentalresultprovesthattheoptimalalgorithmiseffectiveandthelogisticscenterlocationcanobtainasatisfactoryschemebyadoptingthealgorithm．Keywords：GIS；shortestpath；Dijk

4、straalgorithm；binaryheap；priori~queue；logisticcenter效率。O引言1传统的Dijkstra算法现代物流是现代化生产的重要组成部分。物流中心在现代商品流通中的作用极大。它是作为商品周转、分拣、配货、保Dijkstra算法是一个按路径长度递增次序产生最短路径管和流通加工等活动的据点，克服在流通过程中所产生的时间的算法。这种方法实现了从某个源点到其余各顶点的最短路和空间障碍，促进商品按顾客要求顺利转移。物流中心的合理径，它的时间复杂度是0(n)。算法描述如下：布局是物流系统中具有战略意义的投资决策

5、问题。物流中心a)假设用带权的邻接矩阵ares表示带权有向图，ares[i]布局是否合理，将对整个系统的物流合理化和商品流通的社会[力表示弧<，>上的权值。若<，，>不存在，则设置arcs[i]效益有着决定性的影响。[力为(在计算机上可用允许的最大值代替)。s为已找到从随着计算机科学和信息科学的发展，地理信息系统出发的最短路径的终点集合，它的初始状态为空集。那么，(GIS)[1l在人们生产和生活中的应用日益广泛。而将地理信从出发到图上其余各顶点(终点)可能达到的最短路径长息系统等现代信息技术应用于物流中心选址问题，可以更方度的初值为便、更准

6、确地解决该问题。影响物流中心选址的因素非常多，D[i]=arcs[1ocatevex(G，)[i]]；∈V(1)本文只考虑路径因素，路径最短即为所求地址。目前，关于最其中：G为指定的一个带权有向图；D是引进的一个辅助向量，短路径搜索算法研究很多。其中1959年Dijkstra提出的单源它的每个分量D[i]表示当前所找到的从始点”到每个终点”问题算法是最适合拓扑网络中两节点最短路径搜索的算法之的最短路径长度。一本文将此算法称为传统算法。在传统算法中，计算效率和，b)选择v，使得存储效率都很低。因此，本文在提高存储效率方面将采用的是DEj]=m

7、in{D[i]∈V—S}(2)一种新型的网络存储模型——网络边存储模型。这样可使内其中：，就是当前求得的一条从出发的最短路径的终点。令存的占用量大大减少。在提高计算效率方面将采用二叉堆数s=su{}(3)据结构，这样使得算法的效率得到很大的提高，系统的性能也其中：s为已求得最短路径的终点集合。有相应的优化。在物流中心选址系统中采用这种优化算法，可e)修改从出发到集合V—S上任一顶点可达的最短以快速地得到物流中心选址方案，大大提高了物流系统的路径长度。例如D[力+arC8[力[k]

8、修返日期：2006—07—19基金项目：国家自然科学基金资助项目(50405034)；湖南省自然科学基金资助项目(03JJY3O94)作者简介：万莉(1982一)，女，硕士研究生