The first K minimum cost paths in a time-schedule network

The time-constrained shortest path problem is an important generalisation o f the classical shortest path problem and in recent years has attracted muc h research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure fr om a node may take place only at one of these departure times. The objectiv e of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is develop ed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.