A simplification of the double-sweep algorithm to solve the k-shortest path problem |
| |
Authors: | K. A. Rink E. Y. Rodin V. Sundarapandian |
| |
Affiliation: | Center for Optimization and Semantic Control Department of Systems Science and Mathematics Campus Box 1040, Washington University, St. Louis, MO 63130-4899, U.S.A. |
| |
Abstract: | In this paper, we define the k-shortest path problem, which will be used to model the problem of routing aircraft through a network of airfields. This problem finds the optimal alternative routes from one or more origins to one or more destinations. We solve this problem using the double-sweep algorithm. We present a simplification to the double-sweep algorithm, and show that this simplification reduces the computational complexity of the algorithm by a factor of k. We prove that the simplified double-sweep algorithm converges. Finally, we demonstrate this algorithm on a small airlift network. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|