A robust crew pairing based on multi-agent Markov decision processes

Airline scheduling is a real challenge in the context of the airline industry; this includes a lot of planning and operational decision problems and deals with a large number of interdependent resources. A prominent problem in airline scheduling is crew scheduling, specially pairings or Tour-of-Duty planning problem. The objective is to ensure optimal allocation of crews to flights by specifying the set of pairings that minimize the planned cost. The widely used algorithms assume no disruptions. However, airline operations often undergo stochastic disturbances that have to be taken into account in order to minimize the real operating cost. Recently, great interest has been given to robust crew scheduling with consideration of the stochastic nature of disturbances like technical breakdowns or bad weather conditions. In this paper, we develop a stochastic model of crew pairing problem based on Multi-agent Markov Decision Processes (MMDP); thus, the problem will be treated as finding the optimal policy to adopt in stochastic cases of disturbances. Also, a computational study is conducted to ensure validity of our proposed model. © 2014 IEEE.