|
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.
|
 
 Search Authors in
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
|
