Physical Sciences and Mathematics Commons^™

Historical Traffic-Tolerant Paths In Road Networks, Pui Hang Li, Man Lung Yiu, Kyriakos Mouratidis

Research Collection School Of Computing and Information Systems

Historical traffic information is valuable for transportation analysis and planning, as well as for route search services. In view of these applications, we propose the k traffic-tolerant paths problem (TTP) on road networks, which takes a source-destination pair and historical traffic information as input, and returns k paths that minimize the aggregate (historical) travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to compute. We propose an exact algorithm and a heuristic algorithm for this problem. Experiments on real traffic data demonstrate the effectiveness of TTP paths and …