A linear mixed-integer programming approach based on an event-activity network for personalized airline crew scheduling

Schön, Cornelia ; Krömer, Marius Magnus

Document Type: Conference presentation
Year of publication: 2023
Conference title: AGIFORS Crew Management Study Group Meeting
Location of the conference venue: Santiago, Chile
Date of the conference: 22.-24.05.2023
Related URLs:
Publication language: English
Institution: Business School > Service Operations Management (Schön 2014-)
Subject: 330 Economics
Abstract: We present an arc-based linear mixed-integer programming (MIP) approach to personalized airline crew scheduling that integrates the commonly sequential steps of crew pairing and crew assignment. In the sequential approach, global optimality can hardly be achieved, and crew preferences are considered only in the second step where the flexibility to take crew desires into account is very limited. Therefore, increasing attention has been paid to the integration of crew pairing and assignment in recent years, and a few promising path-based approaches have been developed; as centerpiece they embed column generation (CG) into a heuristic branch-and-bound search in a reduced, single-branch search tree. However, the CG subproblems are still hard to solve, and the CG master problem often suffers from degeneracy such that dynamic constraint aggregation techniques need to be applied. Our arc-based model is based on an event-activity network in time and space, where flight legs and other activities are directly assigned to individual crew members, taking crew preferences (e.g., for vacation days, flights, etc.) and all common regulatory rules for flight time limitations into account. Despite these complexities, our MIP formulation still allows to preserve linearity of the relaxation, even if sophisticated and originally non-linear cost functions (e.g., including cost terms for (not) flying, waiting and deadheads) commonly used in North American markets are considered as an objective. The model can be solved exactly for small instances with standard solvers, and we propose a rolling-planning heuristic for solving medium- to large-sized instances. Our approach can be used as a stand-alone alternative or as a complement to existing approaches, e.g., for generating good starting solutions for CG-based methods. Numerical experiments with published test instances show that our approach is promising in terms of solution time and quality.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item