基于OpenStreetMap最短路径算法的分析与实现
|
摘要
随着计算机网络技术和地理信息科学的发展,最短路径问题无论是在交通运输,还是在城市规划、物流管理、网络通讯等方面,都发挥了重要的作用。文中旨在阐述如何基于OSM运用Dijkstra算法计算两联通节点之间的最短路径。首先介绍了开放式OSM的特点以及地图数据文件中道路图像元素的数据结构;然后运用正则表达式算法从OSM数据中提取出交通道路信息,并选择合适的结构进行存储;最后通过将道路信息抽象成路径拓扑图,并以道路的地理距离作为路径权值,运用Dijkstra最短路径算法求解出两连通节点之间的最短路径。
With the rapid development of computer network and GIS technology,the shortest path problem plays an important role in transportation,city planning,logistics management,network communication,etc. Focus on describing how to use Dijkstra algorithm to calculate the shortest path between two connected nodes based on OSM. Firstly introduce the characteristics of OSM and data structure of road image feature. Secondly,extract road information by regular expression from OSM data file and store them in appropriate construction. Finally,form road topological diagram and takes the geographical distance as road weight,calculating the shortest path between two connected nodes by Dijkstra algorithm.
With the rapid development of computer network and GIS technology,the shortest path problem plays an important role in transportation,city planning,logistics management,network communication,etc. Focus on describing how to use Dijkstra algorithm to calculate the shortest path between two connected nodes based on OSM. Firstly introduce the characteristics of OSM and data structure of road image feature. Secondly,extract road information by regular expression from OSM data file and store them in appropriate construction. Finally,form road topological diagram and takes the geographical distance as road weight,calculating the shortest path between two connected nodes by Dijkstra algorithm.
引文
[1]马超.遗传算法和Dijkstra算法在动态权值系统中的比较[J].计算机技术与发展,2012,22(9):21-24.
[2]苏莹,王英杰,余卓渊.一种建立公交网络的最短路径改进算法[J].地球信息科学,2005,7(2):99-104.
[3]杜莹,刘建忠.基于WebGIS最优路径分析的设计与实现[J].测绘学院学报,2002,19(1):56-58.
[4]刘文宝,邓敏,易彤.矢量GIS中模糊地理边界的分析[J].山东科技大学学报:自然科学版,2000,19(1):28-32.
[5]白尘.交通路网中最优路径算法的道路权重选择[J].中国管理信息化,2009,12(15):54-56.
[6]赵春燕,王国华,周军.支持城市多种交通方式的最佳路径分析[J].测绘信息与工程,2009,8(4):8-10.
[7]何卫.Web地理信息系统的设计与实现[D].西安:西安电子科技大学,2004.
[8]Sun Yushan.Embedded vehicle navigation system based on VxWorks[C]//Proceedings of the 5th international symposium on test and measurement(volume 1).[s.l.]:[s.n.],2003.
[9]Zhang Yi,Zhang Meng,Liang Yanchun.Application of an improved dijkstra algorithm in multicast routing problem[J].Computer science,2009,36(8):205-207.
[10]Wang Yawen,Wang Xili,Cao Ham,et al.Shortest routeplanning algorithm within dynamic restricted searching area[J].Application research of computers,2007,24(7):89-91.
[11]常志明,毛新军,齐治昌.基于Agent的网构软件构件模型及其实现[J].软件学报,2008,19(5):1113-1124.
[12]Chen Wenjie.The research and application of reasonable route set of route choice[D].Guangzhou:Guangzhou Sun Yat-sen University,2008.
[13]Azevedo J A,Madeira J J E R S,Martins E Q V,et al.A shortest paths ranking algorithm[C]//Proc of the annual conf AIRO.[s.l.]:[s.n.],1990:1001-1011.
[14]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学报,1999,24(3):209-212.
[15]曾松,杨佩昆,方棣波.城市道路网结构的可达性评价[J].同济大学学报,2001,29(6):666-671.
[16]王行风,贾凌.GIS支持下的城市交通网络最短路径研究[J].计算机与现代化,2005,13(3):9-12.
[17]Martins E Q V,Santos J L E.A new shortest paths ranking algorithm[J].Investigacao operacional,1999,20(1):47-62.
[18]Sim K M,Sun W H.Ant colony optimization for routing and load-balancing:survey and new directions[J].IEEE transactions on system,2003,33(5):560-572.
[2]苏莹,王英杰,余卓渊.一种建立公交网络的最短路径改进算法[J].地球信息科学,2005,7(2):99-104.
[3]杜莹,刘建忠.基于WebGIS最优路径分析的设计与实现[J].测绘学院学报,2002,19(1):56-58.
[4]刘文宝,邓敏,易彤.矢量GIS中模糊地理边界的分析[J].山东科技大学学报:自然科学版,2000,19(1):28-32.
[5]白尘.交通路网中最优路径算法的道路权重选择[J].中国管理信息化,2009,12(15):54-56.
[6]赵春燕,王国华,周军.支持城市多种交通方式的最佳路径分析[J].测绘信息与工程,2009,8(4):8-10.
[7]何卫.Web地理信息系统的设计与实现[D].西安:西安电子科技大学,2004.
[8]Sun Yushan.Embedded vehicle navigation system based on VxWorks[C]//Proceedings of the 5th international symposium on test and measurement(volume 1).[s.l.]:[s.n.],2003.
[9]Zhang Yi,Zhang Meng,Liang Yanchun.Application of an improved dijkstra algorithm in multicast routing problem[J].Computer science,2009,36(8):205-207.
[10]Wang Yawen,Wang Xili,Cao Ham,et al.Shortest routeplanning algorithm within dynamic restricted searching area[J].Application research of computers,2007,24(7):89-91.
[11]常志明,毛新军,齐治昌.基于Agent的网构软件构件模型及其实现[J].软件学报,2008,19(5):1113-1124.
[12]Chen Wenjie.The research and application of reasonable route set of route choice[D].Guangzhou:Guangzhou Sun Yat-sen University,2008.
[13]Azevedo J A,Madeira J J E R S,Martins E Q V,et al.A shortest paths ranking algorithm[C]//Proc of the annual conf AIRO.[s.l.]:[s.n.],1990:1001-1011.
[14]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现[J].武汉测绘科技大学学报,1999,24(3):209-212.
[15]曾松,杨佩昆,方棣波.城市道路网结构的可达性评价[J].同济大学学报,2001,29(6):666-671.
[16]王行风,贾凌.GIS支持下的城市交通网络最短路径研究[J].计算机与现代化,2005,13(3):9-12.
[17]Martins E Q V,Santos J L E.A new shortest paths ranking algorithm[J].Investigacao operacional,1999,20(1):47-62.
[18]Sim K M,Sun W H.Ant colony optimization for routing and load-balancing:survey and new directions[J].IEEE transactions on system,2003,33(5):560-572.