Multi-commodity flow model approach to a crew rostering problem

Abstract

An airline crew rostering problem is a large-scaled and complex optimization problem that assigns crew members to the flight duties while satisfying agreements with the labor union, the government regulations, the carrier’s own policies, and other requirements. The traditional crew rostering problem considers only minimizing the total per-diem in order to reduce the airline expense. This paper presents the crew rostering problem for the international flights of Thai Airways. We propose a 0-1 multi-commodity flow problem whose objective function is to minimize the sum of the maximum of the per-diems and workloads among the crew members. Various test cases are generated from Thai Airways data set and solved by using the commercial optimizer IBM ILOG CPLEX. From the experiment results, the optimizer can solve the multi-commodity flow problems of small and medium sizes within 60 hours. However, the solutions give poor distribution of the per-diems and workloads among crew members where the standard deviations of the per-diems ranging from 1985.415 to 3855.295 and standard deviations of the workloads ranging from 8.7595 to 28.22391. The optimizer cannot solve the problems of large size within 60 hours.