Loading...
Please wait, while we are loading the content...
Similar Documents
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks
| Content Provider | MDPI |
|---|---|
| Author | Strasser, Ben Wagner, Dorothea Zeitz, Tim |
| Copyright Year | 2021 |
| Description | We study the problem of quickly computing point-to-point shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have large index size, slow query running times or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 38 times smaller indexes than competing approaches. |
| Starting Page | 90 |
| e-ISSN | 19994893 |
| DOI | 10.3390/a14030090 |
| Journal | Algorithms |
| Issue Number | 3 |
| Volume Number | 14 |
| Language | English |
| Publisher | MDPI |
| Publisher Date | 2021-03-16 |
| Access Restriction | Open |
| Subject Keyword | Algorithms Transportation Transportation Science and Technology Realistic Road Networks Time-dependent Route Planning Shortest Paths |
| Content Type | Text |
| Resource Type | Article |
