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.
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.