Search

Stochastic route planning is a hard problem, since it deals with uncertain edge weights, usually modeled as probability distributions. Stochastic shortest path queries are very expensive, as they must compute convolutions of edge weight distributions, whose representations can have a major impact on query costs. Effective speedup techniques for shortest path queries exist for deterministic edge weights, but their extensions to stochastic settings have had limited success, and real-time stochastic routing queries remain beyond reach. We introduce the tiering technique for Contraction and Edge Hierarchies (CHs and EHs) to address this challenge. We divide the hierarchy into tiers, and represent edge weights in each tier in ways that permit effective tradeoffs between accuracy, convolution costs, and space use. We show how to use Gaussians to approximate histograms, and bound errors using the KL divergence and Hellinger distance measures. We develop Uncertain Contraction Hierarchies (UCHs) and Uncertain Edge Hierarchies (UEHs) using these methods, and show that they improve both CH and EH performance for three different stochastic query types: probabilistic budget routes, non-dominated routes, and routes to minimize the mean-risk objective. We evaluate our methods using real-world data from Mapbox Traffic Data for a section of Los Angeles. Finally, our results show that query times for EHs can be competitive with CHs for stochastic edge weights, contrary to current belief.

Problem pronalaska najkraćeg puta u grafu široko je primjenjiv u stvarnom svijetu. Mnoge se stvari matematički modeliraju pomoću grafova čime se stvara potreba za što boljim i bržim algoritmima za rješenje ovog problema. Primjeri su razne vrste prometnica i situacija u prometu, internetske mreže, posebne vrste baza podataka te razni drugi. Prvi dio rada posvećen je klasičnim algoritmima koji ne zahtijevaju prethodnu obradu podataka koju nazivamo predprocesiranje. Opisuju se Dijkstrin algoritam i A\( ^*\) algoritam te njihove dvosmjerne verzije. U novije vrijeme ključ ubrzanja pronalaska najkraćeg puta u algoritmima leži u fazi predprocesiranja. Algoritam provodeći potrebne postupke prikupi informacije koje koristi pri ubrzanju faze traženja puta. Detaljno opisujemo dva takva algoritma: Contraction Hierarchies i Landmark A\( ^*\). Contraction Hierarchies algoritam na prikladan način odreduje hijerarhiju vrhova, te u početni graf dodaje nove bridove zvane prečaci. Pronalazak najkraćeg puta provodi se dvosmjernim Dijkstrinim pretraživanjem u modificiranom grafu gdje obje pretrage pretražuju samo bridove koje vode do vrhova veće hijerarhije. Landmark A\( ^*\) algoritam temelji se na A\( ^*\) pretraživanju uz heurističku funkciju procjene udaljenosti dobivenu fazom predprocesiranja. Uvode se vrhovi orijentiri za koje je poznata udaljenost od i do svih preostalih vrhova. Procjena udaljenosti dobije se po uzoru na nejednakost trokuta. U zadnjem dijelu provodimo usporedbu promatranih algoritama te iznosimo neke implementacijske pojedinosti. Rezultati su dobiveni na podacima stvarnih cestovnih prometnica. Contraction Hierarchies nadmašuje Landmark A\( ^*\) algoritam u brzini pronalaska najkraćeg puta, no uz veće vrijeme predprocesiranja. Ovisno o dozvoljenom vremenu i raspoloživoj memoriji kod pripremne faze, bira se prikladniji algoritam. Oba algoritma su značajno brža u usporedbi s klasičnim Dijkstrinim pretraživanjem. The problem of finding the shortest path in a graph is widely applicable in the real world. Many things are mathematically modeled using graphs, which creates the need for better and faster algorithms to solve this problem. Examples are various types of roads and traffic situations, Internet networks, special types of databases, and various others. The first part of this thesis is dedicated to classical algorithms that do not require preprocessing. The Dijkstra’s algorithm and the A\( ^*\) algorithm, and their two-way versions are described. More recently, the key to accelerating finding the shortest path in algorithms lies in the preprocessing phase. By performing the necessary procedures, the algorithm collects the information it uses to speed up the path search phase. We describe two such algorithms in detail: Contraction Hierarchies and Landmark A\( ^*\). The Contraction Hierarchies algorithm appropriately determines the hierarchy of vertices and adds new edges called shortcuts to the initial graph. The shortest path finding is performed by a two-way Dijkstra’s search in a modified graph where both searches search only the edges leading to the tops of the larger hierarchy. The Landmark A\( ^*\) algorithm is based on A\( ^*\) search with a heuristic distance estimation function obtained by the preprocessing phase. We introduce the landmark nodes for which the distance from and to all remaining nodes is known. The estimate of the distance is obtained based on the triangle inequality. In the last part, we compare the observed algorithms and present some implementation details. The results were obtained on the basis of actual road network data. Contraction Hierarchies outperforms the Landmark A\( ^*\) algorithm in the speed of finding the shortest path, but with a longer preprocessing time. Depending on the time allowed and the available memory during the preparation phase, a more suitable algorithm is chosen. Both algorithms are significantly faster compared to the classic Dijkstra’s search.

In many algorithms for traffic assignment, the most time-consuming step is shortest path search between all O–D pairs. Almost unnoticed by the transport modeling community, there has been an enormous amount of research on acceleration techniques for the shortest path problem in road networks in the past decade. These techniques usually divide the problem into a relatively expensive preprocessing phase and a significantly accelerated search phase. In this paper, the recently developed customizable contraction hierarchies are used for both shortest path search and network loading in the bi-conjugate Frank–Wolfe algorithm. For the largest test network, this approach achieves a speedup by a factor of 42 compared with a straightforward implementation of Dijkstra’s algorithm.

When an emergency occurs in the city, a large area of road congestion usually occurs. Therefore, it is particularly important to provide an effective emergency path planning strategy for vehicles. However, existing emergency path planning methods do not take into account the connectivity characteristics of the road network and commuting capacity. For this purpose, a Grid Map Emergency Path Planning (GMEPP) framework based on a novel model Grid Road Network (GRN) is designed in this paper. First, the road network data is divided into grids under equal spacing bands, and the roads data divided into different grids and use the commuting capacity of each road as the weight of each edge in the grid. Then a Grid PageRank (GPR) algorithm will be introduced, the output value of this methodology is calculated based on the capacity and number of connected edges of all vertices pointed by the external grid in each grid. The higher value of the grid will be recommended to users first when the path is planning. According to the GRN model, an improved Bidirectional Dijkstra will be applied to query the shortest path between two points, which is called Gird Bidirectional Dijkstra (GBD). At last, GMEPP uses Reverse Contraction Hierarchies (RCH) and Multiple Reverse Contraction Hierarchies (MRCH) originality methodologies based on intersection type to speed up the query algorithm GBD. To compare the efficiency of the proposed method, this paper conducted extensive experiments to verify. The results of the test showed that the Gird Bidirectional Dijkstra Multiple Reverse Contraction Hierarchies (GBD-MRCH) is better than other methods in different grid distributions.

Computing the shortest path between two vertices is a fundamental problem in road networks that is applied in a wide variety of applications. To support efficient shortest path query processing, a plethora of index-based methods have been proposed in the literature, but few of them can support dynamic road networks commonly encountered in practice, as their corresponding index structures cannot be efficiently maintained when the input road network is dynamically updated. Motivated by this, we study the shortest path index maintenance problem on dynamic road networks in this paper. We adopt Contraction Hierarchies (CH) as our underlying shortest path computation method because of its outstanding overall performance in pre-processing time, space cost, and query processing time and aim to design efficient algorithms to maintain the index structure, shortcut index , of CH when the input road network is dynamically updated. To achieve this goal, we propose a shortcut-centric paradigm focusing on exploring a small number of shortcuts to maintain the shortcut index. Following this paradigm, we design an auxiliary data structure named SS-Graph and propose a shortcut weight propagation mechanism based on the SS-Graph. With them, we devise efficient algorithms to maintain the shortcut index in the streaming update and batch update scenarios with non-trivial theoretical guarantees. We experimentally evaluate our algorithms on real road networks and the results demonstrate that our approach achieves 2--3 orders of magnitude speedup compared to the state-of-the-art algorithm for the streaming update.

Given an urban road network and a set of origin-destination pairs, the traffic assignment problem asks for the traffic flow on each road segment. Common solution algorithms require a large number of shortest-path computations. In this article, we significantly accelerate the computation of flow patterns, enabling interactive transportation and urban planning applications. We achieve this by building a traffic assignment procedure upon customizable contraction hierarchies (CCH), revisiting and carefully engineering CCH customization and queries, and adapting CCH to compute batched point-to-point shortest paths. Although motivated by the traffic assignment problem, our optimizations apply to CCH in general. In contrast to previous work, our evaluation uses real-world production data for all parts of the input. On a metropolitan area encompassing about 2.7 million inhabitants, we decrease the flow-pattern computation for a typical 1-hour morning peak (a quarter million trips) from 90.9 to 14.1 seconds on one core and 2.4 seconds on a 16-core machine. This represents a speedup of 37 over the state of the art and more than three orders of magnitude over the Dijkstra-based baseline.

We study the problem of computing paths that minimize energy consumption of a battery electric vehicle. For that, we must cope with specific properties, such as regenerative braking and constraints imposed by the battery capacity. These restrictions can be captured by profiles, which are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for battery electric vehicles. In this work, we prove that profiles have linear complexity. We examine different variants of Dijkstra’s algorithm to compute energy-optimal paths or profiles. Further, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. We also discuss a heuristic variant that is easy to implement, and carefully integrate it with the well-known Contraction Hierarchies algorithm and A* search. Finally, we propose a practical approach that enables computation of energy-optimal routes within milliseconds after fast (metric-dependent) preprocessing of the whole network. This enables flexible updates due to, e. g., weather forecasts or refinements of the consumption model. Practicality of our approaches is demonstrated in a comprehensive experimental study on realistic, large-scale road networks.

We present a holistic approach for pedestrian routing that allows computing shortest paths that may have indoor and outdoor sections. Such routes arise, for example, when the destination is not just an address but a specific store in a large mall, or when one needs to get to a certain track at a large train station. Currently, map services as Google Maps or OSRM do not offer such functionality. We identify and overcome three main challenges for answering such complex route planning queries: (i) Pedestrian routing requires fine-grained data, as the location of stairs and elevators, building dventrances, building footprints, and elevation/level information. A single missing staircase can change the length of the computed path severely. (ii) Indoor routing has to be integrated carefully into classical path planning to allow the computation of sensible routes that may enter and exit buildings. (iii) Given the large amount of data to be considered in a query, acceleration techniques need to be applied in order to achieve interactive query times. Retrieving barrier-free routes for wheelchairs is also our important use case. published

Over the past few years, several studies have considered the problem of Electric Vehicle Path Planning with intermediate recharge (EVPP-R) that consists of finding the shortest path between two given points by traveling through one or many charging stations, without exceeding the vehicle’s range. Unfortunately, the exact solution to this problem has a high computational cost. Therefore, speedup techniques are generally necessary (e.g., contraction hierarchies). In this paper, we propose and evaluate a new fast and intuitive graph clustering technique, which is applied on a real map with charging station data. We show that by grouping nearby stations, we can reduce the number of stations considered by a factor of 13 and increase the speed of computation by a factor of 35, while having a very limited trade-off increase, of less than \(1\%\), on the average journey duration time.

Efficient GPU single-source shortest-path (SSSP) queries of road network graphs can be realized by a technique called PHAST (Delling et al.) in which the graph is contracted (pre-processed using Geisberger's Contraction Hierarchies) once and the resulting contracted graph is queried as needed. PHAST accommodates GPUs' parallelism requirements well, resulting in efficient queries. For situations in which a graph is not available well in advance or changes frequently contraction time itself becomes significant. Karimi et al. recently described a GPU contraction technique, CU-CH, which significantly reduces the contraction time of small-to medium-sized graphs, reporting a speedup of over 20× on an NVidia P100 GPU. However CU-CH realizes little speedup on larger graphs, such as DIMACS’ USA and W. Europe graphs. The obstacle to faster contraction of larger graphs is the frequently performed witness path search (WPS). A WPS for a node determines which shortcut edges need to be added between the node's neighbors to maintain distances after the removal of the node. GPUs' strict thread convergence requirements and limited scratchpad preclude the bidirectional Dijkstra approach used in CPU implementations. Instead, CU-CH uses a two-hop-limit WPS tightly coded to fit GPU shared storage and to maintain thread convergence. Where two hops is sufficient speedup is high, but for larger graphs the hop limit exacts a toll due to the accumulation of unneeded shortcuts. The problem is overcome here by retaining the efficient CU-CH WPS but using it both for its original purpose and also to identify unnecessary shortcuts added in prior steps. The unnecessary shortcuts are culled (removed). Culling shortcuts not only dramatically reduces the time needed to contract a graph but also improves the quality of the contracted graph. For smaller graphs such as DIMACS Cal (travel time) contraction time is 61 % faster compared to CU-CH. For the DIMACS Europe and USA graphs contraction times are 40× and 12× faster, respectively. SSSP query times also improve dramatically, approaching those obtained on aggressively contracted graphs. The speedup over Geisberger's CPU code is over 100 times for NVidia VI00 GPUs on most graphs tried.

We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto sense. Our core algorithm heuristically solves the balanced connected st -edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core algorithm as a subroutine, we build variants that compute node separators that are independent of s and t . From the computed Pareto set, we can identify cuts with a particularly good tradeoff between cut size and balance that can be used to compute contraction and minimum fill-in orders, which can be used in Customizable Contraction Hierarchies (CCHs), a speed-up technique for shortest-path computations. Our core algorithm runs in O ( c ∣ E ∣) time, where E is the set of edges and c is the size of the largest outputted cut. This makes it well suited for separating large graphs with small cuts, such as road graphs, which is the primary application motivating our research. For road graphs, we present an extensive experimental study demonstrating that FlowCutter outperforms the current state of the art in terms of both cut sizes and CCH performance. By evaluating FlowCutter on a standard graph partitioning benchmark, we further show that FlowCutter also finds small, balanced cuts on nonroad graphs. Another application is the computation of small tree decompositions. To evaluate the quality of our algorithm in this context, we entered the PACE 2016 challenge [13] and won first place in the corresponding sequential competition track. We can therefore conclude that our FlowCutter algorithm finds small, balanced cuts on a wide variety of graphs.

We propose the first routing engine for computing driving directions in large-scale road networks that satisfies all requirements of a real-world production system. It supports arbitrary metrics (cost functions) and turn costs, enables real-time queries, and can incorporate a new metric in less than a second, which is fast enough to support real-time traffic updates and personalized cost functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in memory simultaneously. The algorithm is the core of the routing engine currently in use by Bing Maps.

Ride-hailing sharing involves grouping ride-hailing customers with similar trips and time schedules to share the same ride-hailing vehicle to reduce their total travel cost. With the current information and communication technology, ride-hailing customers and drivers can be matched in real-time via a ride-hailing platform. This paper formulates a dynamic ride-hailing sharing problem that simultaneously maximizes the number of served customers, minimizes the travel cost and travel time ratios, and considers the capacity, time window, and travel cost constraints. The travel cost ratio is the ratio of actual passengers’ fare to the passengers’ fare without ride-hailing sharing, whereas the travel time ratio is defined as the actual travel time (including waiting time) over the maximum allowable travel time. To solve the dynamic problem, it is divided into many small and continuous static subproblems with an equal time interval. Each subproblem is solved by a modified artificial bee colony (MABC) algorithm with path relinking, while the contraction hierarchies and vantage point tree are used to determine the shortest path and accelerate the algorithm, respectively. Problem properties and the performance of the proposed solution method are demonstrated using large-scale real-time data from Didi that is the largest ride-hailing company in China. The proposed method is shown to outperform the benchmark, i.e., greedy randomized adaptive search procedure (GRASP) with path relinking. The proposed method also performs better when the length of each time interval is longer, and the tolerance for the incremental travel time caused by detours is higher. We also demonstrate that (a) considering both travel cost and travel time ratios in the objective can achieve a better sharing percentage, and balance the increase in the travel time ratio and the decrease in the travel cost ratio compared with the objective that misses either travel time or the travel cost ratio; and (b) the passengers can gain a large out-of-pocket cost saving in the case of ride-hailing sharing while enduring a relatively small increase in travel time compared with the case without ride-hailing sharing.

We propose a novel technique for answering routing queries in public transportation networks that allows unrestricted walking. We consider several types of queries: earliest arrival time, Pareto-optimal journeys regarding arrival time, number of transfers and walking time, and profile, i.e. finding all Pareto-optimal journeys regarding travel time and arrival time in a given time interval. Our techniques uses hub labeling to represent unlimited foot transfers and can be adapted to both classical algorithms RAPTOR and CSA. We obtain significant speedup compared to the state-of-the-art approach based on contraction hierarchies. A research report version is deposited on HAL with number hal-02161283.

Real-world route planning problems are conventionally modeled as weighted graphs - either as grid graphs for open spaces or as path/road networks. The edge weights (e.g. Euclidean distances, travel times or energy consumption) are then derived from measurements or estimations. But the resulting weights are often overly precise and demand a lot of space to be stored. In addition, operations on these weights are computationally expensive. The common approach to avoid those problems is to round edge weights to reasonable precisions (e.g. whole meters, seconds or watt). Unfortunately, naive rounding schemes can easily distort the structure of optimal paths in the graph. In this paper, we present a novel rounding framework based on the construction of an overlay graph. We show that a carefully designed overlay graph based on so called contraction hierarchies can accelerate shortest path computations and minimize rounding errors at the same time, while demanding little space on its own.

Contraction hierarchies and (N-level) subgoal graphs are two preprocessing-based path-planning algorithms that have so far only been compared experimentally through the grid-based path-planning competitions, where both algorithms had undominated runtime/memory trade-offs. Subgoal graphs can be considered as a framework that can be customized to different domains through the choice of a reachability relation R that identifies pairs of nodes on a graph between which it is easy to find shortest paths. Subgoal graphs can exploit R in various ways to speed-up query times and reduce memory requirements. In this paper, we break down the differences between N-level subgoal graphs and contraction hierarchies, and augment contraction hierarchies with ideas from subgoal graphs to exploit R. We propose three different modifications, analyze their runtime/memory trade-offs, and provide experimental results on grids using canonical-freespace-reachability as R, which show that both N-level subgoal graphs and contraction hierarchies are dominated in terms of the runtime/memory trade-off by some of our new variants.

Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures - which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time., Projekt DEAL

Магістерська дисертація: 145 с., 45 рис., 24 табл., 2 додатки, 25 джерел. Дана робота присвячена дослідженню проблем побудови маршрутів на графах реальних доріг та створенню мультиагентної системи для маршрутизації та створення відповідного графу. В роботі досліджується можливість створення графу доріг з наявних картографічних даних, створюється граф доріг Києва, розглядаються існуючі методи пошуку оптимальних маршрутів на графах, реалізовуються 3 алгоритми та порівнюються результати їх роботи. Метою даної роботи є побудова мультиагентної системи, що дозволить створювати графи доріг за даними сервісу OpenStreetMap та виконувати пошук маршрутів будь-якої складності на побудованих графах за допустимий час. Об’єктом дослідження є побудова мультиагентної системи маршрутизації на основі алгоритмів пошуку маршруту. Предметом дослідження є алгоритми пошуку маршрутів на графах. Практична цінність: Розроблена система може слугувати веб-сервісом для мобільних додатків та веб сайтів та надавати можливості роутингу. Master’s thesis: 145 p., 45 fig., 24 tab., 2 appendixes, 25 sources. The theme: Multi agent routing system based on shortest path search algorithms in graph. The paper is devoted to the problem of route construction on the real road network graphs and multi agent routing system creation. The paper considered by the possibility of road graph creating using cartographic data, creating road graph for Kyiv road network, researching methods for searching optimal routes on graphs and implementation of three routing algorithms. The aim is to build multi agent system, that allows us to create road graphs using cartographic data from OpenStreetMap service and to build any complexity routes on created graphs for a reasonable time. The object of research is multi agent routing system construction based on route finding algorithms. The subject of research is route finding algorithms on graphs. Practical value: The system can be used as web-service by mobile applications and web-sites to provide a routing opportunity

We study the computation of good alternatives to the shortest path in road networks. Our approach is based on single via-node routing on top of contraction hierarchies and achieves superior quality and efficiency compared to previous methods. We present a fast preprocessing method for computing multiple good alternatives and apply this result in an online setting. This setting makes our result applicable in legacy systems with negligible memory overhead. An extensive experimental analysis on a continental-sized real- world road network proves the performance of our algorithm and supports the general systematic algorithm engineering approach. We also show how to combine our results with the competing concept of alternative graphs that encode many alternative paths at once.

Consider objects moving in a road network (e.g., groups of people or delivery vehicles), who may be free to choose routes, yet be required to arrive at certain locations at certain times. Such objects may need to assemble in groups within the network (friends meet while visiting a city, vehicles need to exchange items or information) without violating arrival constraints. Planning for such assemblies is hard when the network or the number of objects is large. Conversely, discovering actual or potential assemblies of such objects is important in many surveillance, security, and law-enforcement applications. This can be hard when object arrival observations are sparse due to inadequate sensor coverage or object countermeasures. We propose the novel class of assembly queries to model these scenarios, and present a unified scheme that addresses both of these complementary challenges. Given a set of objects and arrival constraints, we show how to first obtain the set of all possible locations visited by each moving object (the travel corridor), and then determine all possible assemblies, including the participants, locations, and durations. We present a formal model for various tracking strategies and several algorithms for using these strategies. We achieve excellent performance on these queries by preprocessing the network, using Contraction Hierarchies. Experimental results on real-world road networks show that we can efficiently and rapidly infer assembly information for very large networks and object groups.

The authors present a case study of a multimodal routing system that takes into account both dynamic and stochastic travel time information. A multimodal network model is presented that makes it possible to model the travel time information of each transportation mode differently. This travel time information can either be static or dynamic, or either deterministic or stochastic. Next, a Dijkstra-based routing algorithm is presented that deals with this variety of travel time information in a uniform way. This research focuses on a practical implementation of the system, which means that a number of assumptions were made, like the modelling of the stochastic distributions, comparing these distributions, and so on. A tradeoff had to be made between the performance of the system and the accuracy of the results. Experiments have shown that the proposed system produces realistic routes in a short amount of time. It is demonstrated that routing dynamically indeed results in a travel time gain in comparison to routing statically. By making use of the additional stochastic travel time information even better (i.e. faster), more reliable routes can be calculated. Moreover, it is shown that routing in the multimodal network may have its advantages over routing in a unimodal network, especially during rush hours.

We present a novel algorithm to solve the nonnegative single-source shortest path problem on road networks and other graphs with low highway dimension. After a quick preprocessing phase, we can compute all distances from a given source in the graph with essentially a linear sweep over all vertices. Because this sweep is independent of the source, we are able to reorder vertices in advance to exploit locality. Moreover, our algorithm takes advantage of features of modern CPU architectures, such as SSE and multi-core. Compared to Dijkstra's algorithm, our method needs fewer operations, has better locality, and is better able to exploit parallelism at multi-core and instruction levels. We gain additional speedup when implementing our algorithm on a GPU, where our algorithm is up to three orders of magnitude faster than Dijkstra's algorithm on a high-end CPU. This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. Several algorithms, such as computing the graph diameter, exact arc flags, or centrality measures (exact reaches or betweenness), can be greatly accelerated by our method.

Current route planning services like Google Maps exhibit a clear-cut separation between the map rendering component and the route planning engine. While both rely on respective road network data, the route planning task is typically performed using state-of-the art data structures for speeding-up shortest/quickest path queries like Hub Labels, Arc Flags, or Transit Nodes, whereas the map rendering task usually involves a rendering framework like Mapnik or Kartograph. In this paper we show how to augment Contraction Hierarchies – another popular data structure for speeding-up shortest path queries – to also cater for the map rendering task. As a result we get a unified data structure (URAN) which lays the algorithmic foundation for novel map rendering and navigation systems. It also allows for customization of the map rendering, e.g. to accommodate different display devices (with varying resolution and hardware capabilities) or routing scenarios. At the heart of our approach lies a generalized graph simplification scheme derived from Contraction Hierarchies with a very lightweight augmentation for extracting (simplified) subgraphs. In a client-server scenario it additionally has the potential to shift the actual route computation to the client side, both relieving the server infrastructure as well as providing some degree of privacy when planning a route.

We study the problem of computing time-dependent shortest routes for truck drivers. In contrast to conventional route planning, truck drivers have to obey government regulations that impose limits on non-stop driving times. Therefore, route planners must plan break periods in advance and select suitable parking lots. To ensure that maximum driving times are not exceeded, predictable congestion due to, e. g., peak hours should also be taken into account. Therefore, we introduce the truck driver routing problem in time-dependent road networks. It turns out that the combination of time-dependent driving times with constraints imposed by drivers’ working hours requires computation of multiple time-dependent profiles for optimal solutions. Although conceptually simple, profile search is expensive. We greatly reduce (empirical) running times by calculating bounds on arrival and departure times during additional search phases to only query partial profiles and only to a fraction of the parking lots. Carefully integrating this approach with a one-to-many extension of time-dependent contraction hierarchies makes our approach practical. For even faster queries, we also propose a heuristic variant that works very well in practice. Excellent performance of our algorithms is demonstrated on a recent real-world instance of Germany that is much harder than time-dependent instances considered in previous works.

The current widespread use of location-based services and GPS technologies has revived interest in very fast and scalable shortest path queries. We introduce a new shortest path query type in which dynamic constraints may be placed on the allowable set of edges that can appear on a valid shortest path (e.g., dynamically restricting the type of roads or modes of travel which may be considered in a multimodal transportation network). We formalize this problem as a specific variant of formal language constrained shortest path problems, which we call the Kleene Language Constrained Shortest Paths problem. To efficiently support this type of dynamically constrained shortest path query for large-scale datasets, we extend the hierarchical graph indexing technique known as Contraction Hierarchies. Our experimental evaluation using the North American road network dataset (with over 50 million edges) shows an average query speed and search space improvement of over 3 orders of magnitude compared to the naïve adaptation of the standard Dijkstra's algorithm to support this query type. We also show an improvement of over 2 orders of magnitude compared to the only previously-existing indexing technique which could solve this problem without additional preprocessing.

We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.

We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto sense. Our core algorithm heuristically solves the balanced connected st-edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core algorithm as a subroutine, we build variants that compute node separators that are independent of s and t. From the computed Pareto set, we can identify cuts with a particularly good tradeoff between cut size and balance that can be used to compute contraction and minimum fill-in orders, which can be used in Customizable Contraction Hierarchies (CCHs), a speed-up technique for shortest-path computations. Our core algorithm runs in O(cmEm) time, where E is the set of edges and c is the size of the largest outputted cut. This makes it well suited for separating large graphs with small cuts, such as road graphs, which is the primary application motivating our research. For road graphs, we present an extensive experimental study demonstrating that FlowCutter outperforms the current state of the art in terms of both cut sizes and CCH performance. By evaluating FlowCutter on a standard graph partitioning benchmark, we further show that FlowCutter also finds small, balanced cuts on nonroad graphs. Another application is the computation of small tree decompositions. To evaluate the quality of our algorithm in this context, we entered the PACE 2016 challenge [13] and won first place in the corresponding sequential competition track. We can therefore conclude that our FlowCutter algorithm finds small, balanced cuts on a wide variety of graphs.

Graph fill-in, elimination ordering, separators, nested dissection orders and tree-width are only some examples of classical graph concepts that are related in manifold ways. This essay shows how contraction hierarchies, a successful approach to speed up Dijkstra’s algorithm for shortest paths, fits into this series of graph concepts. A theoretical consequence of this insight is a guarantee for the size of the search space required by Dijkstra’s algorithm combined with contraction hierarchies. On the other hand, the use of nested dissection leads to a very practicable variant of contraction hierarchies that can be applied in scenarios where edge lengths often change.

The goods structure effect increases the complexity and dynamics of logistic processes. To handle the resulting challenges and requirements, planning and controlling of logistic processes have to be reliable and adaptive. Especially in these dynamic environments, Multiagent-Based Simulation (MABS) is a suitable approach to support decision makers in order to evaluate the companies' processes and to identify optimal decisions. This paper presents the PlaSMA multiagent simulation platform, which has been developed for the evaluation of logistics scenarios and strategic analyses. As shortest-path searches are an essential but cost intensive part of the agents for the simulation of transport processes, we focus on the parallel application of a state-of-the-art Hub Labeling algorithm, which is combined with Contraction Hierarchies. The results show, that the optimal number of concurrently running routing agents is restricted by available cores and/or the number of agents running physically concurrently. Moreover, by slightly restricting the agents' autonomy a significant increase in runtime performance can be achieved without losing the advantages of agent-based simulations. This allows to simulate large real-world transport scenarios with MABS and low hardware requirements.

In the last decade, there has been a substantial amount of research in finding routing algorithms designed specifically to run on real-world graphs. In 2010, Abraham et al. showed upper bounds on the query time in terms of a graph’s highway dimension and diameter for the current fastest routing algorithms, including contraction hierarchies, transit node routing, and hub labeling. In this paper, we show corresponding lower bounds for the same three algorithms. We also show how to improve a result by Milosavljevic which lower bounds the number of shortcuts added in the preprocessing stage for contraction hierarchies. We relax the assumption of an optimal contraction order (which is NP-hard to compute), allowing the result to be applicable to real-world instances. Finally, we give a proof that optimal preprocessing for hub labeling is NP-hard. Hardness of optimal preprocessing is known for most routing algorithms, and was suspected to be true for hub labeling.

The Fourth Industrial Revolution and the consequent integration of the Internet of Things and Services into industrial processes increase the requirements of transport processes. Customer demanding same-day deliveries, shorter transit-times, individual qualities of shipments, and higher amounts of small size orders raise the complexity and dynamics in logistics. In these highly dynamic environments, multiagent systems (MAS) and multiagent-based simulation (MASB) offer a suitable approach to handle the complexity and to provide the required flexibility, robustness, as well as customized behavior. This article focuses on the impact and the relevance of shortest-path queries in MAS and MABS. It compares the application of state-of-the-art algorithms and investigates different modeling approaches for efficient and concurrent shortest-path searches. The results prove that the application of a highly efficient algorithm such as hub labeling with contraction hierarchies is an essential key component in the agent-based control of dynamic transport processes. Moreover, the results reveal that choosing a modeling approach which slightly restricts the agents’ autonomy increases significantly the runtime performance without losing the advantages of multiagent systems. This allows for applying MAS to solve large scale real-world transport problems and for performing MABS with low hardware requirements.

We present a new way of analyzing Contraction Hierarchies (CH), a widely used speed-up technique for shortest path computations in road networks. In previous work, preprocessing and query times of deterministically constructed CH on road networks with n nodes were shown to be polynomial in n as well as the highway dimension h of the network and its diameter D. While h is conjectured to be polylogarithmic for road networks, a tight bound remains an open problem. We rely on the empirically justifiable assumption of the road network exhibiting small growth. We introduce a method to construct randomized Contraction Hierarchies on road networks as well as a probabilistic query routine. Our analysis reveals that randomized CH lead to sublinear search space sizes in the order of \(\sqrt{n} \log \sqrt{n}\), auxiliary data in the order of \(n \log ^2 \sqrt{n}\), and correct query results with high probability after a polynomial time preprocessing phase.

Are you looking for new lectures for your course on algorithms, combinatorial optimization, or algorithmic game theory? Maybe you need a convenient source of relevant, current topics for a graduate student or advanced undergraduate student seminar? Or perhaps you just want an enjoyable look at some beautiful mathematical and algorithmic results, ideas, proofs, concepts, and techniques in discrete mathematics and theoretical computer science?Gems of Combinatorial Optimization and Graph Algorithms is a handpicked collection of up-to-date articles, carefully prepared by a select group of international experts, who have contributed some of their most mathematically or algorithmically elegant ideas. Topics include longest tours and Steiner trees in geometric spaces, cartograms, resource buying games, congestion games, selfish routing, revenue equivalence and shortest paths, scheduling, linear structures in graphs, contraction hierarchies, budgeted matching problems, and motifs in networks.This volume is aimed at readers with some familiarity of combinatorial optimization, and appeals to researchers, graduate students, and advanced undergraduate students alike.

Graph-like data appears in many applications, such as social networks, internet hyperlinks, roadmaps, etc. and in most cases, graphs are dynamic, evolving through time. In this work, we study the problem of efficient shortest-path query evaluation on evolving social graphs. Our shortest-path queries are "temporal": they can refer to any time-point or time-interval in the graph's evolution, and corresponding valid answers should be returned. To efficiently support this type of temporal query, we extend the traditional Dijkstra's algorithm to compute shortest-path distance(s) for a time-point or a time-interval. To speed up query processing, we explore preprocessing index techniques such as Contraction Hierarchies (CH). Moreover, we examine how to maintain the evolving graph along with the index by utilizing temporal partition strategies. Experimental evaluations on real world datasets and large synthetic datasets demonstrate the feasibility and scalability of our proposed efficient techniques and optimizations.

We develop the data structure PReaCH (for Pruned Reachability Contraction Hierarchies) which supports reachability queries in a directed graph. PReaCH adapts the contraction hierarchy speedup techniques for shortest path queries to the reachability setting. The resulting approach is surprisingly simple and guarantees linear space and near linear preprocessing time. Orthogonally to that, we improve existing pruning techniques for the search by gathering more information from a single DFS-traversal of the graph. In particular, we show that more classes of node numberings can be used to obtain strong pruning information.

All customization running times in this article are reported to be in milliseconds. This is unfortunately a mistake. The correct unit is seconds. This is especially the case for the reported CRP customization times. All comparisons between our method and CRP are therefore still valid as the compared numbers are wrong by the same factor.

For single-pair shortest path problems, Contraction Hierarchies (CH) provide very small query times together with a very low space overhead for the graph. During a preprocessing every node is assigned a distinct rank. Queries are performed using an alternating bidirectional Dijkstra search that only expands towards higher ranked nodes. In its original version CH do not take turn restrictions (TR) into account. This may lead to illegal routes whose length may considerably differ from legal ones. Incorporating TR widens the scope of application for CH, e.g., car navigation or precise traffic simulations. A way to consider TR is to switch from a node-based to an edge-based search, implicitly allowing nodes to be settled more than once. Compared to the original CH query this increases the size of the search trees substantially. A more space efficient adaptive algorithm combining node-based with on-demand edge-based search is presented, where nodes may only be settled multiply if the encountered path towards them traverses a (possible) TR. The number of iterations in this approach is at most as high as the edge-base search. Depending on the number of TR and the average node degree in the graph our approach outperforms the edge-based search by far.