Historical Traffic-Tolerant Paths in Road Networks

• Main Authors: LI, Pui Hang, YIU, Man Lung, MOURATIDIS, Kyriakos
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2014
• Subjects: Road networks; Road traffic; Databases and Information Systems; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/2327; https://ink.library.smu.edu.sg/context/sis_research/article/3327/viewcontent/Historical_Traffic_Tolerant_Paths_in_Road_Networks.pdf
• Institution: Singapore Management University

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 the efficiency of our proposed algorithms.