基于M2M模型的出行路径规划算法  

Path planning algorithm based on M2M model

作　　者：杨兆升[1] 汪健[1] 张颖鹏[2] 

机构地区：[1]吉林大学交通学院,长春130022 [2]华南理工大学计算机科学与工程学院,广州510640

出　　处：《吉林大学学报（工学版）》2008年第S2期45-49,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：吉林大学“985工程”项目;“863”国家高技术研究发展计划项目(2007AA12Z242，2007AA11Z218，2007AA11Z245)．

摘　　要：提出了一种源自于人类认知思维模式的普遍适用的算法设计模型——M2M模型(Macro to Micro model)。M2M模型的数据结构用O(n)时间建成,并具备高度的并行性。针对交通网络的最优路径规划问题,提出了基于M2M模型的交通网络出行路径规划算法,将交通路网运用M2M模型分层分块,减少搜索区域,优化路径搜索速度。实验证明,相对于当前使用较多的Dijkstra及A*等经典算法,本算法在求解速度上有明显提高。A generally applicable algorithm named Macro-to-Micro Model(M2M)is introduced which is derived from the human thinking pattern.The M2M data structure can be built in O(n)time.It can also be built in O(1)time using parallel technology.The thesis proposes a new algorithm based on the M2M.It transform the transportation network to multi-lever and multi-part to decrease the search region.Experiments show that it improves the path search speed compared with the widely used Dijkstra and A* algorithms.

关 键 词：交通运输系统工程 路径规划算法 MACRO to Micro模型 交通网络 

分 类 号：U116.2[交通运输工程]