A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows

By Russell W. Bent, Pascal Van Hentenryck. Computers & Operations Research, 2003

302 citations recorded by the source corpus.

This paper presents a two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows and multiple vehicles (PDPTW). The first stage uses a simple simulated annealing algorithm to decrease the number of routes, while the second stage uses LNS to decrease total travel cost. Experimental results show the effectiveness of the algorithm which has produced many new best solutions on problems with 100, 200, and 600 customers. In particular, it has improved 47% and 76% of the best solutions on the 200 and 600-customer benchmarks, sometimes by as much as 3 vehicles. These results further confirm the benefits of two-stage approaches in vehicle routing. They also answer positively the open issue in the original LNS paper, which advocated the use of LNS for the PDPTW and argue for the robustness of LNS with respect to side-constraints.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/7344087c7883c4089721e58262cc963d98216f48

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 Industrial and Manufacturing Engineering

Citations in the corpus

An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows (2006, background): “The general idea is to remove requests that are somewhat similar, as we expect it to be reasonably easy to shufﬂe similar requests around and thereby create new, perhaps better solutions.”
Static pickup and delivery problems: a classification scheme and survey (2007, methodology): “A two-stage heuristic for the VRPPDTW was developed by Bent and Van Hentenryck (2006) .”