Branch-Price-and-Cut for the Vehicle Routing Problem With Simultaneous Delivery and Pickup, Time Windows, and Load-Dependent Cost

Carolin Hasse () and Stefan Irnich ()
Additional contact information
Carolin Hasse: Johannes-Gutenberg University, Germany
Stefan Irnich: Johannes-Gutenberg University, Germany

No 2509, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: 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 columngeneration 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.

Keywords: routing; load-dependent cost; simultaneous delivery and pickup; branch-price-and-cut; dynamic-programming labeling algorithm (search for similar items in EconPapers)
Pages: 23 pages
Date: 2025-11-06
New Economics Papers: this item is included in nep-tre
References: Add references at CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2509.pdf first version, 2025 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:2509

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().