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.