A simplification of the double-sweep algorithm to solve the k-shortest path problem

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 o ne or more destinations. We solve this problem using the double-sweep algor ithm. We present a simplification to the double-sweep algorithm, and show t hat this simplification reduces the computational complexity of the algorit hm by a factor of k. We prove that the simplified double-sweep algorithm co nverges. Finally, we demonstrate this algorithm on a small airlift network. (C) 2000 Elsevier Science Ltd. All rights reserved.