EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Branch-price-and-cut for the vehicle routing problem with simultaneous delivery and pickup, time windows, and load-dependent cost

Carolin Hasse, Stefan Irnich

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →