Theories and algorithms of time-dependent shortest path in GIS

摘要

Time-dependent shortest path problem arise in a variety applications, e.g., traffic navigation, dynamic traffic assignment, network control. Based on the road network, which the travel time of each link dependents on the time interval, we suggest a new time-dependent network model, analyse the mathematics features of first-in-first-out (FIFO) link and conclude FIFO character of the road network, study and prove the theories of shortest time path algorithm in FIFO network systematically. The “forward” and “backward” shortest time path algorithms are designed and realized also in this paper.