Quickest path queries on transportation network

DOI10.1016/J.COMGEO.2014.01.004MaRDI QIDQ2249042zbMATH OpenOpenAlexFDO

Authors Radwa El Shawi, Christos Levcopoulos, Joachim Gudmundsson

Publication date 27 June 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.0634

zbMATH Keywords

computational geometryapproximation algorithmsshortest pathtransport networks

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Transportation, logistics and supply chain management (90B06)

Abstract: This paper considers the problem of finding a quickest path between two points in the Euclidean plane in the presence of a transportation network. A transportation network consists of a planar network where each road (edge) has an individual speed. A traveller may enter and exit the network at any point on the roads. Along any road the traveller moves with a fixed speed depending on the road, and outside the network the traveller moves at unit speed in any direction. We give an exact algorithm for the basic version of the problem: given a transportation network of total complexity n in the Euclidean plane, a source point s and a destination point t, and the quickest path between s and t. We also show how the transportation network can be preprocessed in time O(n^2 log n) into a data structure of size O(n^2) such that (1 + epsilon)-approximate cheapest path cost queries between any two points in the plane can be answered in time O(1epsilon^4 log n).

Recommendations

• scientific article; zbMATH DE number 5734726
• Engineering Highway Hierarchies
• Robust, almost constant time shortest-path queries in road networks
• Shortest path calculation in large road networks
• Fast Routing in Road Networks with Transit Nodes

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• A note on two problems in connexion with graphs
• Algorithms and Computation
• An algorithmic approach to some problems in terrain navigation
• CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER
• Computational geometry. Algorithms and applications.
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Geometric Spanner Networks
• OPTIMAL CONSTRUCTION OF THE CITY VORONOI DIAGRAM
• Ordered theta graphs
• Path Planning in 0/1/∞ Weighted Regions with Applications
• Quickest paths, straight skeletons, and the city Voronoi diagram
• The weighted region problem
• VORONOI DIAGRAMS FOR A TRANSPORTATION NETWORK ON THE EUCLIDEAN PLANE
• Voronoi diagram for services neighboring a highway

Cited in

(2)

• scientific article; zbMATH DE number 5734726 (Why is no real title available?)
• Fast Routing in Road Networks with Transit Nodes

This page was built for publication: Quickest path queries on transportation network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249042)