5,832 research outputs found
Fast Computation of Shortest Smooth Paths and Uniformly Bounded Stretch with Lazy RPHAST
No full textWe study the shortest smooth path problem (SSPP), which is motivated by traffic-aware routing in road networks. The goal is to compute the fastest route according to the current traffic situation while avoiding undesired detours, such as briefly using a parking area to bypass a jammed highway. Detours are prevented by limiting the uniformly bounded stretch (UBS) with respect to a second weight function which disregards the traffic situation. The UBS is a path quality metric which measures the maximum relative length of detours on a path. In this paper, we settle the complexity of the SSPP and show that it is strongly NP-complete. We then present practical algorithms to solve the problem on continental-sized road networks both heuristically and exactly. A crucial building block of these algorithms is the UBS evaluation. We propose a novel algorithm to compute the UBS with only a few shortest path computations on typical paths. All our algorithms utilize Lazy RPHAST, a recently proposed technique to incrementally compute distances from many vertices towards a common target. An extensive evaluation shows that our algorithms outperform competing SSPP algorithms by up to two orders of magnitude and that our new UBS algorithm is the first to consistently compute exact UBS values in a matter of milliseconds
A Fast and Tight Heuristic for A* in Road Networks
No full textWe study exact, efficient and practical algorithms for route planning in large road networks. Routing applications often require integrating the current traffic situation, planning ahead with traffic predictions for the future, respecting forbidden turns, and many other features depending on the exact application. While Dijkstra’s algorithm can be used to solve these problems, it is too slow for many applications. A* is a classical approach to accelerate Dijkstra’s algorithm. A* can support many extended scenarios without much additional implementation complexity. However, A*’s performance depends on the availability of a good heuristic that estimates distances. Computing tight distance estimates is a challenge on its own. On road networks, shortest paths can also be quickly computed using hierarchical speedup techniques. They achieve speed and exactness but sacrifice A*’s flexibility. Extending them to certain practical applications can be hard. In this paper, we present an algorithm to efficiently extract distance estimates for A* from Contraction Hierarchies (CH), a hierarchical technique. We call our heuristic CH-Potentials. Our approach allows decoupling the supported extensions from the hierarchical speed-up technique. Additionally, we describe A* optimizations to accelerate the processing of low degree nodes, which often occur in road networks
Combining Predicted and Live Traffic with Time-Dependent A* Potentials
No full textWe study efficient and exact shortest path algorithms for routing on road
networks with realistic traffic data. For navigation applications, both current
(i.e., live) traffic events and predictions of future traffic flows play an
important role in routing. While preprocessing-based speedup techniques have
been employed successfully to both settings individually, a combined model
poses significant challenges. Supporting predicted traffic typically requires
expensive preprocessing while live traffic requires fast updates for regular
adjustments. We propose an A*-based solution to this problem. By generalizing
A* potentials to time dependency, i.e. the estimate of the distance from a
vertex to the target also depends on the time of day when the vertex is
visited, we achieve significantly faster query times than previously possible.
Our evaluation shows that our approach enables interactive query times on
continental-sized road networks while allowing live traffic updates within a
fraction of a minute. We achieve a speedup of at least two orders of magnitude
over Dijkstra's algorithm and up to one order of magnitude over
state-of-the-art time-independent A* potentials.Comment: 19 pages, 5 figures. Full version of ESA22 pape
Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks
No full textWe study the problem of computing 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 either 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 30 times smaller indexes than competing approaches
Do dolphins benefit from nonlinear mathematics when processing their sonar returns?
No full textAn interview with author Tim Leighton about the paper
Opportunities for linking young surveyors across professional surveying member organisations and FIG
No full textCustomizable Contraction Hierarchies with Turn Costs
No full textWe incorporate turn restrictions and turn costs into the route planning algorithm customizable contraction hierarchies (CCH). There are two common ways to represent turn costs and restrictions. The edge-based model expands the network so that road segments become vertices and allowed turns become edges. The compact model keeps intersections as vertices, but associates a turn table with each vertex. Although CCH can be used as is on the edge-based model, the performance of preprocessing and customization is severely affected. While the expanded network is only three times larger, both preprocessing and customization time increase by up to an order of magnitude. In this work, we carefully engineer CCH to exploit different properties of the expanded graph. We reduce the increase in customization time from up to an order of magnitude to a factor of about 3. The increase in preprocessing time is reduced even further. Moreover, we present a CCH variant that works on the compact model, and show that it performs worse than the variant on the edge-based model. Surprisingly, the variant on the edge-based model even uses less space than the one on the compact model, although the compact model was developed to keep the space requirement low
Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas
No full textWe study the problem of planning routes in road networks when certain streets or areas are closed at certain times. For heavy vehicles, such areas may be very large since many European countries impose temporary driving bans during the night or on weekends. In this setting, feasible routes may require waiting at parking areas, and several feasible routes with different trade-offs between waiting and driving detours around closed areas may exist. We propose a novel model in which driving and waiting are assigned abstract costs, and waiting costs are location-dependent to reflect the different quality of the parking areas. Our goal is to find Pareto-optimal routes with regards to arrival time at the destination and total cost. We investigate the complexity of the model and determine a necessary constraint on the cost parameters such that the problem is solvable in polynomial time. We present a thoroughly engineered implementation and perform experiments on a production-grade real world data set. The experiments show that our implementation can answer realistic queries in around a second or less which makes it feasible for practical application
Tim Di Muzio on 'Sabotage'
No full textIn a series of essays published in 2013 and 2014 on capitaspower.com, political economist Tim Di Muzio explored the concept of ‘sabotage’ as it applies to capitalist power. I recently rediscovered these essays and was so impressed by them that I have reposted them here as a single piece.
About the author: Tim Di Muzio is a researcher at the University of Wollongong. He is the author of numerous books, including Debt as power, Carbon capitalism, and The 1% and the Rest of us
1996-1997 Tim Gautreaux
No full textTim Gautreaux is the author of three novels and two earlier short story collections. His work has appeared in The New Yorker, The Best American Short Stories, The Atlantic, Harper’s, and GQ. After teaching for thirty years at Southeastern Louisiana University, he now lives, with his wife, in Chattanooga, Tennessee. (Photo credit: Randy Bergeron)https://egrove.olemiss.edu/grisham_res/1023/thumbnail.jp
- …
