License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2016.12
URN: urn:nbn:de:0030-drops-65360
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6536/
Go to the corresponding OASIcs Volume Portal

Blanco, Marco ; Borndörfer, Ralf ; Hoang, Nam-Dung ; Kaier, Anton ; Schienle, Adam ; Schlechte, Thomas ; Schlobach, Swen

Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind

pdf-format:
OASIcs-ATMOS-2016-12.pdf (0.6 MB)

Abstract

We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions.

The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs.

We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs)
algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.

BibTeX - Entry

@InProceedings{blanco_et_al:OASIcs:2016:6536,
  author =	{Marco Blanco and Ralf Bornd{\"o}rfer and Nam-Dung Hoang and Anton Kaier and Adam Schienle and Thomas Schlechte and Swen Schlobach},
  title =	{{Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{12:1--12:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Marc Goerigk and Renato Werneck},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6536},
  URN =		{urn:nbn:de:0030-drops-65360},
  doi =		{10.4230/OASIcs.ATMOS.2016.12},
  annote =	{Keywords: shortest path problem, A*, flight trajectory optimization, preprocessing, contraction hierarchies, time-dependent shortest path problem}
}

Keywords: shortest path problem, A*, flight trajectory optimization, preprocessing, contraction hierarchies, time-dependent shortest path problem
Collection: 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI