Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows

By Stefan Røpke, Jean-François Cordeau. Transportation Science, 2009

514 citations recorded by the source corpus.

In the pickup and delivery problem with time windows vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and nonelementary shortest path problem. Valid inequalities are added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the pickup and delivery problem with time windows are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm.

Subfields: Automotive Engineering, Building and Construction, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/c313fd0b1c719eda52561d63610691e0c2bfa171

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Building and Construction

In Industrial and Manufacturing Engineering

Citations in the corpus

The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations (2016, unknown): “Algorithm 1: Pseudo code of a label setting algorithm for the ESPPTWRS (similar to Ropke and Cordeau (2009)).”
Finding Optimal Solutions for Vehicle Routing Problem with Pickup and Delivery Services with Time Windows: A Dynamic Programming Approach Based on State-space-time Network Representations (2015, methodology): “Ropke et al. (2007) presented a branch-and-cut algorithm to minimize the total routing cost, based on a two-index formulation.”
Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care (2013, unknown): “Parragh, et al., 2010) designed simulated annealing, genetic algorithm, adaptive large neighborhood search heuristic, and variable neighborhood search heuristic for solving the PDPTW. Extensive review of the PDPTW literature is out of the scope of in this paper and interested readers are referred to”
Static pickup and delivery problems: a classification scheme and survey (2007, methodology): “Recently, a branch-andcut-and-price algorithm for the VRPPDTW was proposed by Ropke and Cordeau (2007) .”