A heuristic approach to the deterministic and stochastic air crew pairing problem
Date
2019-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH SUMMARY : The air crew pairing problem is a subproblem of the integrated airline management problem and one of the more complicated problems to solve in the field of transport logistics.
There have been various approaches both in literature and in industry for solving the deterministic crew pairing problem. More recently there have been developments in solving stochastic instances of the problem. This study presents a heuristic approach to solve the crew pairing problem, for the one day planning horizon. An exact solution approach is also presented to generate the entire feasible region and produce the optimal solution, however this approach is computationally tasking for larger problem sets. To address the need to generate solutions in reasonable time for industry requirements, two heuristic solution approaches are presented; the first is based on a greedy tree search heuristic and the second is based on a random tree search with logical constraints to ensure feasibility in all solutions.
A comparison is made with results for a benchmark study in literature in order to test the performance of the algorithms used in the deterministic crew pairing problem. The results are competitive for larger problem sets. Sensitivity analysis is also performed to generate -"what-if" scenarios to test for algorithm robustness. The two heuristic approaches are also adjusted to solve the stochastic crew pairing problem, where weather delays are introduced in the flight network. The results illustrate that in most network problems given a delay as
applied from a given distribution, an airline would need to employ additional crew to service a network of scheduled flights. The results also indicate that a greedy based algorithm performs better than a completely random monte carlo approach for both the deterministic and stochastic crew pairing problems.
AFRIKAANSE OPSOMMING : Die skedulering en toekenning van bemanning aan vlugte is ’n subprobleem in die geïntegreerde lugrederyskeduleringsprobleem en ook een van die meer ingewikkelde probleme om op te los in vervoer logistiek. Daar is verskeie benaderings, beide in die literatuur en in die bedryf, vir die oplossing van ‘n deterministiese bemanningskeduleringsprobleem. Daar is onlangs ook verwikkelinge in die oplossing van stogastiese gevalle van die probleem gewees. Hierdie studie bied ’n heuristiese benadering tot die bemanningskeduleringsprobleem vir ‘n een dag beplanningshorison. ’n Eksakte oplossingsbenadering word ook aangebied deur die hele toelaatbare gebied te genereer en die optimale oplossing te vind, maar hierdie benadering is berekeningintensief vir groter probleemversamelings. Om die behoefte aan te spreek om oplossings vir die industrie in ‘n redelike tyd te vind, word twee heuristiese benaderings aangebied; die eerste is gebaseer op ’n gulsige boom soektog heuristiek en die tweede is gebaseer op ’n ewekansig lukrake boom soektog met logiese beperkinge om die toelaatbaarheid van alle oplossings te verseker. Resultate word vergelyk met die van ’n maatstaf studie in die literatuur om die gehalte-prestasie van die algoritmes te bepaal wat gebruik word in die deterministiese bemanningskeduleringsprobleem. Die algoritmes is mededingend vir groter probleem stelle. Sensitiwiteitsanalise word ook uitgevoer om verskillende scenarios te toets om die robuustheid van die algoritmes te bepaal. Die twee heuristiese benaderings word ook aangepas om die stogastiese probleem op te los, waar vertragings lukraak in die vlug netwerk veroorsaak word as gevolg van weerstoestande.
AFRIKAANSE OPSOMMING : Die skedulering en toekenning van bemanning aan vlugte is ’n subprobleem in die geïntegreerde lugrederyskeduleringsprobleem en ook een van die meer ingewikkelde probleme om op te los in vervoer logistiek. Daar is verskeie benaderings, beide in die literatuur en in die bedryf, vir die oplossing van ‘n deterministiese bemanningskeduleringsprobleem. Daar is onlangs ook verwikkelinge in die oplossing van stogastiese gevalle van die probleem gewees. Hierdie studie bied ’n heuristiese benadering tot die bemanningskeduleringsprobleem vir ‘n een dag beplanningshorison. ’n Eksakte oplossingsbenadering word ook aangebied deur die hele toelaatbare gebied te genereer en die optimale oplossing te vind, maar hierdie benadering is berekeningintensief vir groter probleemversamelings. Om die behoefte aan te spreek om oplossings vir die industrie in ‘n redelike tyd te vind, word twee heuristiese benaderings aangebied; die eerste is gebaseer op ’n gulsige boom soektog heuristiek en die tweede is gebaseer op ’n ewekansig lukrake boom soektog met logiese beperkinge om die toelaatbaarheid van alle oplossings te verseker. Resultate word vergelyk met die van ’n maatstaf studie in die literatuur om die gehalte-prestasie van die algoritmes te bepaal wat gebruik word in die deterministiese bemanningskeduleringsprobleem. Die algoritmes is mededingend vir groter probleem stelle. Sensitiwiteitsanalise word ook uitgevoer om verskillende scenarios te toets om die robuustheid van die algoritmes te bepaal. Die twee heuristiese benaderings word ook aangepas om die stogastiese probleem op te los, waar vertragings lukraak in die vlug netwerk veroorsaak word as gevolg van weerstoestande.
Description
Thesis (MSc)--Stellenbosch University, 2019.
Keywords
Heuristic, Flight crews -- Mathematical models, Scheduling -- Mathematical models, Airlines -- Personnel management -- Mathematical models, Mathematical optimization, UCTD