Highlights Trackable column generation method for large-sized flight-to-gate assignment problems. Use of submodularity in column generation in solving pricing problems. Combination of exact algorithms and approximation algorithms in solving pricing problems.

    Abstract In this paper, we provide a column generation-based approach for solving the airport flight-to-gate assignment problem, where the goal is to minimize the on-ground portion of arrival delays by optimally assigning each scheduled flight to a compatible gate. Specifically, we use a set covering formulation for the master problem and decompose the pricing problem such that each gate is the basis for an independent pricing problem to be solved for assignment patterns with negative reduced costs. We use a combination of an approximation algorithm based on the submodularity of the underlying set and dynamic programming algorithms to solve the independent pricing problems. To the best of our knowledge, this is the first use of submodularity property to efficiently solve pricing problems and improve the performance of column generation algorithm. We show that the dynamic programming algorithm is pseudo-polynomial when there are integer inputs. We also design and employ a rolling horizon method and block decomposition algorithm to solve large-sized instances. Finally, we perform extensive computational experiments to validate the performance of our approach.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Using submodularity within column generation to solve the flight-to-gate assignment problem


    Beteiligte:
    Li, Yijiang (Autor:in) / Clarke, John-Paul (Autor:in) / Dey, Santanu S. (Autor:in)


    Erscheinungsdatum :

    2021-05-07




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Robust flight gate assignment

    Jaehn, Florian | TIBKAT | 2008


    Robust flight-to-gate assignment using flight presence probabilities

    van Schaijk, Oscar R. P. / Visser, Hendrikus G. | Taylor & Francis Verlag | 2017

    Freier Zugriff

    Robust flight-to-gate assignment using flight presence probabilities

    van Schaijk, Oscar R. P | Online Contents | 2017


    Submodularity of optimal sensor placement for traffic networks

    Li, Ruolin / Mehr, Negar / Horowitz, Roberto | Elsevier | 2023


    Flight Gate Assignment with a Quantum Annealer

    Stollenwerk, Tobias / Lobe, Elisabeth / Jung, Martin | Deutsches Zentrum für Luft- und Raumfahrt (DLR) | 2019

    Freier Zugriff