We consider the
point-to-point (approximate) shortest-path query problem
, which is the following generalization of the classical
single-source (SSSP)
and
all-pairs shortest-path (APSP)
problems: we ...are first presented with a
network (graph)
. A so-called preprocessing algorithm may compute certain information
(a data structure or index)
to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance queries, which should be answered as fast as possible.
Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast route planning methods; database and information systems researchers investigate
materialization tradeoffs
, query processing on
spatial networks
, and
reachability queries
; and theoretical computer scientists analyze
distance oracles
and
sparse spanners
. Related problems are considered for
compact routing
and
distance labeling
schemes in networking and distributed computing and for
metric embeddings
in geometry as well.
In this survey, we review selected approaches, algorithms, and results on shortest-path queries from these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguable practical significance such as planar graphs and complex networks.
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has ...been studied extensively. Previously, Hershberger and Suri (in SIAM Journal on Computing, 1999) gave an algorithm of O(n log n) time and O(n log n) space, where n is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri’s algorithm, Wang (in SODA’21) reduced the space to O(n) while the runtime of the algorithm is still O(n log n). In this article, we present a new algorithm of O(n+h log h) time and O(n) space, provided that a triangulation of the free space is given, where h is the number of obstacles. The algorithm is better than the previous work when h is relatively small. Our algorithm builds a shortest path map for a source point s so that given any query point t, the shortest path length from s to t can be computed in O(log n) time and a shortest s-t path can be produced in additional time linear in the number of edges of the path.
•Recursive exact algorithm that implicitly enumerates all solutions.•Fast method that works well on graphs of up to 1.2 million nodes and 2.8 million arcs.•Consistently outperformed a top-performer ...benchmark algorithm for real road networks.•Easily extensible to the multiobjective shortest path problem with three or more objectives.
The Biobjective Shortest Path Problem (BSP) is the problem of finding (one-to-one) paths from a start node to an end node, while simultaneously minimizing two (conflicting) objective functions. We present an exact recursive method based on implicit enumeration that aggressively prunes dominated solutions. Our approach compares favorably against a top-performer algorithm on two large testbeds from the literature and efficiently solves the BSP on large-scale networks with up to 1.2 million nodes and 2.8 million arcs. Additionally, we describe how the algorithm can be extended to handle more than two objectives and prove the concept on networks with up to 10 objectives.
The clustered shortest-path tree problem (CluSPTP) is an extension of the classical single-source shortest-path problem, in which, given a graph with the set of nodes partitioned into a predefined, ...mutually exclusive and exhaustive set of clusters, we are looking for a shortest-path spanning tree from a given source to all the other nodes of the graph, with the property that each cluster should induce a connected subtree. CluSPTP belongs to the class of generalized combinatorial optimization problems, and, in general, is proved to be a non-deterministic polynomial time hard (NP-hard) problem. In this paper, we propose a novel genetic algorithm (GA), which is designed to fit the challenges of the investigated problem. The main features of our GA are: the use of an innovative representation scheme that allows us to define meaningful genetic operators and the use of a hybrid initial population. Extensive computational results are reported and discussed for two sets of instances: euclidean and non-euclidean. The performance of the proposed algorithm was evaluated on six types of benchmark euclidean instances available in the literature and on six types of non-euclidean instances obtained from the corresponding euclidean ones. The obtained results show an improvement with respect to existing methods from the literature, both in terms of the quality of the achieved solutions and the computation times necessary to obtain them. They demonstrate that our genetic algorithm outperforms all the existing methods from the literature, providing for all the existing benchmark instances the optimal solutions in all 30 independent trials.
This paper addresses the problem of multiple graph matching (MGM) by considering both offline batch mode and online setting. We explore the concept of cycle-consistency over pairwise matchings and ...formulate the problem as finding optimal composition path on the supergraph, whose vertices refer to graphs and edge weights denote score function regarding consistency and affinity. By our theoretical study we show that the offline and online MGM on supergraph can be converted to finding all pairwise shortest paths and single-source shortest paths respectively. We adopt the Floyd algorithm <xref ref-type="bibr" rid="ref1">1 and shortest path faster algorithm (SPFA) <xref ref-type="bibr" rid="ref2">2 , <xref ref-type="bibr" rid="ref3">3 to effectively find the optimal path. Extensive experimental results show our methods surpass state-of-the-art MGM methods, including CAO <xref ref-type="bibr" rid="ref4">4 , MISM <xref ref-type="bibr" rid="ref5"> 5 , IMGM <xref ref-type="bibr" rid="ref6">6 , and many other recent methods in offline and online settings. Source code will be made publicly available.
The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under ...column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.
•A moment-matching-based hybrid genetic algorithm is proposed to search RSP.•Empirical travel time data from probe vehicles are utilized to measure TTR.•A moment-matching method is utilized to ...determine path TTD parameters.•Numerical studies based on a synthetic network and a real network are conducted.
Most existing studies on routing guidance only paid attention to the average path travel time, which failed to consider travel time reliability (TTR) preferences by different travelers. In this study, a moment-matching-based hybrid genetic algorithm (MHGA) is proposed to search the reliable shortest path (RSP) in stochastic road networks with link correlations. First, the goodness-of-fit results based on field data reveal that lognormal distributions are more appropriate for characterizing link travel times. The impact of topological distance (measured by the number of links) and road type on link correlations is also scrutinized. Then, a moment-matching method (MOM) is utilized to determine the parameters of the approximate path travel time distribution (TTD) by accounting for link correlations. A local search algorithm is designed to improve the search ability of the path finding algorithm. In view of travelers’ risk tolerance, the algorithm enables the provision of personalized routing guidance for individual travelers. Furthermore, to support path finding applications in a large-scale network, heuristic constraints are imposed to help reduce the computational workload and accelerate the convergence speed of the search process. Finally, numerical case studies based on synthetic networks and a real road network in Beijing are presented, and the results help demonstrate that the algorithm has good potential to solve RSP searching problems in a large-scale network with desirable efficiency.
This paper aims at solving the stochastic shortest path problem in vehicle routing, the objective of which is to determine an optimal path that maximizes the probability of arriving at the ...destination before a given deadline. To solve this problem, we propose a data-driven approach, which directly explores the big data generated in traffic. Specifically, we first reformulate the original shortest path problem as a cardinality minimization problem directly based on samples of travel time on each road link, which can be obtained from the GPS trajectory of vehicles. Then, we apply an ℓ 1 -norm minimization technique and its variants to solve the cardinality problem. Finally, we transform this problem into a mixed-integer linear programming problem, which can be solved using standard solvers. The proposed approach has three advantages over traditional methods. First, it can handle various or even unknown travel time probability distributions, while traditional stochastic routing methods can only work on specified probability distributions. Second, it does not rely on the assumption that travel time on different road segments is independent of each other, which is usually the case in traditional stochastic routing methods. Third, unlike other existing methods which require that deadlines must be larger than certain values, the proposed approach supports more flexible deadlines. We further analyze the influence of important parameters to the performances, i.e., accuracy and time complexity. Finally, we implement the proposed approach and evaluate its performance based on a real road network of Munich city. With real traffic data, the results show that it outperforms traditional methods.
Abstract
The paper considers two problems: computation of shortest paths on triangle surfaces and calculation of principal curvatures at vertices of triangle surfaces. A technique that allows us to ...compute smoother and shorter paths using intermediate admissible directions and linear interpolation of potential functions is proposed. Conventional methods that compute the curvature in nodes of triangle surfaces are based on processing only adjacent vertices. They are non stable because triangle meshes contain frequently oscillating errors in positions of the vertices. We propose a simple practical method that accounts for larger neighborhoods of vertices. The kriging method aimed to the sparse representation of specific surface parts (aesthetic regions) is sketched. Preliminary numerical results are presented.
PDF
