Strategic Deconfliction in the European Air Traffic Flow Management with Column Generation

Kurzfassung

In the European Air Traffic Flow Management, en-route conflicts between aircraft may be avoided strategically. One option for strategic deconfliction is the allocation of alternative departure-timeslots. To find the best slots for all flights, we solve a Binary Integer Problem. In this problem, each flight is associated with linear delay costs and a departure condition. Furthermore, flights have to satisfy sector and aerodrome capacity constraints. Since conflicts involve at least two flights, there is a coupling between variables. Each potential conflict is modelled by a linear constraint, which assigns conflict costs by setting a conflict variable. However, conflict constraints of lp-relaxed variables do not trigger their conflict costs. Therefore, branch-and-bound nodes do not contain costs for relaxed conflicts, which weakens lower bounds. With a conventional solver, the deconfliction of a full-day of European air traffic takes approximately one hour. To reduce the computation times of the Network Flow Environment (NFE), we extend the pricing algorithm to perform deconfliction. This method of column generation is initiated with only a subset of possible departure-timeslots and includes more slot-options iteratively. Promising variables with reduced costs are discovered by pricing dual variables. Conflicts increase dual departure costs and thereby boost the search of alternative departure-timeslots for conflicted flights. The column generation method reduces computation times for the optimal solution of a problem with over twenty-five thousand flights by more than eighty percent.