The Integrated Aircraft Routing and Crew Pairing Problem: ILP Based Formulations

Minimization of cost is very important in airline as great profit is an important objective for

any airline system. One way to minimize the costs in airline is by developing an integrated

planning process. Airline planning consists of many difficult operational decision problems

including aircraft routing and crew pairing problems. These two sub-problems, though

interrelated in practice, are usually solved sequentially leading to suboptimal solutions. We

propose an integrated aircraft routing and crew pairing problem model, one approach to

generate the feasible aircraft routes and crew pairs, followed by three approaches to

solve the integrated model. The integrated aircraft routing and crew scheduling problem

is to determine a minimum cost aircraft routes and crew schedules while each flight leg is

covered by one aircraft and one crew. The first approach is an integer programming

solution method, the second formulation is developed in a way to lend itself to be used

efficiently by Dantzig Wolfe decomposition whereas the third one is formulated as a

Benders decomposition method. Encouraging results are obtained when tested on four

types of aircraft based on local flights in Malaysia for one week flight cycle.