2026-07-24T14:19:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18777 2024-03-06T10:32:15Z ddc:004 open_access

Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion Saken, Aigerim Maher, Stephen J. logic-based Benders' decomposition vehicle routing subproblem separation connected components 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aigerim Saken and Stephen J. Maher 2023 Is Part Of OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2023.16 urn:nbn:de:0030-drops-187771 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode