2026-07-27T17:10:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21191 2024-10-07T04:59:11Z ddc:004 open_access

Pricing for the EVRPTW with Piecewise Linear Charging by a Bounding-Based Labeling Algorithm Enerbäck, Jenny Eveborn, Lukas Rönnberg, Elina ESPPRC EVRP Bounding Labeling Algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jenny Enerbäck and Lukas Eveborn and Elina Rönnberg 2024 Is Part Of OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2024.3 urn:nbn:de:0030-drops-211911 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode