国际航线网络中K条最短路径算法改进与仿真
开篇：润墨网以专业的文秘视角，为您筛选了一篇国际航线网络中K条最短路径算法改进与仿真范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：K条最短路径（KSP）问题是国际航线网络实际路径优化问题。通过对航线网络特征与K条最短路径算法的分析，研究了解决KSP问题的典型Yen算法。针对Yen算法求解候选路径占用大量运算时间的问题，提出一种改进Yen算法。改进Yen算法通过借助A*算法的启发式策略，减少了产生候选航线路径的时间，从而提高了算法的搜索效率并减小了算法搜索的规模。通过对国际航线网络实例的仿真，实验结果表明改进Yen算法能够快速求解国际航线网络中的KSP问题；同时，与Yen算法相比，运算效率提升了75.19%以上，能够为航线路径优化提供决策支持。
关键词：国际航线网络；最短路径算法；K条最短路径问题；Yen算法；启发式策略
0 引言
最短路径问题是图论中的一个重要研究课题[1-2]，其目的是在多项式时间内找到图中任意两节点之间的最短路径。近年来我国高铁建设蓬勃发展，对民航业造成了巨大的冲击，驱使我国航空公司的未来空间向国际航线发展。而随着全球航空业的飞速发展，国际航线网络变得越来越复杂，其规模也变得更加庞大。同时，在相同起飞降落机场之间有很多航线路径可供旅客选择。因此，求解K条可行最短路径供旅客根据自身的实际情况进行选择[3-4]就成为国际航线网络所面临的基本问题之一。这种情况反映在最短路径问题上是不仅需要求出最短路径，还需要求出次短、再次短路径，即K条最短路径（KShortestPaths， KSP）问题。
KSP问题最早由Hoffman等[5]提出，多年来一直受到学术界的广泛关注，先后提出了多种求解KSP问题的算法[6-8]。文献[9]将求解KSP问题的算法分为严密算法和有损算法两大类，其中严密算法能够得到问题的最优解，但计算时间代价较大，尤其是当网络规模或求解的K值较大时；有损算法则是根据一些启发式策略，通过损失一定的求解精度来提高算法的时间效率。
目前改进传统的最短路径算法与现有的KSP算法求解大规模网络下K条最短路径问题搜索效率低，而改进的人工智能算法搜索K条路径时易陷入局部最优，不能保证所求路径全局最优，因此上述算法都很难满足国际航线网络实时性、高精确度的要求。我国航线网络路径搜索系统主要采用静态算法求解K条最短路径。然而由于国际航线数据规模庞大，存储事先计算好的航线路径需占用大量的存储空间。此外，用户发出搜索请求时，从庞大的数据库中查找相匹配的静态航线数据需要花费大量时间，使得航线路径结果不能及时反馈给用户。因此，寻求一种高效、动态的KSP搜索算法是解决国际航线网络路径搜索的关键问题之一。
Yen算法[10]是典型的限定无环KSP算法，目前已经提出了多种改进算法[11-13]。Yen算法采用偏离路径算法的思想能够准确地发现网络中任意两节点之间的K条最短路径，十分适合复杂的国际航线网络K条最短路径搜索的高精确度要求。然而Yen算法在选择节点发展候选路径时占用了大量时间，运行速度慢，尤其是当国际航线网络的规模较大时。为此，本文引入A*算法[14]的启发式策略对Yen算法进行改进来求解国际航线网络中的KSP问题，从而弥补Yen算法的不足，既保证算法求解路径的精确度，又能够提高算法的运行效率。通过仿真实验结果表明，改进Yen算法能够快速高效地求解国际航线网络中的K条最短路径问题。
3 仿真实验
3.1 仿真数据及环境
本文为了验证利用改进Yen算法求解国际航线网络KSP问题的有效性，将改进Yen算法与Yen算法进行了比较。实验采用国际航线网络的实际数据作为仿真数据，其共有3728个机场节点，65903条航线。对国际航线网络的相关数据进行整理并建立了相应的数据结构，该数据结构以DEP_LOC（起飞地代码）为主要标识建立数据块，数据块中包含DEP_LOC（起飞机场代码），ARR_LOC（目的机场代码）， ARR_LONGI（目的机场经度），ARR_LATI（目的机场纬度）和AIR_DIS（飞行航线距离）。同时，采用前向星型存储结构（即路网存储结构）对数据进行存储。两种算法在同一实验环境下完成：处理器为Intel Core Duo CPU，主频为2.94GHz，物理内存为2.00GB；操作系统为Windows XP，开发工具为Visual Studio 2008，且仿真实验数据存放在Oracle数据库中，数据库表结构如表1所示。
通过上述5组实验，从不同的角度对改进Yen算法与Yen算法进行了比较。根据实验的运行时间、平均运行时间、最终路径解的长度与候选路径数目对比结果来看，改进Yen算法是有效和可行的。改进Yen算法在复杂规模的国际航线网络中找到K条航线路径的同时，也减小了算法的搜索规模，并提高了算法的时间效率。
4 结语
本文对Yen算法在求解国际航线网络中KSP问题上进行了分析研究，为了提高Yen算法搜索K条最短路径的时间效率，提出了结合A*启发式策略的改进Yen算法。针对国际航线网络搜索规模庞大与实时性的特点，通过引入启发式策略缩小了算法的搜索空间，使得搜索路径更加具有针对性，从而减小了算法求解KSP问题的搜索规模与运行时间。与Yen算法相比，改进Yen算法具有更加突出的时间优势，大大提高了算法的求解效率。数据仿真结果表明：改进Yen算法在求解国际航线网络中的KSP问题上比Yen算法更加高效。该算法可为进一步求解国际航线网络或空铁联运网络中的K条联程路径优化问题提供依据。
参考文献：
[1]LU F. Shortest path algorithms： taxonomy and advance in research [J]. Acta Geodaetica et Cartographica Sinica， 2001， 30（3）： 269-275. （陆锋. 最短路径算法：分类体系与研究进展[J].测绘学报，2001，30（3）：269-275.）
[2]GODSIL C， ROYEL G F. Algebraic graph theory [M]. Berlin： SpringerVerlag， 2004.
[3]DIAS L C， CLIMACO J N. Shortest path problems with partial information： models and algorithms for detecting dominance [J]. European Journal of Operation Research， 2000， 121（1）：16-31.
[4]BAI Y， HU P， XIA L， et al. A kthshortest path algorithm based on k-1 shortest paths [J]. Geomatics and Information Science of Wuhan University， 2009， 34（4）：492-494. （白轶多，胡鹏，夏兰芳，等.关于k次短路径问题的分析与求解[J].武汉大学学报，2009，34（4）：492-494.）
[5]HOFFMAN W， PAVLEY R. A method of solution of the Nth best path problem [J]. Journal of the ACM， 1959， 6（4）： 506-514.
[6]WANG Z， HAN W， LI Y. Shortest path problem with multiple shortest paths [J]. Journal of Harbin Institute of Technology， 2010， 42（9）： 1428-1431. （王志坚，韩伟一，李一军.具有多条最短路径的最短路问题[J].哈尔滨工业大学学报，2010，42（9）：1428-1431.）
[7]KANG T， ZHANG X， WANG Z， et al. Algorithm for shortest path of multiobjectives based on k short path algorithm [J]. Journal of Changzhou Institute of Technology， 2011， 24（3）： 25-28. （康太平，张晓刚，王宗峰，等.基于k短路径算法的多目标最短路径算法[J].常州工学院学报，2011，24（3）：25-28.）
[8]MA X， LIU Q. A shuffled frog leaping algorithm for kshortest paths problem[J]. Information and Control， 2011， 40（5）： 614-618. （马炫，刘庆.求解k条最短路径问题的混合蛙跳算法[J].信息与控制，2011，40（5）：614-618.）
[9]GAO S， LU F. The kth shortest path algorithms： accuracy and efficiency evaluation [J]. Journal of Image and Graphics， 2009， 14（8）： 1677-1683. （高松，陆峰.K则最短路径算法效率与精度评估[J].中国图象图形学报，2009，14（8）：1677-1683.）
[10]YEN J Y. Finding the K shortest loopless paths in a network [J]. Management Science， 1971， 17（11）： 712-716.
[11]MARTINS E Q V， PASCOAL M M B， SANTOS J L E. A new algorithm for ranking loopless paths [R]. Coimbra， Portugal： Center for Informatics and Systems of the University of Coimbra， 1997.
[12]MARTINS E Q V， PASCOAL M M B. A new implementation of Yens ranking loopless paths algorithm [J]. Quarterly Journal of the Belgian， French， Italian Opertaions Research Societies， 2000， 1（2）：121-134.
[13]HERSHBERGER J， MAXEL M， SUR S. Finding the K shortest simple paths： a new algorithm and its implementation [J]. ACM Transactions on Algorithms， 2007， 3（4）： 45-es.
[14]NILSSON N J. Artificial intelligence： a new synthesis [M]. San Francisco： Morgan Kaufmann Publishers Inc.， 2000.