Finding the first K shortest paths in a time-window network

摘要

The time-constrained shortest path problem is an important generalization of the classical shortest path problem and has attracted much research interest in recent years. We consider a time-window network, where every node in the network has a list of pre-specified windows and departure from a node may take place only in these window periods. The objective of this paper is to find the first K shortest paths in a time-window network. An algorithm of time complexity of O(Kr|V|~3) is developed to find the first K shortest paths, where |V| is the numbers of nodes in the network and r represents the maximum number of windows associated with a node.