Biased randomised iterated greedy search with local search for airline crew scheduling

Airline crew scheduling is a complex problem that is faced by airline companies. The crew scheduling problem is divided into two sub-problems: crew pairing and crew assignment. The crew pairing problem defines a sequence of flight legs of the same fleet which begins and ends at the same crew base location. Pairings are controlled by some complex constraints such as flying time restrictions, rest requirements of crew members, daily working hours of the crew and the connection time between two flights. The assignment problem assigns the pairings to crew members. Airline transportation frequently has to deal with disruptions caused by technical problems or weather conditions. This leads to delays between different resources such as aircrafts and crews. In this research, we propose to formulate the problem as a set partitioning model and using a heuristic method to generate the pairing flight schedules, assign the crew, and reschedule disrupted flights after assigning pairing schedules to crew by
swapping delayed flights with other flights, in order to minimize total flying time. The heuristic proposed is the Biased Randomised Iterated Greedy Algorithm with local search, which employs destruction and construction phases to generate the flight schedules. The destruction phase removes randomly some flight candidates, and the construction phase inserts new flights in the partial solution to build a complete solution. The biased randomisation is used in the construction phase to select the flights to insert in the partial solution; and local search is used to intensify the search around the complete solution generated. Experimentation with benchmark problem from of real-world flight schedule in Turkey with 38 flights, 58 flights, and 96 flights. The evaluation of the performance shows that the Biased Randomised Iterated Greedy with Local Search outperforms the results in the literature for this case study.