【作者】 周兴；

【导师】 蔡文学； 巫建文；

【作者基本信息】 华南理工大学 ， 物流工程， 2011， 硕士

【摘要】 路径规划问题网络优化问题中典型问题,它广泛应用于物流运输、交通导航、通信工程、计算机工程等领域。交通路网中的路径规划问题的本质是图论中的最短路问题,Dijkstra算法是公认的计算最短路的经典算法。但是随着交通的发展,道路网络复杂性不断提高,路网规模也不断扩大;Dijkstra算法的计算效率已无法满足实际的要求。于是,很多加速策略被提了出来,比如启发式策略、双向搜索策略、分层搜索策略等。在些改进策略中,基于路网分层压缩策略的Highway Hierarchical算法具有优势,该算法对路网进行预处理,按一定比例进行压缩,通过缩减搜索空间和搜索量来提高算法效率,得到了广泛的重视和研究。随着浮动车等动态交通信息采集技术的发展,动态交通信息可获得性得到了提高,基于动态交通信息的路径规划成为了近年来研究的热点。同时,随着物流运输系统、公众出行交通信息服务系统对路径规划需求的上升,在Internet环境下,如何构建高效合理的动态路径规划系统成为大家研究的重点。论文依托《2008年广东省现代信息服务业发展专项资金扶持项目》和《广东省公众出行服务项目》,对路径规划算法进行研究以及在Internet环境下对路径规划应用系统进行设计,论文主要完成了以下三部分工作的研究:一、通过对基于路网分层压缩策略的Highway Hierarchical算法的分析,发现该算法在应用中存在路网压缩成环问题、预处理数据存储问题和完整最短路计算问题;采用无环压缩策略、分层存储策略和局部最短路存储策略,对算法进行了改进,并实现了改进的Highway Hierarchial算法;二、在Internet环境下,设计和实现了路径规划系统,通过分析系统实现中存在的网络数据传输和多用户并发请求的问题,运用WCF技术,构建分布式系统,实现高效合理的路径规划系统;三、随着动态交通信息可获得性的提高,论文基于动态交通数据构建时间依赖路网,提出基于Highway Hierarchical算法的动态路径规划算法,实现动态路径规划系统。通过在广东省路网上进行的大规模测试,结果表明论文提出的改进Highway Hierarchical算法在大规模路网中仍具有高效性;同时保证了Internet环境下路径规划系统服务的高效性,最后,通过在物流运输和公众出行中的应用证明该系统具有良好的实际应用价值。更多还原

【Abstract】 Route planning is a classical problem in network optimization, which is widely used in logistics transportation, traffic navigation, communication engineering, computer engineering and other fields. The essence of route planning in road networks is the shortest path problem in graph theory, and Dijkstra algorithm is recognized as the most classical algorithm to solve this problem.But with the development of transportation, the complexity of the road network increased and the scale of network expanded such as Dijkstra algorithm would be far too slow in large road networks. Thus, many speedup strategies are proposed, such as heuristic strategy, bidirectional searching strategy, hierarchical compression strategy and so on. During which, the highway hierarchical algorithm based on hierarchical compression strategy has the advantage and which is widely studied, for the algorithm preprocess road network according to a certain percentage of compression, and which improves the compute efficiency by reducing the search space and search volume. Meanwhile, with the development of dynamic traffic information collection technology such as floating cars technique, the availability of dynamic traffic information has been improved, the dynamic route planning has become a study hotspot in recent years. As the demand of planning path rising in logistics and transport systems and public transportation information service, how to build effective and rational dynamic path planning system in the Internet environment becomes a focus of the study. In this context, this thesis studies the route planning algorithm and system based on the―2008 Guangdong Province modern information service development‖project. The main works of this thesis are as follows:Firstly, through the analysis of the Highway Hierarchical algorithm based on road network compression strategy, find that the algorithm has problems such as compression into the ring in road network, the storage of pretreatment data problem and the calculate of the shortest path problem. Improve and implement the algorithm with no-ring compression strategy, tiered storage strategy and local shortest path storage strategy. Secondly, design and implement the path planning system in the internet environment. After analyzing the data transmission problem and multi-user concurrency of the request problem of system, use WCF technology and build up a distributed system, to achieve a reasonable and efficient path planning system.Thirdly, with the availability of dynamic traffic information being improved, this thesis builds dynamic road networks based on the available dynamic traffic data, and the dynamic route planning based on highway hierarchical algorithm is proposed. Dynamic route planning based on large-scale road networks is carried out.A large scale experiment is taken in the road networks of Guangdong Province. The experiment results show that the improved highway hierarchical also is more efficient in the large-scale road network. It ensures the efficiency of path planning system in the internet. The application in the logistics transportation and public travel service also proved that the system has good practical value.更多还原