Research on Fast KCSP Algorithms for Searching Connecting Paths in Airline Networks

Jian Fu Li; Tie Jun Li

doi:10.4028/www.scientific.net/AMM.505-506.1005

Paper Titles

The Influence of Future Vehicle Safety Network Impact on Traffic Flow
p.985

Research on Quantification of Airline SMS Security Risk Assessment
p.990

Building Topological Structure of the Post-Disaster Road Network Based MapX
p.995

Flow-Density Relationship for Discontinuous Flow on Urban Street Network
p.999

Research on Fast KCSP Algorithms for Searching Connecting Paths in Airline Networks
p.1005

Study on Performance Measurement of Beijing Urban Expressway Based on Microwave Data
p.1014

Prediction of Urban Rail Transit Sectional Passenger Flow Based on Elman Neural Network
p.1023

A Study of an Adaptive Two-Phrase Signal Control Strategy for Resolving Conflicting Transit Signal Priority Calls
p.1028

Pedestrian Evacuation with a Improved Dynamic Parameters Model
p.1037

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 505-506Research on Fast KCSP Algorithms for Searching...

Research on Fast KCSP Algorithms for Searching Connecting Paths in Airline Networks

Abstract:

With the rapid development of the civil aviation industry in the world, airline networks become increasingly complex and large, which provide more choices for passengers. To search in airline networks for better connecting paths, it is very time-consuming by existing general K Constrained Shortest Paths (KCSP) algorithms. According to that the acceptable transfer times is generally not more than 3, combined with the structure characteristics of the Yen algorithm, a fast algorithm named as KCSP_Yen is proposed for searching connecting paths in airline networks. At the same time, based on the bounded breadth-first search and A* search, two fast KCSP algorithms are proposed. Finally, the three algorithms are test through experiments on the world airline network.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 505-506)

Pages:

1005-1013

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.505-506.1005

Citation:

Cite this paper

Online since:

January 2014

Authors:

Jian Fu Li, Tie Jun Li

Keywords:

Airline Networks, Connecting Paths, KCSP, Search, Yen

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] A. Goel, D. Kataria, D. Logothetis and K. G. Ramakrishnan. An Efficient Algorithm for Constraint-based Routing in Data Networks. Technical Report, BL0112120-990616-11TM, Bell Laboratories /Lucent Technologies, (1999).

Google Scholar

[2] Yen J Y. Finding the k shortest loopless paths in a network[J]．Management Science, 1971, 17(11): 712-716.

DOI: 10.1287/mnsc.17.11.712

Google Scholar

[3] E. Q. V. Martins, M. M. B. Pascoal, and J. L. E. Santos. Deviation algorithms for ranking shortest paths[J]. The International Journal of Foundations of Computer Science, 1999, 10(3): 247-263.

DOI: 10.1142/s0129054199000186

Google Scholar

[4] Climaco J, Craveirinha J, Pascoal M. A bicriterion approach for routing problems in multimedia networks[J]．Networks, 2003, 41(4): 206-220.

DOI: 10.1002/net.10073

Google Scholar

[5] Ning S．K constrained shortest path problem[J]．IEEE Transactions on Automation Science and Engineering, 2010, 1(7): 15-23.

Google Scholar

[6] R. Dechter, N. Flerova, R. Marinescu. Search Algorithms for M Best Solutions for Graphical Models. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence[C], 2012, 1895-(1901).

DOI: 10.1609/aaai.v26i1.8405

Google Scholar

[7] H. Aljazzar, S. Leue. K*: a heuristic search algorithm for finding the K shortest paths. Artificial Intelligence[J], 2011, 175 : 2129-2154.

DOI: 10.1016/j.artint.2011.07.003

Google Scholar

[8] Y. Kobayashi, A. Kishimoto and O. Watanabe. Evaluations of Hash Distributed A* in Optimal Sequence Alignment[C]. Proceedings of the Twenty- Second International Joint Conference on Artificial Intelligence, 2011, 585-590.

Google Scholar

[9] Liu G，Ramakrishnan K G．A* Prune: an algorithm for finding k shortest paths subject to multiple constraints[C]. Proceedings of the Conference on Computer Communications, 2001, 2: 743-749.

DOI: 10.1109/infcom.2001.916263

Google Scholar