Abstract#R##N#Real-word road networks are typically time-dependent, but research on time-dependent shortest paths (TDSPs) is not as rich as that on static shortest paths (SSPs). For large networks, some speed-up techniques are usually applied to compute SSPs. Unfortunately, many of these techniques are impractical for TDSPs, especially the techniques requiring a precomputation because the number of time instances may be incredibly large or even infinite. Therefore, this study introduced a new TDSP technique that is able to overcome the issue of infinite time instances by utilizing network geometry alone for the pre-computation, namely the Minimum Step Linkage (MSL) algorithm. It works with a data model called Cumulative Cost Model (CCM). The theoretical concepts of the new data model and algorithm are described, and its performances were tested and compared with existing algorithms through a series of simulations.
['Vini Indriasari', 'Denis J. Dean']
The Minimum Step Linkage Algorithm and Cumulative Cost Model for Time-Dependent Shortest Paths.