Finding the K shortest paths in a time-schedule network with constraints on arcs

We study a new variant of the time-constrained shortest path problem (TCSPP), that is, the K shortest paths problem in a time-schedule network with constraints on arcs. In such networks, each arc has a list of pre-specified departure times, and traversal along the arc can only take place at one of those departure times. We develop a solution algorithm that finds the K shortest looping paths in O(mlog(nr)+Kmr2η) time, where n is the number of nodes, m is the number of arcs, r is the maximum number of departure times on an arc, and η is the maximum in-degree of a node. Computational experiments show that our algorithm outperforms existing ones adapted to solve the same problem.