最短路径Auction算法及其在路径诱导中的应用  

Auction Algorithm for Shortest Paths and its Application in Route Guidance

作　　者：杜牧青[1] 程琳[1] 

机构地区：[1]东南大学交通学院,南京210096

出　　处：《武汉理工大学学报（交通科学与工程版）》2012年第6期1161-1165,共5页Journal of Wuhan University of Technology（Transportation Science & Engineering）

基　　金：国家重点基础研究发展计划(973计划)项目(批准号:2006CB705500);国家高技术研究发展计划项目(批准号:2007AA11Z205);国家自然科学基金项目(批准号:50578037)资助

摘　　要：通过采用C#语言程序,对比传统路径算法,并在实际道路网络和随机网络中进行了试验,测试了算法在求解网络"一对一"最短路径问题时的运算性能.结果表明,Auction算法在求解此类问题时,体现算法自身原理的优势,虽然整体性能表现不及经典的路径算法,即迭代步骤略多,但仍有改进的余地.Taking Dijkstra＇s algorithm as a reference, the algorithm＇s performance was tested in the ＂one-to-one＂ shortest path problems via a corresponding computer program coded in C #. The compu- tational tests on the actual networks and random networks show the advantages of Auction algorithm＇ s principle. But its overall performance is not as good as labeling algorithms, i.e. some computational steps of iteration are repeated too many times, affecting the efficiency. Reducing these redundant op- erations, Auction algorithm could be improved.

关 键 词：道路网络 路径诱导 最短路径 标号算法 Auction算法 

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