DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2024.3

Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm

Authors: Jenny Enerbäck, Lukas Eveborn, and Elina Rönnberg

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract

The elementary shortest path problem with resource constraints (ESPPRC) is a common problem that often arises as a pricing problem when solving vehicle routing problems with a column generation approach. One way of solving the ESPPRC is to use a labeling algorithm. In this paper, we focus on how different bounding strategies for labeling algorithms can be adapted and strengthened for the ESPPRC that arises from the Electric Vehicle Routing Problem with Time Windows and Piecewise Linear Recharging function (EVRPTW-PLR). We present a new completion bound method that takes charging times into account, and show how the completion bound can be combined with ng-routes. Computational experiments show that the new completion bound combined with ng-routes significantly improves the performance compared to a basic labeling algorithm.

Cite as

Jenny Enerbäck, Lukas Eveborn, and Elina Rönnberg. Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{enerback_et_al:OASIcs.ATMOS.2024.3,
  author =	{Enerb\"{a}ck, Jenny and Eveborn, Lukas and R\"{o}nnberg, Elina},
  title =	{{Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{3:1--3:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.3},
  URN =		{urn:nbn:de:0030-drops-211911},
  doi =		{10.4230/OASIcs.ATMOS.2024.3},
  annote =	{Keywords: ESPPRC, EVRP, Bounding, Labeling Algorithm}
}

Search Results

Documents authored by Eveborn, Lukas

Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message