基于交通约束的高效路径规划算法  

High Efficient Route Planning Algorithm Based on Traffic Constraints

作　　者：杨东凯[1] 陈志宇[1] 吴今培[1] 徐爱功[2] 

机构地区：[1]北京航空航天大学电子信息工程学院,北京100083 [2]辽宁工程技术大学地理空间信息技术及应用重点实验室,辽宁阜新123000

出　　处：《交通运输系统工程与信息》2008年第2期64-68,共5页Journal of Transportation Systems Engineering and Information Technology

基　　金：辽宁工程技术大学地理空间信息技术及应用重点实验室开放基金(2004007)

摘　　要：分析了路径规划问题及其在交通约束条件下的特点．从算法改进和模型改进两方面对路径规划算法进行了研究，在详细分析Dijkstra算法步骤和对偶法的基础上，给出了交通约束的数学模型及道路网络的相关定理．基于传统Dijkstra算法，时搜索过程中的节点和边的标记方式和规则进行了改进，提出了一种在交通约束条件下的高效路径规划算法．该算法通过减少搜索节点和标记边的次数而减少搜索过程中的运算量．仿真结果表明，该算法只有对偶法1／3-1／4的运算量．This paper analyzes the characteristics of route planning with traffic constraints. It explores the route planning algorithm from both the algorithm modifications and modelin modifications. Meanwhile, based on the elaborate analysis of Dijkstra algorithm steps and dual method, this paper discusses the mathematic model with traffic constraints and the relative theorem on road network. In addition, the traditional Dijkstra algorithm is modified for the node searching and link marking rule during the planning process. Furthermore, a high efficient algorithm is proposed with consideration of traffic constraints. It decreases the computation time through decreasing the searching nodes and link marking times. The simulation result indicates that the computation complexity the presented algorithm is 1/3-1/4 of the dual method.

关 键 词：路径规划 交通约束 Diikstra算法 

分 类 号：U491[交通运输工程—交通运输规划与管理]