License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2023.16
URN: urn:nbn:de:0030-drops-187771
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18777/
Go to the corresponding OASIcs Volume Portal

Saken, Aigerim ; Maher, Stephen J.

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

pdf-format:
OASIcs-ATMOS-2023-16.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2023/18777},
  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}
}

Keywords: logic-based Benders' decomposition, vehicle routing, subproblem separation, connected components
Collection: 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)
Issue Date: 2023
Date of publication: 31.08.2023
Supplementary Material: Software (Source Code): https://git.exeter.ac.uk/as1392/subproblem-separation-in-lbbd

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI