The Path&Cycle formulation for the Hotspot Problem in Air Traffic Management
Chapter
Published version
Permanent lenke
http://hdl.handle.net/11250/2564824Utgivelsesdato
2018Metadata
Vis full innførselSamlinger
- Publikasjoner fra CRIStin - SINTEF AS [5583]
- SINTEF Digital [2379]
Originalversjon
18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), August 23–24, 2018, Helsinki, Finland, 14:1-14:11Sammendrag
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.