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 lime-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 lime 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. (C) 1998 Elsevier Science Ltd. All rights reserved.
