MetaTOC stay on top of your field, easily

The Minimum Step Linkage Algorithm and Cumulative Cost Model for Time‐Dependent Shortest Paths


Transactions in GIS

Published online on


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.