To main content

The Path&Cycleformulation for the HotspotProblem in Air Traffic Management

The Path&Cycleformulation for the HotspotProblem in Air Traffic Management

Category
Conference lecture and academic presentation
Abstract
Air traffic management involves the coordination of flights in a particular region of the world with the objective of guaranteeing their safety while possibly reducing delays. Each region is subdivided in smaller sectors and the number of airplanes that will occupy each sector in a given time can be forecast taking into account the timetable and the planned route of the airplanes. For safety reasons, a certain capacity is assigned to each sector and a hotspot is defined as a sector in which the predicted number of airplanes is greater than its maximum capacity in at least one point in time. The hotspot problem consists of finding a hotspot-free schedule for the airplanes that minimize delays. In particular, given the route and timetable of a set of flights we assume that the airplanes will fly at constant speed and we focus on choosing their departure times in order prevent hotspots while minimizing the total sum of delays. We present a novel, non-compact formulation for this problem that is alternative to the more conventional big-M. In particular we present a methodology that exploits Benders’ decomposition to obtain a (master) problem only in the binary variables plus a few continuous variables to represent the objective function. The decomposition allows us to get rid of infamous big-M coefficients (at the cost of an increased number of linear constraints). Moreover, the constraints of the reformulated master correspond to basic graph structures, such as paths, cycles and trees. The new formulation is obtained by strengthening and lifting the constraints of a classical Benders’ reformulation. Preliminary computational results on random but realistic instances show that the new approach favorably compares against the big-M formulation.
Client
  • Norges forskningsråd / 267554
Language
English
Affiliation
  • SINTEF Digital / Mathematics and Cybernetics
  • University of Oslo
Presented at
ODS 2018
Place
Taormina
Date
09.09.2018 - 12.09.2018
Organizer
AIRO - Italian Operation Research Society
Year
2018