A general heuristic for vehicle routing problems

By David Pisinger, Stefan Røpke. Computers & Operations Research, 2007

1,546 citations recorded by the source corpus.

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP). All problem variants are transformed into a rich pickup and delivery model and solved using the adaptive large neighborhood search (ALNS) framework presented in Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, to appear]. The ALNS framework is an extension of the large neighborhood search framework by Shaw [Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98, Fourth international conference on principles and practice of constraint programming, Lecture notes in computer science, vol. 1520, 1998. p. 417-31] with an adaptive layer. This layer adaptively chooses among a number of insertion and removal heuristics to intensify and diversify the search. The presented approach has a number of advantages: it provides solutions of very high quality, the algorithm is robust, and to some extent self-calibrating. Moreover, the unified model allows the dispatcher to mix various variants of VRP problems for individual customers or vehicles. As we believe that the ALNS framework can be applied to a large number of tightly constrained optimization problems, a general description of the framework is given, and it is discussed how the various components can be designed in a particular setting. The paper is concluded with a computational study, in which the five different variants of the vehicle routing problem are considered on standard benchmark tests from the literature. The outcome of the tests is promising as the algorithm is able to improve 183 best known solutions out of 486 benchmark tests. The heuristic has also shown promising results for a large class of vehicle routing problems with backhauls as demonstrated in Ropke and Pisinger [A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 2004, to appear].

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/13b1a67a0505bb15dee0af2000518fa08c73ee4f

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

A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems (2012, background): “of Pisinger and Ropke (2007) (PR) for the MDVRP.”
The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations (2016, positive): “A general introduction to LNS and its variants and extensions can be found in Pisinger and Ropke (2010). An outline of our approach is shown in Algorithm 1.”
A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows (2013, methodology): “…compares the average and best results, as well as the average run time of HGSADC with state-of-the-art methods for each problem: • PisR: ALNS of Pisinger and Ropke (2007) • LZ: Two-phase ejections chains and iterated local search of Lim and Zhang (2007) • PDR: Branch-and-price based LNS of…”
An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones (2019, methodology): “The negative savings indicate that the heuristic for the truck-only case (Pisinger and Ropke (2007)) is superior to the VRP-D heuristic when the VRP-D heuristic cannot make use of its drones.”
Industrial aspects and literature survey: Fleet composition and routing (2010, background): “Also, a trend towards a more holistic approach can be seen in the recent VRP literature [40, 64, 78, 116].”
An artificial bee colony algorithm for the capacitated vehicle routing problem (2011, background): “After that, each onlooker finds a food source near its selected food source (using a neighborhood operator) and calculates the nectar amount of the neighbor food source.”
An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics (2012, methodology): “ALNS was first developed by Ropke and Pisinger (2006) for the pickup and delivery problem and these authors later solved several variants of the vehicle routing problem with a general algorithm based on the same methodology (Pisinger and Ropke (2007)).”
Recent advances in selection hyper-heuristics (2020, methodology): “Vehicle routing problems (VRPs) are an area in which selection hyper-heuristic methods have been particularly successful, with the Adaptive Very Large Neighbourhood Search (AVLNS) hyper-heuristic of Pisinger and Ropke (2007) achieving state-of-the-art results for multiple VRP variants back in 2007.”
An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows (2006, background): “In the papers by Pisinger and Ropke (2005) and Ropke and Pisinger (2006), it is shown how the heuristic presented in this paper can be extended to solve a variety of vehicle routing problems?for example the VRPTW, the mul tidepot vehicle routing problem, and the vehicle routing problem with backhaul”
What you should know about the vehicle routing problem (2007, methodology): “In adaptive large neighbourhood search (Pisinger and Ropke [47]), several insertion and removal heuristics are applied.”
The time-dependent vehicle routing problem with soft time windows and stochastic travel times (2014, positive): “The scheme of the ALNS method is introduced by Pisinger and Ropke (2005, 2007), and Ropke and Pisinger (2006) to handle various types of the routing problems.”
A Classification of Hyper-heuristic Approaches (2010, methodology): “deluge [38] and simulated annealing [4, 23, 50].”