|
A linear mixed-integer programming approach based on an event-activity network for personalized airline crew scheduling
Schön, Cornelia
;
Krömer, Marius Magnus
|
Dokumenttyp:
|
Präsentation auf Konferenz
|
|
Erscheinungsjahr:
|
2023
|
|
Veranstaltungstitel:
|
AGIFORS Crew Management Study Group Meeting
|
|
Veranstaltungsort:
|
Santiago, Chile
|
|
Veranstaltungsdatum:
|
22.-24.05.2023
|
|
Verwandte URLs:
|
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Betriebswirtschaftslehre > Service Operations Management (Schön 2014-)
|
|
Fachgebiet:
|
330 Wirtschaft
|
|
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.
|
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
