Publication Type

Journal Article

Publication Date

1-2017

Abstract

Historic traffic information is valuable in transportation analysis and planning, e.g., evaluating the reliability of routes for representative source-destination pairs. Also, it can be utilized to provide efficient and effective route-search services. In view of these applications, we propose the k traffic-tolerant paths (TTP) problem on road networks, which takes a source-destination pair and historic traffic information as input, and returns k paths that minimize the aggregate (historic) travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to find. First, we propose an exact algorithm with effective pruning rules to reduce the search time. Second, we develop an anytime heuristic algorithm that makes ‘best-effort’ to find a low-cost solution within a given time limit. Extensive experiments on real and synthetic traffic data demonstrate the effectiveness of TTP and the efficiency of our proposed algorithms.

Keywords

Road networks, Road traffic

Discipline

Theory and Algorithms

Research Areas

Data Management and Analytics

Publication

GeoInformatica

Volume

21

Issue

1

First Page

1

Last Page

32

ISSN

1384-6175

Identifier

10.1007/s10707-016-0265-y

Publisher

Springer Verlag (Germany)

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://doi.org/10.1007/s10707-016-0265-y

Share

COinS