Publication Type

Conference Proceeding Article

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

Research Areas

Data Management and Analytics

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

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://dx.doi.org/10.1145/2666310.2666483

Share

COinS