5 Search Results for "Blanco, Marco"

Document
DOI: 10.4230/OASIcs.ATMOS.2022.1
An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles

Authors: Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A* heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.
Cite as

Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas. An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2022.1,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Maristany de las Casas, Pedro},
  title =	{{An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.1},
  URN =		{urn:nbn:de:0030-drops-171052},
  doi =		{10.4230/OASIcs.ATMOS.2022.1},
  annote =	{Keywords: shortest path problem, a-star algorithm, flight trajectory optimization, flight planning, heuristics}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.7
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data

Authors: Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.
Cite as

Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe. Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.7,
  author =	{Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine},
  title =	{{Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{7:1--7:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.7},
  URN =		{urn:nbn:de:0030-drops-148767},
  doi =		{10.4230/OASIcs.ATMOS.2021.7},
  annote =	{Keywords: Preprocessing Shortest Path Problems, Interval Data, Graph Algorithms}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.8
A Priori Search Space Pruning in the Flight Planning Problem

Authors: Adam Schienle, Pedro Maristany, and Marco Blanco

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra’s algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft’s tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs. We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90% in our setting.
Cite as

Adam Schienle, Pedro Maristany, and Marco Blanco. A Priori Search Space Pruning in the Flight Planning Problem. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schienle_et_al:OASIcs.ATMOS.2019.8,
  author =	{Schienle, Adam and Maristany, Pedro and Blanco, Marco},
  title =	{{A Priori Search Space Pruning in the Flight Planning Problem}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.8},
  URN =		{urn:nbn:de:0030-drops-114205},
  doi =		{10.4230/OASIcs.ATMOS.2019.8},
  annote =	{Keywords: time-dependent shortest path problem, crossing costs, flight trajectory optimization, preprocessing, search space}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.15
Cost Projection Methods for the Shortest Path Problem with Crossing Costs

Authors: Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that transforms crossing costs into shadow costs on individual arcs, thus approximating the SPPCC by a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
Cite as

Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach. Cost Projection Methods for the Shortest Path Problem with Crossing Costs. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2017.15,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Dung Ho\`{a}ng, Nam and Kaier, Anton and Casas, Pedro M. and Schlechte, Thomas and Schlobach, Swen},
  title =	{{Cost Projection Methods for the Shortest Path Problem with Crossing Costs}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{15:1--15:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.15},
  URN =		{urn:nbn:de:0030-drops-78939},
  doi =		{10.4230/OASIcs.ATMOS.2017.15},
  annote =	{Keywords: shortest path problem, resource constrained shortest path, crossing costs, flight trajectory optimization, overflight fees, cost projection}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.12
Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind

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

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

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.
Cite as

Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2016.12,
  author =	{Blanco, Marco and Bornd\"{o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Schienle, Adam and Schlechte, Thomas and Schlobach, Swen},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.12},
  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}
}
  • Refine by Author
  • 4 Blanco, Marco
  • 3 Borndörfer, Ralf
  • 2 Kaier, Anton
  • 2 Maristany de las Casas, Pedro
  • 2 Schienle, Adam
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorial optimization
  • 2 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Paths and connectivity problems
  • 1 Mathematics of computing → Discrete optimization
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 4 flight trajectory optimization
  • 3 shortest path problem
  • 2 crossing costs
  • 2 preprocessing
  • 2 time-dependent shortest path problem
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017
  • 1 2019
  • 1 2021
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact