大规模交通网络实时路径搜索算法研究  

Real-Time Path Searching Algorithm for Large Traffic Network

作　　者：李树彬[1,2] 高自友[1] 林勇 吴建军[1] 李珂[2] 许兆霞[2] 丁青燕[1] 

机构地区：[1]北京交通大学交通运输学院,北京100044 [2]山东省科学院自动化研究所,济南250014

出　　处：《交通运输系统工程与信息》2009年第5期141-147,共7页Journal of Transportation Systems Engineering and Information Technology

基　　金：国家重点基础研究发展计划(973计划)项目(2006CB705500);国家自然科学基金(70801005;70871099);公安部应用创新计划项目(2007YYCXSDST057);山东省自然科学基金(Y2008F14);山东省科学院博士基金项目(鲁科院字[2008]102号)

摘　　要：对在研的DynaCHINA软件中大规模交通网络下的实时路径搜索问题进行了研究.提出了新的设计思想,给出了有效路径的产生算法,并设计了支持海量路径数据的存储及高效检索的数据结构.算法充分利用路径的递归特性,降低问题的规模,实现了较小空间花费下的海量路径随机查询.大大提高了大规模交通网络中实时路径搜索问题的计算速度,节省了计算机存储资源.通过与原有算法比较表明,本算法能够在较小的计算机存储资源下,快速有效地处理大规模交通网络中的实时路径搜索问题,具有广阔的应用前景和现实意义.In this paper, the real-time path searching problem for the larger traffic network is investigated in the developing software--DynaCHINA, and an effective path generation algorithm is proposed. Addition- ally, a new data structure is provided to store large count of paths and support high performance searching. By the reeursive property, the new algorithm can reduce the size of problem whic^i derives the paths with a small space required. As a result, it improves the computing speed greatly in real-time path searching and saves the computer memory resource significantly. Compared with original algorithms, it is found that the proposed algorithm deals with the real-time path searching problem in large traffic network quickly and effec- tively with a small computer memory. Therefore, the algorithm can be used in practical traffic management.

关 键 词：大规模交通网络 实时 路径搜索 递归算法 动态中国 

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