The airline crew pairing (ACP) problem is one of the most challenging problems in airline operations. It aims to decide the optimal connections among pairs of flights assigned to flight crews. However, the number of connections grows exponentially with the increasing number of flights. Conventional approaches usually follow a two-stage method, i.e., divide-and-conquer. The flight sequences (pairings) spanning multiple days are firstly generated for each crew. Then, the best pairing set is chosen based on minimum operational costs. When the number of flights is large, it becomes too difficult to generate all feasible pairings and find the optimum. In order to solve large-scale ACP problems efficiently, we propose a novel iterative optimization framework based on monte carlo tree search (MCTS). Thus, the speed of pairing generation and solution accuracy can be improved. To evaluate the performance of the proposed method, we conduct experiments on different scales of real-world instances provided by airline companies. The empirical results show that the proposed approach is capable of producing high-quality solutions, especially in large-scale instances.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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


    Beteiligte:
    Li, Yuewen (Autor:in) / Wang, Xiaoling (Autor:in) / Kang, Qi (Autor:in) / Fan, Zheng (Autor:in) / Yao, Shuaiyu (Autor:in)


    Erscheinungsdatum :

    2023-05-01


    Format / Umfang :

    8161462 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    On Large-Scale Airline Crew Pairing Generation

    Aggarwal, Divyam / Saxena, Dhish Kumar / Emmerich, Michael et al. | IEEE | 2018


    An adaptive greedy heuristic for large scale airline crew pairing problems

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


    A VRP-based Approach for the Airline Crew Pairing Problem

    Li, Zhuang / Wang, Shuo / Li, WeiDong et al. | IEEE | 2022


    Robust Airline Crew Pairing: Move-up Crews

    Shebalov, Sergey | Online Contents | 2006


    Robust Airline Crew Pairing: Move-up Crews

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