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