基于PIN LRU算法的路网最短路径研究  

Research on road network shortest path based on PIN LRU algorithm

作　　者：赵雍 周孝军 ZHAO Yong;ZHOU Xiaojun(Land Surveying Planning and Design Institute of Shaanxi Land Engineering Construction Group Co.,Ltd.,Xi’an,Shaanxi 710075,China;The First Topographic Surveying Brigade of the Ministry of Natural Resources,Xi’an,Shaanxi 710054,China)

机构地区：[1]陕西地建土地勘测规划设计院有限责任公司,陕西西安710075 [2]自然资源部第一地形测量队,陕西西安710054

出　　处：《测绘技术装备》2023年第2期11-16,共6页Geomatics Technology and Equipment

摘　　要：在陕西省交通地理信息系统数据存储与导航的实际应用中,由于路网数据量庞大,直接利用最短路径算法计算会出现内存溢出,导致无法完成计算。针对此问题,本文提出利用R Tree与最近最少使用(Least Recently Used,LRU)算法缓存优化管理相结合的锁定最近最少使用(Pin Least Recently Used,PIN LRU)算法对实际路网进行最短路径计算。与LRU、基于四叉树的空间数据缓存策略模型(Spatial Least Recently Frequently Used,SLRFU)算法相比,该算法在10个途经点路径检索时的耗时为5000 ms,SLRFU算法耗时为30000 ms,LRU算法耗时为75000 ms。试验测试证明,该算法检索响应高效,可解决计算实际数据过程中因内存溢出而导致系统崩溃的问题。Due to the huge amount of road network data,direct calculation using the shortest path algorithm will overflow the memory and cannot complete the calculation in the practical application of data storage and navigation in the Shaanxi transportation geographic information system.To solve the problem above,this paper proposes a PIN LRU algorithm which combine R Tree operation characteristics and LRU to calculate shortest path in the actual complex network.Compared with LRU and SLRFU algorithm,PIN LRU algorithm has a fast response in 10 paths,which takes 5,000 ms to retrieve,30,000 ms for SLRFU,and 75,000 ms for LRU.The experimental results show that the algorithm is efficient in retrieval response and can solve the problem of system crash caused by memory overflow during the calculation of actual data.

关 键 词：交通地理信息系统 最短路径 R Tree 锁定最近最少使用算法 缓存优化管理 

分 类 号：P208[天文地球—地图制图学与地理信息工程]