Publication

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

Schrotenboer, A. H., Ursavas, E. & Vis, I., 2019, In : Transportation Science. 53, 4, p. 1001-1022 22 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard

Documents

DOI

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
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

Download statistics

No data available

ID: 66428307