车载导航系统动态最优路径算法研究  

Dynamic Optimal Path Algorithm in Vehicle Navigation System

作　　者：王鹏飞[1] 马寿峰[1] 贾宁[1] 

机构地区：[1]天津大学管理与经济学部,系统工程研究所,天津300072

出　　处：《交通运输系统工程与信息》2011年第3期113-118,共6页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家自然科学基金(70971094);天津市科技支撑计划重点项目(08ZCKFSF01000)

摘　　要：目前用于车载导航系统最优路径搜索算法大多数只能适应静态交通环境,当交通环境或者出行者位置发生改变时,需要重新计算修改整个最优路径,速度较慢.在LPA算法的基础上,首先将出行者位置不断变化而目的地位置固定不变的问题转化为起点固定终点固定的问题,另一方面结合增量搜索的思想,利用先前搜索的结果不断更新当前搜索过程中的遗传值,来提高搜索的效率,并最终提出了可用于车载导航系统的动态最优路径搜索算法.实验结果表明,在交通环境和出行者位置同时发生变化的情况下,最优路径搜索时间要比静态算法小很多.最后将算法部署在WindowsMobile手机移动平台上,实际结果表明,该算法较好地解决了动态最优路径问题,具有理论参考价值和实际意义.Most of the optimal path search algorithms in the current vehicle navigation system can only satisfy the static traffic environment.When traffic environment and the traveler position changes,the data will be recalculated and the overall optimal path will be searched again,the process is very slow.On the basis of the LPA algorithm,it first changes the problem of unfixed position of traveler and fixed destination into a fixed origin and destination problem.On the other hand,with the idea of incremental search it updates its heuristics between search episodes.At last,a dynamic optimal path search algorithm is proposed for in-vehicle route guidance system.Then the algorithm is developed on Windows Mobile platform,the analytical results demonstrate that when traffic environment and the traveler position changes,the algorithm can quickly search for the optimal path.The cost of search time is much smaller than the static shortest path-finding algorithm.Experiments and actual results show that this algorithm is of great referential value and applicable significance.

关 键 词：信息技术 车载导航系统 动态最优路径算法 增量搜索 LIFELONG PLANNING A＊ 

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