Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies

Christian Tilk, Michael Drexl, Stefan Irnich

Publications: Contribution to journalArticlePeer Reviewed

Abstract

This paper considers vehicle routing problems (VRPs) with multiple resource interdependencies and addresses the development and computational evaluation of an exact branch-and-price-and-cut algorithm for their solution. An interdependency between two resources means that the two resource consumptions influence one another in such a way that a tradeoff exists between them. This impacts the feasibility and/or the cost of a solution. The subproblem in branch-and-price-and-cut procedures for VRPs is very often a variant of the shortest-path problem with resource constraints (SPPRC). For the exact solution of many SPPRC variants, dynamic-programming based labeling algorithms are predominant. The tradeoffs in problems with multiple resource interdependencies, however, render the application of labeling algorithms unpromising. This is because complex data structures for managing the tradeoff curves are necessary and only weak dominance criteria are possible, so that the labeling algorithm becomes almost a pure enumeration. Therefore, we propose to solve also the SPPRC subproblem with branch-and-price-and-cut. This results in a two-level, nested branch-and-price-and-cut algorithm. We analyze different variants of the algorithm to enable the exchange of columns and also rows between the different levels. To demonstrate the computational viability of our approach, we perform computational experiments on a prototypical VRP with time windows, minimal and maximal delivery quantities for each customer, a customer-dependent profit paid for each demand unit delivered, and temporal synchronization constraints between some pairs of customers. In this problem, tradeoffs exist between cost and load and between cost and time.

Original languageEnglish
Pages (from-to)549-565
Number of pages17
JournalEuropean Journal of Operational Research
Volume276
Issue number2
DOIs
Publication statusPublished - 16 Jul 2019
Externally publishedYes

Austrian Fields of Science 2012

  • 101015 Operations research

Keywords

  • Branch-and-price-and-cut
  • Nested decomposition
  • Routing
  • Synchronization
  • Vehicle routing

Fingerprint

Dive into the research topics of 'Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies'. Together they form a unique fingerprint.

Cite this