Quickest path queries on transportation network

DOI10.1016/J.COMGEO.2014.01.004zbMATH Open1291.90035arXiv1012.0634OpenAlexW2569740479MaRDI QIDQ2249042FDOQ2249042

Authors: Radwa El Shawi, Christos Levcopoulos, Joachim Gudmundsson 

Publication date: 27 June 2014

Published in: Computational Geometry (Search for Journal in Brave)

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).

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

Recommendations

• scientific article
• 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

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)

Cites Work

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

Cited In (2)

• Fast Routing in Road Networks with Transit Nodes
• Title not available (Why is that?)

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)