Minimum time paths in a network with mixed time constraints

The time-constrained shortest path problem is an important generalization of the shortest path problem and has attracted much research interest in recent years. In a recent paper, a new time constraint, namely time-schedule constraint, is introduced. This time constraint assumes that every node in the network has a list of pre-specified departure times and requires that departure from a node take place only at one of these departure times. Therefore, when a time-schedule constraint is considered, the total time in a network includes traveling time and waiting time. In this paper, we consider a network consisting of two types of nodes in terms of their time constraints. The first type of nodes are subject to time-schedule constraints, but the second type is not. For such a network, a set of minimum time (shortest) path problems is studied, including minimization of total time, minimization of total time subject to a total traveling time constraint, minimization of total traveling time subject to a total time constraint and minimization of a weighted sum of total time and total traveling time.