A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems

Albert H. Schrotenboer, Evrim Ursavas, Iris Vis

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
622 Downloads (Pure)

Abstract

We study a multicommodity, multiperiod, resource-constrained pickup-and-delivery problem inspired by the short-term planning of maintenance services at offshore wind farms. To begin a maintenance service, different types of relatively scarce servicemen need to be delivered (transported) to the service locations. We develop resource-exceeding route (RER) inequalities, which are inspired by knapsack cover inequalities, to model the scarcity of servicemen. In addition to a traditional separation approach, we present a column-dependent constraints approach so as to include the RER inequalities in the mathematical formulation. An alternative pricing strategy is developed to correctly include the column-dependent constraints. The resulting approach is broadly applicable to any routing problem that involves a set of scarce resources. We present a branch-and-price-and-cut algorithm to compare both approaches that include RER inequalities. The branch-and-price-and-cut algorithm relies on efficiently solving a new variant of the elementary resource-constrained shortest-path problem, using a tailored pulse algorithm developed specifically to solve it. Computational experiments show that the RER inequalities significantly tighten the root node relaxations. The column-dependent constraints approach then searches the branch-and-bound tree more effectively and appears to be competitive with the traditional separation procedure. Both approaches are able to solve instances of up to 92 nodes over 21 periods to optimality.

Original languageEnglish
Pages (from-to)1001-1022
Number of pages22
JournalTransportation Science
Volume53
Issue number4
DOIs
Publication statusPublished - 2019

Keywords

  • column generation
  • column-dependent constraints
  • pickup and delivery
  • multicommodity
  • branch-and-price-and-cut
  • offshore wind
  • VEHICLE-ROUTING PROBLEM
  • SHORTEST-PATH PROBLEM
  • COLUMN-GENERATION
  • MAINTENANCE
  • OPTIMIZATION
  • INEQUALITIES
  • PROGRAMS

Fingerprint

Dive into the research topics of 'A Branch-and-Price-and-Cut Algorithm for Resource-Constrained Pickup and Delivery Problems'. Together they form a unique fingerprint.

Cite this