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.2018.14
URN: urn:nbn:de:0030-drops-97191
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9719/
Go to the corresponding OASIcs Volume Portal

Mannino, Carlo ; Sartor, Giorgio

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

pdf-format:
OASIcs-ATMOS-2018-14.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{mannino_et_al:OASIcs:2018:9719,
  author =	{Carlo Mannino and Giorgio Sartor},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Ralf Bornd{\"o}rfer and Sabine Storandt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9719},
  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}
}

Keywords: Air Traffic Management, Hotspot Problem, Job-shop scheduling, Mixed Integer Linear Programming
Collection: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Issue Date: 2018
Date of publication: 28.08.2018

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