Historical traffic-tolerant paths in road networks

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.

• Publication year

  2014

• Venue

  SIGSPATIAL/GIS

• Publication date

  2014-11-04

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1145/2666310.2666483
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Shortest path and distance queries on road networks: towards bridging theory and practice

  2013cited by this paper
• A continuous query system for dynamic route planning

  2011influential reference
• Online Computation of Fastest Path in Time-Dependent Spatial Networks

  2011cited by this paper
• Limits of Predictability in Human Mobility

  2010cited by this paper
• Understanding individual human mobility patterns

  2008cited by this paper
• Finding Fastest Paths on A Road Network with Speed Patterns

  2006cited by this paper

• Mobile user identification based on road networks and multiple distance measures

  2023cites this paper
• A novel trajectory similarity measurement method based on node‐sequence hierarchical digraph

  2023cites this paper
• User Identification across Asynchronous Mobility Trajectories

  2019cites this paper
• Discovering historic traffic-tolerant paths in road networks

  2016cites this paper
• Automatic user identification method across heterogeneous mobility data sources

  2016cites this paper
• Integrating Traffic Data Stream with Public Route Planning Algorithm and Personalizing it for the End Users

  2015cites this paper