交通运输系统工程与信息
交通運輸繫統工程與信息
교통운수계통공정여신식
JOURNAL OF COMMUNICATION AND TRANSPORTATION SYSTEMS ENGINEERING AND INFORMATION
2008年
2期
64-68
,共5页
杨东凯%陈志宇%吴今培%徐爱功
楊東凱%陳誌宇%吳今培%徐愛功
양동개%진지우%오금배%서애공
路径规划%交通约束%Dijkstra算法
路徑規劃%交通約束%Dijkstra算法
로경규화%교통약속%Dijkstra산법
分析了路径规划问题及其在交通约束条件下的特点.从算法改进和模型改进两方面对路径规划算法进行了研究,在详细分析Dijkstra算法步骤和对偶法的基础上,给出了交通约束的数学模型及道路网络的相关定理.基于传统Dijkstra算法,对搜索过程中的节点和边的标记方式和规则进行了改进,提出了一种在交通约束条件下的高效路径规划算法.该算法通过减少搜索节点和标记边的次数而减少搜索过程中的运算量.仿真结果表明,该算法只有对偶法1/3～1/4的运算量.
分析瞭路徑規劃問題及其在交通約束條件下的特點.從算法改進和模型改進兩方麵對路徑規劃算法進行瞭研究,在詳細分析Dijkstra算法步驟和對偶法的基礎上,給齣瞭交通約束的數學模型及道路網絡的相關定理.基于傳統Dijkstra算法,對搜索過程中的節點和邊的標記方式和規則進行瞭改進,提齣瞭一種在交通約束條件下的高效路徑規劃算法.該算法通過減少搜索節點和標記邊的次數而減少搜索過程中的運算量.倣真結果錶明,該算法隻有對偶法1/3～1/4的運算量.
분석료로경규화문제급기재교통약속조건하적특점.종산법개진화모형개진량방면대로경규화산법진행료연구,재상세분석Dijkstra산법보취화대우법적기출상,급출료교통약속적수학모형급도로망락적상관정리.기우전통Dijkstra산법,대수색과정중적절점화변적표기방식화규칙진행료개진,제출료일충재교통약속조건하적고효로경규화산법.해산법통과감소수색절점화표기변적차수이감소수색과정중적운산량.방진결과표명,해산법지유대우법1/3～1/4적운산량.
