计算机应用 ›› 2011, Vol. 31 ›› Issue (03): 651-653.DOI: 10.3724/SP.J.1087.2011.00651

• 人工智能 • 上一篇    下一篇

路网信息不完备条件下的动态最短路搜索

龙科军1,Lee.D.HAN2,王赛政1   

  1. 1. 长沙理工大学 交通运输工程学院,长沙410114;长沙理工大学 道路灾变防治及交通安全教育部工程研究中心,长沙410114
    2. 长沙理工大学 交通运输工程学院,长沙410114;田纳西大学 土木及环境工程系,田纳西 诺克斯维尔37996-2010,美国
  • 收稿日期:2010-09-25 修回日期:2010-11-17 发布日期:2011-03-03 出版日期:2011-03-01
  • 通讯作者: 龙科军
  • 作者简介:龙科军(1974-),男,湖南双峰人,副教授,博士,主要研究方向:智能交通、交通安全与行为;Lee D. HAN(1963-),男,美国田纳西州人,副教授,博士,主要研究方向:智能交通、交通数据融合与挖掘;王赛政(1985-),男,湖南益阳人,硕士研究生,主要研究方向:智能交通。
  • 基金资助:
    国家“十一五”科技支撑计划项目(115-05-YK-038);湖南省科学技术厅科技计划重点项目(2010WK4001)

Shortest path search in road network with incomplete information

LONG Ke-jun1,Lee. D. HAN2,WANG Sai-zheng1   

  1. 1. College of Traffic and Transportation Engineering, Changsha University of Science and Technology, Changsha Hunan 410114, China; Highway Disaster Prevention and Traffic Safety Engineering Research Center of Ministry of Education, Changsha University of Science and Technology, Changsha Hunan 410114, China;
    2. College of Traffic and Transportation Engineering, Changsha University of Science and Technology, Changsha Hunan 410114, China; Department of Civil and Environmental Engineering, University of Tennessee, Knoxville Tennessee 37996-2010, USA
  • Received:2010-09-25 Revised:2010-11-17 Online:2011-03-03 Published:2011-03-01
  • Contact: LONG Ke-jun

摘要: 针对路网信息不完备性、路网结构特征和驾驶员习惯等因素,研究最短路搜索问题。提出以全局规划和局部规划相结合的动态最短路混合规划方法:全局规划中,基于参数d/l(起终点距离d与平均路段长度l之比),确定路径搜索区域的椭圆方程,运用Dijkstra算法生成静态的全局最短路径;局部规划中,结合路网结构特征、突发事件影响范围,提出改进Bug算法,以避免车辆进入全局最短路径上发生的紧急事件或严重堵塞区域,实现动态诱导。仿真实验结果表明,混合规划方法能在路网信息不完备条件下实现最短路径动态诱导,有效避开拥堵区域。

关键词: 智能交通系统, 最短路搜索, 全局规划, 局部规划, 不完备信息

Abstract: Concerning the incomplete information, structural characteristics and driver's habit, issue of the shortest path search in road network was studied. A mixed programming was proposed combining the global and local planning. During global planning, an index d/l was introduced which represented the ratio of Origin-Destination (OD) distance to the average link length, elliptical minimal search area was determined by d/l, and the initial global shortest path was calculated by Dijkstra algorithm. During local planning, an improved Bug algorithm was introduced based on network structure and influence range of unexpected events, and the congested or hazard region along the global planned path was avoid. The simulated experimental results indicate that the mixed planning can search the shortest path dynamically in road network with incomplete information and evade from congestion efficiently.

Key words: Intelligent Transportation System(ITS), shortest path search, global planning, local planning, incomplete information

中图分类号: