OASIcs.ATMOS.2018.14.pdf
- Filesize: 0.55 MB
- 11 pages
Document
The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management
Authors
-
Part of:
Volume:
18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-28
Cite AsGet BibTex
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)
https://doi.org/10.4230/OASIcs.ATMOS.2018.14
https://doi.org/10.4230/OASIcs.ATMOS.2018.14
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.
Subject Classification
ACM Subject Classification
- Applied computing → Transportation
Keywords
- Air Traffic Management
- Hotspot Problem
- Job-shop scheduling
- Mixed Integer Linear Programming
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Cyril Allignol, Nicolas Barnier, Pierre Flener, and Justin Pearson. Constraint programming for air traffic management: a survey 1: In memory of pascal brisset. The Knowledge Engineering Review, 27(3):361-392, 2012.
-
Thomas Dubot, Judicaël Bedouet, and Stéphane Degrémont. Modelling, generating and evaluating sector configuration plans-methodology report of the sesar vp-755 exercise. In 30th Congress of the International Council of the Aeronautical Sciences (ICAS 2016), 2016.
- Leonardo Lamorgese and Carlo Mannino. A non-compact formulation for job-shop scheduling problems in transportation (Dagstuhl Seminar 16171). Dagstuhl Reports, 6(4):151, 2016. submited to Operations Research, under revision. URL: http://dx.doi.org/10.4230/DagRep.6.4.139.
-
Alessandro Mascis and Dario Pacciarelli. Job-shop scheduling with blocking and no-wait constraints. European Journal of Operational Research, 143(3):498-517, 2002.
-
Tolebi Sailauov and ZW Zhong. An optimization model for large scale airspace. International Journal of Modeling and Optimization, 6(2):86, 2016.
-
Nina Schefers, Miquel Angel Piera, Juan José Ramos, and Jenaro Nosedal. Causal analysis of airline trajectory preferences to improve airspace capacity. Procedia Computer Science, 104:321-328, 2017.
-
Bo Vaaben and Jesper Larsen. Mitigation of airspace congestion impact on airline networks. Journal of Air Transport Management, 47:54-65, 2015.