Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
11-2014
Abstract
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.
Keywords
Road networks, Road traffic
Discipline
Databases and Information Systems | Transportation
Publication
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems: 4-7 November 2014, 2014, Dallas
First Page
477
Last Page
480
ISBN
9781450331319
Identifier
10.1145/2666310.2666483
Publisher
ACM
City or Country
New York
Citation
LI, Pui Hang; YIU, Man Lung; and MOURATIDIS, Kyriakos.
Historical Traffic-Tolerant Paths in Road Networks. (2014). SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems: 4-7 November 2014, 2014, Dallas. 477-480.
Available at: https://ink.library.smu.edu.sg/sis_research/2327
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://dx.doi.org/10.1145/2666310.2666483