Shortest paths in a network with time-dependent flow speeds

The model and solution of the shortest path problem on time-dependent networks, where the travel time of each Link depends on the time interval, violate the non-passing property of real phenomena. Calculating the solution of the problem needs much more computation and memory than the general shortest path problem. Here we suggest a new model for time-dependent networks where the flow speed of each link depends on the time interval, and a solution algorithm modified from Dijkstra's label setting algorithm. We present numerical examples and computational experiments showing that the solution of our model satisfies the non-passing property and is stable to the variance of the time interval length. Solving the shortest path of our model needs just a little more computation and memory than the general shortest path problem. (C) 2000 Elsevier Science B.V. All rights reserved.