Article ID: | iaor2001455 |
Country: | Netherlands |
Volume: | 121 |
Issue: | 1 |
Start Page Number: | 32 |
End Page Number: | 39 |
Publication Date: | Feb 2000 |
Journal: | European Journal of Operational Research |
Authors: | Sung Kiseok, Bell Michael G.H., Park Soondal, Seong Myeongki |
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.