A Tabu Search Algorithm for the Optimization of the Long Term Parking of Aircraft

Abstract

The 2020 coronavirus pandemic lead to a virtual standstill of air passenger traffic in the spring of that same year. While some travel restrictions have since been lifted, passenger air travel is not expected to return to pre-coronavirus levels for several years. Then the question arises of how to park the large amounts of grounded aircraft efficiently, minimizing valuable airport space used. While aircraft parking for this purpose is a largely unexplored area in academic literature, the problem shows similarities with cutting and packing problems which have been researched for many years. Hence, the proposed model in the paper is modelled similar to that of the irregular strip packing model, where a fixed width is used and the length of the parking layout is to be minimized. Aircraft are represented as non-convex polygons and are allowed to rotate in discrete intervals. The concept of the no-fit polygon (NFP) is used in order to prevent overlap between aircraft. A tabu search algorithm with an adaptive tabu list is proposed in order to optimize the sequence and orientations in which the aircraft are placed onto the placement area using a bottom-left (BL) placement strategy. In order to evaluate the effectiveness of the proposed algorithm, several instances are created and tested using computational experiments.