Crew operating cost is the second largest cost component of an airlines’ total operating cost (second only to the fuel cost) and even marginal cost savings here may amount to millions of dollars, annually. Towards it, a crew needs to be efficiently assigned a sequence of flights starting and ending at the same crew base (a crew pairing). The challenge for an airline is to generate crew pairings which completely cover a finite set of flights over a particular time window, with minimum cost, while satisfying multiple legality constraints linked to airlines’ own regulations, labor laws, and government safety rules etc. The success in solving the associated constrained optimization problem largely depends on solving NP-complete subproblems, linked to the generation of a feasible solution (legal crew pairings covering all flights) and generation of pairings with reasonable cost-quality. In an attempt to address these subproblems in a computationally- and time-efficient manner, the contributions of this paper relate to the use and characterization of network structure for pairing generation; enhancement of the graph traversal algorithm, namely Depth-first Search (DFS); its parallel implementation on multiple processors of a single computer; and embedding of cost considerations during pairing generation itself towards boosting the optimizer’s performance subsequently. The utility of the cited contributions is demonstrated on medium $( \sim 2000$ flights) and large $(\sim 4000$ flights) data sets provided by GE Aviation.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    On Large-Scale Airline Crew Pairing Generation


    Contributors:


    Publication date :

    2018-11-01


    Size :

    235930 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    An adaptive greedy heuristic for large scale airline crew pairing problems

    Zeren, Bahadır / Özcan, Ender / Deveci, Muhammet | Elsevier | 2023


    Robust Airline Crew Pairing: Move-up Crews

    Shebalov, S. / Klabjan, D. | British Library Online Contents | 2006


    Robust Airline Crew Pairing: Move-up Crews

    Shebalov, Sergey | Online Contents | 2006


    An MCTS-Based Solution Approach to Solve Large-Scale Airline Crew Pairing Problems

    Li, Yuewen / Wang, Xiaoling / Kang, Qi et al. | IEEE | 2023


    Airline crew pairing with fatigue: Modeling and analysis

    Yildiz, Burak C | Online Contents | 2017