Data-driven kernel search for trajectory based air traffic flow management

In the Air Traffic Flow Management (ATFM) problem, we want to assign a flight plan to each scheduled flight, taking both the network manger’s and the airspace users’ perspectives into account: on the one side, safe operations and efficient use of airspace are required, on the other side, we have to consider the airspace users flying preferences [1]. In this talk, we explicitly consider routes’ preference into account and, to this aim, we propose a trajectory based ATFM modeling framework, where a set of alternative flight plans is directly extracted from air traffic data repositories by means of data analytics. We thus build consistent trajectory option sets (in the spirit of [2]) and, moreover, we learn the preference of each flight for each option [3]. We propose an assignment formulation for the ATFM, where binary variables select a trajectory option and a delay for each flight, constraints limit total delays and airspace congestion, and the objective function maximizes airspace users preferences. Realistic daily instances lead to prohibitively large Integer Linear Programming models, and we consider kernel search inspired matheuristics: they solve a sequence of models restricted to a suitable variable subset and, at each iteration, a kernel of variables is expanded by a further bucket. We compare different implementations where buckets are a-priori defined based on a linear relaxation, or they are dynamically determined by machine learning techniques. In particular, a tree classifier, trained on reduced-size instances, selects the next bucket by considering features of the candidate variables, the current solution and the search state. Preliminary computational results show that appropriate configurations of the methods are able to solve realistic daily instances within limited optimality gap and acceptable running times. [1] Dal Sasso, V., Djeumou Fomeni, F., Lulli, G., Zografos, K.: Incorporating stakeholders priorities and preferences in 4D trajectory optimization. Transportation Research Part B 117:594609, 2018. [2] Estes, A.S, Ball, M.O.: Alternative Resource Allocation Mechanisms for the Collaborative Trajectory Options Program (CTOP). In Thirteenth USA/Europe Air Traffic Management Research and Development Seminar, 1-9, 2019. [3] Lancia, C., De Giovanni, L., Lulli, G.: Data analytics for trajectory selection and preference-model extrapolation in the European airspace. In: The OR2018 Proceedings. Springer, 1-7, 2018.