Solving a manpower scheduling problem for airline catering using metaheuristics
Ho and Leung (2010) study a manpower scheduling problem with job time-windows and job-skills compatibility constraints. Their study is motivated by airline in-flight catering operations, where airline meals must be delivered and stowed on the aircraft on the tarmac during a very tight time-window. The service of each aircraft must be realized by a team whose skills are compatible with the particular configuration of the aircraft. In addition, the service must also be completed within the flight’s time window and the team’s shift hours. The overall objective is to maximize the number of feasibly assigned aircrafts and to create a balanced feasible working schedule for each of the teams. A working schedule for each team consists of a number of trips the team has to make during their shift. For each trip the team leaves the production unit, arrives at the tarmac to service a number of aircrafts, and finally returns to the production unit.
The authors study the basic manpower scheduling problem and two variants of it. In the basic manpower scheduling problem, an aircraft is serviced by one team only and each team serves only one aircraft in each trip. The other two modes of operation are (i) a team may service two aircrafts in one trip; (ii) the service of an aircraft may be shared between two teams.
Ho and Leung (2010) show how this problem can be solved using tabu search. The neighborhood structure used is the insertion move, where it is adapted to conform with different variants of the problem. In order to explore a wider part of the solution space, frequently made moves are penalized. As feasibility may be difficult to achieve, search in infeasible regions of the solution space is also allowed to be conducted.
Computational experiments have been conducted on a set of real-life instances and on a set of generated test instances. Experimental results show that the tabu search heuristic generates good solutions that satisfy the balance requirements using only 7-19 seconds of computing time. Experiments also show that the tabu search heuristic outperforms the simulated annealing heuristic that was implemented for comparison purposes. The results also indicate that the variant of allowing the service of an aircraft to be shared between two teams seems to be a better choice as a mode of operations.
References
Ho, S. C. and Leung, J. M. Y., “Solving a manpower scheduling problem for airline catering using metaheuristics”, European Journal of Operational Research, 202(3): 903-921, 2010.