Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost
European Journal of Operational Research · 2026-06
DOI: 10.1016/j.ejor.2026.06.030 ↗Kurz gefasst
Fachartikel in der Zeitschrift European Journal of Operational Research, 2026-06. Verfasst von Carolin Hasse und 1 weiteren Autor:innen. Die Arbeit nennt 72 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Johannes Gutenberg-Universität Mainz.
Abstract (Originalsprache)
The vehicle routing problem with load-dependent cost is an extension of the classical capacitated vehicle routing problem in which the cost of traveling along an arc is dependent on the load carried by the vehicle. For the benefit of generalization, this work considers the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost (VRPSDPTW-LDC). We utilize both continuous and discontinuous monotonically non-decreasing load-dependent cost functions. These cost structures are justified by real-life applications: First and foremost, transportation cost rises in load due to increasing fuel cost. In addition, cost functions may also show discontinuities due to toll-by-weight schemes, weight restricted passage, and lift axles that may be raised when the vehicle is empty or lightly loaded, therefore decreasing tire wear. We employ a fully equipped branch-price-and-cut algorithm to solve the VRPSDPTW-LDC. A major complication in its development is the consistent handling of the load-dependent cost in the column-generation subproblem when solved by bidirectional labeling algorithms. Indeed, in the VRPSDPTW-LDC, the precise load on board is not known when a partial path is constructed. We provide a unifying description of the associated resource extension function for forward and backward labeling. In several computational experiments, we analyze algorithmic components of the branch-price-and-cut algorithm, and give managerial insights on the impact of the cost structure on key metrics such as total cost, the number of routes, and the average load carried in an optimal solution.
Förderung
- Johannes Gutenberg-Universität Mainz
Zitieren
APA
Hasse, C., & Irnich, S. (2026). Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2026.06.030
Vancouver
Hasse C, Irnich S. Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost. European Journal of Operational Research. 2026. doi:10.1016/j.ejor.2026.06.030
BibTeX
@article{Hasse2026,
author = {Hasse, Carolin and Irnich, Stefan},
title = {Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost},
journal = {European Journal of Operational Research},
year = {2026},
doi = {10.1016/j.ejor.2026.06.030}
}
EUVIMED