Abstract
This study investigates the online route planning problem in time-dependent traffic networks. Given a road network, the problem involves planning a dynamic route as short as possible from a source to a destination, but possibly discovering online (real-time) traffic congestions or accidents, which may cause long delays. From a practical perspective, the problem discusses the shortestpath query problem with a set of dynamic changes that are subject to online traffic conditions. In comparison with prior work, we design efficient algorithms for solving this problem without the assumption that the given time-dependent networks satisfy the FIFO (First-In-First-Out) property. Moreover, we conduct empirical studies with high-density time-series traffic data and exploit data structures to significantly reduce computation loads. In fact, the size of the resulting sets of preprocessed data structures might be too heavy to be practical. Our approaches can immediately respond to online traffic changes, but in small real-world instances. We also propose some heuristics to speed up computation, and the experiments demonstrate the effectiveness of the proposed algorithms. In particular, the travel cost of the derived online near-shortest routes can be shown very close to that of the static (offline) time-dependent shortest paths in hindsight, where all traffic changes are known a priori.