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

Albert H. Schrotenboer (), Evrim Ursavas () and Iris F. A. Vis ()
Additional contact information
Albert H. Schrotenboer: Department of Operations, Faculty of Economics and Business, University of Groningen, Nettelbosje 29747 AE Groningen, Netherlands
Evrim Ursavas: Department of Operations, Faculty of Economics and Business, University of Groningen, Nettelbosje 29747 AE Groningen, Netherlands
Iris F. A. Vis: Department of Operations, Faculty of Economics and Business, University of Groningen, Nettelbosje 29747 AE Groningen, Netherlands

Transportation Science, 2019, vol. 53, issue 4, 1001–1022

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.

Keywords: column generation; column-dependent constraints; pickup and delivery; multicommodity; branch-and-price-and-cut; offshore wind (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0880 (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:inm:ortrsc:v:53:y:2019:i:4:p:1001-1022

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().