DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2023.16

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

Authors: Aigerim Saken and Stephen J. Maher

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract

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.

Cite as

Aigerim Saken and Stephen J. Maher. Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saken_et_al:OASIcs.ATMOS.2023.16,
  author =	{Saken, Aigerim and Maher, Stephen J.},
  title =	{{Subproblem Separation in Logic-Based Benders' Decomposition for the Vehicle Routing Problem with Local Congestion}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{16:1--16:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.16},
  URN =		{urn:nbn:de:0030-drops-187771},
  doi =		{10.4230/OASIcs.ATMOS.2023.16},
  annote =	{Keywords: logic-based Benders' decomposition, vehicle routing, subproblem separation, connected components}
}

Search Results

Documents authored by Saken, Aigerim

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

Abstract

Cite as

Thanks for your feedback!

Could not send message