DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2018.14

The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management

Authors: Carlo Mannino and Giorgio Sartor

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract

The Hotspot Problem in Air Traffic Management consists of optimally rescheduling a set of airplanes that are forecast to occupy an overcrowded region of the airspace, should they follow their original schedule. We first provide a MILP model for the Hotspot Problem using a standard big-M formulation. Then, we present a novel MILP model that gets rid of the big-M coefficients. The new formulation contains only simple combinatorial constraints, corresponding to paths and cycles in an associated disjunctive graph. We report computational results on a set of randomly generated instances. In the experiments, the new formulation consistently outperforms the big-M formulation, both in terms of running times and number of branching nodes.

Cite as

Carlo Mannino and Giorgio Sartor. The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mannino_et_al:OASIcs.ATMOS.2018.14,
  author =	{Mannino, Carlo and Sartor, Giorgio},
  title =	{{The Path\&Cycle Formulation for the Hotspot Problem in Air Traffic Management}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{14:1--14:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.14},
  URN =		{urn:nbn:de:0030-drops-97191},
  doi =		{10.4230/OASIcs.ATMOS.2018.14},
  annote =	{Keywords: Air Traffic Management, Hotspot Problem, Job-shop scheduling, Mixed Integer Linear Programming}
}

Search Results

Documents authored by Sartor, Giorgio

The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management

Abstract

Cite as

Thanks for your feedback!

Could not send message