????????????Ч·???滮??

分析了路径规划问题及其在交通约束条件下的特点。从算法改进和模型改进两方面对路径规划算法进行了研究，在详细分析Dijkstra算法步骤和对偶法的基础上，给出了交通约束的数学模型及道路网络的相关定理。基于传统Dijkstra算法，对搜索过程中的节点和边的标记方式和规则进行了改进，提出了一种在交通约束条件下的高效路径规划算法。该算法通过减少搜索节点和标记边的次数而减少搜索过程中的运算量。仿真结果表明，该算法对偶法1/3～1/4的运算量。

High Efficient Route Planning Algorithm Based on Traffic Constraints

This paper analyzes the characteristics of route planning with traffic constraints. It explores the route planning algorithm from both the algorithm modifications and modeling 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.