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.
Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion
2023-08-31
12 pages , 689102 byte
OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 16:1-16:12
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
British Library Online Contents | 2001
|Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
Online Contents | 2001
|Taylor & Francis Verlag | 2021
|Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem
British Library Online Contents | 2006
|