【作者】 郑烟武；

【导师】 蔡文学；

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

【摘要】 路径规划是网络优化中的经典问题,路径规划广泛应用于交通运输、通信工程、计算机工程、电网工程等领域。道路网络中的路径规划问题的本质是图论中的最短路问题,Dijkstra算法是公认的求解该问题最经典的算法。但是随着网络复杂性的提高和网络规模的扩大,Dijkstra算法的计算效率无法满足实际的要求。于是,很多加速策略被提了出来,比如启发式策略、压缩搜索空间策略、层次搜索策略等等。在这些方法中,基于道路等级的分层分区路径规划算法具有优势,该算法考虑了路网特性和路径选择偏好,且通过缩减搜索空间来提高算法效率,得到了广泛的重视和研究。同时,随着浮动车等动态交通信息采集技术的发展,动态交通信息可获得性得到了提高,基于动态交通信息的路径规划成为了近年来研究的热点。论文以《2008年广东省现代信息服务业发展专项资金扶持项目》为依托,对路径规划算法进行研究,论文主要完成了以下三部分工作的研究:一、通过基于道路等级的分层分区路径规划算法的分析,发现该算法在应用中存在同层路网连通性无法保证、路径绕远和分区不合理等问题,为此,论文对该算法进行改进,引入虚拟边、新分区算法和其他优化方法,实现了改进分层分区路径规划算法;二、路径规划时使用者不仅关心路径长度同时关心行驶时间,而不同道路等级的路段在长度相同的情况下具有不一样的通行时间,因此,单纯考虑基于路段长度路阻函数的静态路径规划算法是不够的,需要对路阻函数进行扩展,论文考虑不同等级道路的路网特性,将动态路网特性静态化,考虑了基于道路等级的路段平均旅程时间的路阻函数,然后基于以上两类路阻函数,对比其他路径规划算法进行改进分层分区算法的计算效率和规划结果的分析;三、随着动态交通信息可获得性的提高,论文基于动态交通数据构建动态路网,提出基于分层分区的动态路径规划算法,实现基于大规模路网的动态路径规划。通过在广东省路网上进行的大规模测试,结果表明论文提出的改进分层分区路径规划算法不仅计算效率高而且规划的路径更合理;同时通过对基于分层分区的动态路径规划算法的实现,发现本文提出的动态路径规划算法得到的规划结果会随着出发时刻或到达时刻的变化而变化,最后,通过在实际的物流运作中的应用证明该算法具有良好的实际应用价值。更多还原

【Abstract】 Route planning is a classical problem in network optimization, which is widely used in transportation, communication engineering, computer engineering, electricity grid 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 for large road networks this would be far too slow. Thus, many speedup strategies are proposed, such as heuristic strategy, searching space compression strategy, hierarchical strategy and so on. During which, the hierarchical and partitioned algorithm based on road class has the advantage and which is widely studied, for the algorithm considers the character of road networks and the path selection preference, and which improves the compute efficiency by reducing the search space. 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.In this context, this thesis studies the route planning algorithm based on the“2008 Guangdong Province modern information service development”project. The main works of this thesis are as follows:Firstly, analyze the hierarchical and partitioned route planning algorithm, and found out that the algorithm has some problems such as the disconnection of the same road layer, unreasonable planning result and partitioning method and so on. Then virtual link, new partitioning algorithm and some other optimal methods are taken, and the adaptive hierarchical and partitional A-star algorithm is proposed.Secondly, when use the route planning service the users concern both the length of the path and the travelling time, while different road sections take various passage time of the same road length, which means the static route planning algorithm consider the road length impedance function is not enough, we should extend the impedance function. Therefore, different road networks’character is considered, and average traveling time impedance function is used to evaluate the dynamic road networks. An experiment is taken to check the computation efficiency and planning rationality of the algorithm based on two impedance functions compare to different route planning algorithms.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 hierarchical and partitioned A-star 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 adaptive hierarchical and partitioned A-star algorithm is more efficient and the planning result is more reasonable, and the planning result vary with different departure time or arrival time when use the dynamic route planning algorithm proposed by the thesis, the application in the logistics operation also proved that the algorithm has good practical value.更多还原