Otimização na reprogramação de transporte aéreo de passageiros para unidades marítimas por meio de heurísticas MIP

Abstract

In air passenger transport, events often occur that make it impossible to comply with the flight schedule planned for a certain period. In these situations, the Aircraft Recovery Problem (ARP) emerges, which involves rescheduling flights and reallocating aircraft to those flights. In this work, we treated an ARP in an oil and gas production company with an offshore operation that carries out, daily, via helicopters, the transportation of its employees and airport employees to maritime units, and vice versa . Therefore, we sought to: (i) develop Mixed Integer Programming (MIP) models to represent the problem, considering both the different optimization objectives pursued by the company (that is, minimizing flight delays in one day, the need for flight transfers to the next day due to unexpected events and the designation of helicopters for flights other than those already allocated in the schedule) and various practical restrictions of the company; (ii) develop MIP heuristics of the type Relax-and-fix and Fix-and-optimize that, when combined with a model formulated in (i), provide good quality results using little computational time. As for the models, five formulations were elaborated, and their validations and performance comparisons were performed using real and simulated instances provided by the company, selecting the formulation that provided the best solution within the time limit of one hour. In relation to MIP heuristics, different configurations were tested, using the same instances, to identify which would make it possible to provide better quality solutions. To solve the models and heuristics, a commercial optimization solver was used for the rescheduling of helicopter flights. Optimum solutions were obtained for part of the tested instances of the problem and, for those that could not be solved optimally, the settings for the heuristics were identified, which, among the tested ones, provided the best solutions comparatively. Thus, the results obtained demonstrate the notorious potential of the approaches proposed in this work to solve the evaluated ARP.