A Combined Optimization-Simulation Framework for Airline Crew Scheduling Under Uncertainty
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3111997Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Beskrivelse
Full text not available
Sammendrag
Denne masteroppgaven presenterer et optimerings-simuleringsrammeverk for å løse det generelle besetningsplanleggingsproblemet for flyselskaper under usikkerhet. Hensikten er å konstruere en besetningsplan som presterer godt under usikkerhet knyttet til avgangs- og ankomsttider for flygninger. For å oppnå dette utvikler vi et iterativ rammeverk som kombinerer optimering og simulering gjennom to optimeringsmodeller.
Flyselskapers planlegging av timeplan for besetningen er delt inn i to beslutninger; valg av pairinger og tildeling av pairinger til hvert enkelt medlem av besetningen. Disse beslutningene tas uker før besetningsplanen skal driftes. Usikkerheten avdekkes under selve driften, og kan i noen tilfeller føre til at flyselskaper må endre den opprinnelige besetningsplanen. Fase 1 av rammeverket genererer en planlagt besetningsplan der beslutningene om valg av paringer og tildeling av pairinger til besetningsmedlemmer utføres. Fase 2 evaluerer løsningene under usikkerhet ved hjelp av en omplanleggingsmodell og tilfeldig genererte flyforsinkelser. Ved å løse omplanleggingsproblemet flere ganger for hver løsning, kan vi simulere hvor godt hver løsning presterer under usikkerhet i drift målt i form av omplanleggingskostnader. En estimert usikkerhetskostnad assosieres med den planlagte besetningsplanen, noe som fører til at fase 1 av modellen genererer en ny besetningsplan i neste iterasjon av rammeverket. Denne prosessen gjentas til rammeverket har funnet en planlagt besetningsplan som er optimal under usikkerhet.
Videre implementerer vi flere forbedringer for å redusere kjøretiden til rammeverket. De viktigste forbedringene er at vi trekker ut flere løsninger i hver iterasjon og deretter evaluerer dem parallelt, samt at vi inkluderer symmetribrytende restriksjoner i optimeringsmodellen i fase 1. I tillegg introduserer vi en utvidelse av rammeverket hvor evalueringen av løsninger gjennomføres i to steg. Til tross for at vi klarer å redusere kjøretiden til rammeverket, konvergerer det ikke innenfor en rimelig tidsramme. Ved å analysere de beste løsningene generert av rammeverket ser vi likevel at løsningene som blir funnet ved hjelp av rammeverket, presterer betydelig bedre under usikkerhet enn de optimale deterministiske løsningene. This Master's thesis presents an optimization-simulation framework for a generalized tactical Airline Crew Scheduling Problem under uncertainty faced by airlines worldwide. The aim is to find airline crew schedules that perform well under uncertainty in operations with respect to the departure and arrival times of aircraft. To accomplish this, we develop an iterative feedback framework combining optimization and simulation through two optimization models.
The decision of airlines regarding crew scheduling is divided into pairings selection and crew assignment, taken weeks prior to the operation of the crew schedule. The uncertainty is revealed during the operation, which in turn may require airlines to perform rescheduling of the original crew schedule. Phase 1 of the solution framework generates crew schedules where the decisions regarding pairing selection and assignment of crew members are conducted. Phase 2 evaluates the solutions under uncertainty using a rescheduling model and randomly generated flight delays. By solving the rescheduling problem multiple times for each solution, we are able to simulate how well each solution performs under uncertainty in operations in terms of rescheduling costs. The expected cost of uncertainty for the planned crew schedule is then associated with the Phase 1 solution in the next iteration of the framework, prompting the Phase 1 model to create a different schedule. This process is repeated until the framework terminates with an estimated optimal solution under uncertainty.
Furthermore, we implement several improvements to reduce the runtime of the framework. Most notably we extract multiple solutions in each iteration and evaluate them in parallel, in addition to the introduction of symmetry-breaking constraints in the Phase 1 optimization model. Additionally, we propose a two-step evaluation approach as an expansion to the framework. Despite the fact that our effort to reduce the runtime of the framework resulted in a substantial reduction in runtime, the framework did not reach convergence within a reasonable amount of time. Nonetheless, valuable insights were obtained by analyzing the best solutions generated by the framework. We found that these solutions consistently outperformed the deterministic approach, indicating an increase in robustness related to performance under uncertainty in operations.