Subproblem separation is a common strategy for the acceleration of the logic-based Benders' decomposition (LBBD). However, it has only been applied to problems with an inherently separable subproblem structure. This paper proposes a new method to separate the subproblem using the connected components algorithm. The subproblem separation is applied to the vehicle routing problem with local congestion (VRPLC). Accordingly, new Benders' cuts are derived for the new subproblem formulation. The computational experiments evaluate the effectiveness of subproblem separation for different methods applying new cuts. It is shown that subproblem separation significantly benefits the LBBD scheme.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion


    Beteiligte:
    Saken, Aigerim (Autor:in) / Maher, Stephen J. (Autor:in) / Frigioni, Daniele (Herausgeber:in) / Schiewe, Philine (Herausgeber:in)


    Erscheinungsdatum :

    2023-08-31


    Format / Umfang :

    12 pages , 689102 byte


    Anmerkungen:

    OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 16:1-16:12





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch






    Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling

    Cordeau, J.-F. / Stojkovic, G. / Soumis, F. et al. | British Library Online Contents | 2001




    Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

    Kolokolov, A. / Kosarev, N. | British Library Online Contents | 2006