MINIMUM WEIGHT PATHS IN TIME-DEPENDENT NETWORKS

We investigate the minimum weight path problem in networks whose link weights and link delays are both functions of time. We demonstrate that, in general, there exist cases in which no finite path is optimal leading us to define an infinite path (naturally, containing loops) in such a way that the minimum weight problem always has a solution. We also characterize the structure of an infinite optimal path. In many practical cases, finite optimal paths do exist. We formulate a criterion that guarantees the existence of a finite optimal path and develop an algorithm to find such a path. Some special cases, e.g., optimal loopless paths, are also discussed.