Improvement and simulation of K-shortest-paths algorithm in international flight route network
Hu Xi · Journal of Computer Applications · 2014
K-Shortest-Paths( KSP) problem is the optimization issue in international flight route network. With the analysis on the international flight route network and KSP algorithm, the typical Yen algorithm solve KSP problem was investigated. To resolve the problem that Yen algorithm occupied much time in solving the candidate paths, an improved Yen algorithm was proposed. The improved Yen algorithm was set up by using the heuristic strategy of A*algorithm, which reduced the time to generate candidate paths, thereby, the search efficiency was improved and the search scale was reduced. The simulation results of international flight route network example show that the improved Yen algorithm can quickly solve KSP problem in international flight route network. Compared with the Yen algorithm, the efficiency of the proposed algorithm is increased by 75. 19%, so it can provide decision support for international flight route optimization.