Shortest paths in time-schedule networks

The time-constrained shortest path problem is an important generalization of the shortest path problem and has attracted much research interest in recent years. The time window is a common form of time constraint discussed in the literature, which requires that a node can be visited only in a specified time interval. In this paper, we introduce a new time constraint, which consists of a list of pre-specified departure times for each node and requires that departure from a node can take place only at one of these departure times. For a network under this time constraint, a set of problems are studied, including minimization of total time, minimization of total waiting time, minimization of total cost subject to a total time constraint, minimization of total time subject to a total cost constraint, and minimization of a weighted sum of total cost and total time. In addition, possible extensions to multiple criteria problems and additional constrained problems are discussed.