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.


    Access

    Download


    Export, share and cite



    Title :

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


    Contributors:


    Publication date :

    2023-08-31


    Size :

    12 pages , 689102 byte


    Remarks:

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





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English






    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