Metaheuristics for Vehicle Routing Problems

This book is dedicated to metaheuristics as applied to vehicle routing problems. Several implementations are given as illustrative examples, along with applications to several typical vehicle routing problems. As a first step, a general presentation intends to make the reader more familiar with the related field of logistics and combinatorial optimization. This preamble is completed with a description of significant heuristic methods classically used to provide feasible solutions quickly, and local improvement moves widely used to search for enhanced solutions. The overview of these fundamentals allows appreciating the core of the work devoted to an analysis of metaheuristic methods for vehicle routing problems. Those methods are exposed according to their feature of working either on a sequence of single solutions, or on a set of solutions, or even by hybridizing metaheuristic approaches with others kind of methods.

Table of Contents:
Notations and Abbreviations ix Introduction  xiii Chapter 1. General Presentation of Vehicle Routing Problems 1 1.1. Logistics management and combinatorial optimization 1 1.1.1. History of logistics 2 1.1.2. Logistics as a science 5 1.1.3. Combinatorial optimization 5 1.2. Vehicle routing problems 6 1.2.1. Problems in transportation optimization 6 1.2.2. Vehicle routing problems in other contexts 7 1.2.3. Characteristics of vehicle routing problems 7 1.2.4. The capacitated vehicle routing problem 11 1.3. Conclusion 13 Chapter 2. Simple Heuristics and Local Search Procedures 15 2.1. Simple heuristics 16 2.1.1. Constructive heuristics 16 2.1.2. Two-phase methods 19 2.1.3. Best-of approach and randomization 22 2.2. Local search 23 2.2.1. Principle 23 2.2.2. Classical moves 24 2.2.3. Feasibility tests 25 2.2.4. General approach from Vidal et al 28 2.2.5. Multiple neighborhoods  30 2.2.6. Very constrained problems 33 2.2.7. Acceleration techniques 33 2.2.8. Complex moves 36 2.3. Conclusion 37 Chapter 3. Metaheuristics Generating a Sequence of Solutions 39 3.1. Simulated annealing (SA) 39 3.1.1. Principle 39 3.1.2. Simulated annealing in vehicle routing problems 40 3.2. Greedy randomized adaptive search procedure: GRASP 41 3.2.1. Principle 41 3.2.2. GRASP in vehicle routing problems 43 3.3. Tabu search 44 3.3.1. Principle 44 3.3.2. Tabu search in vehicle routing problems 45 3.4. Variable neighborhood search 47 3.4.1. Principle 47 3.4.2. Variable neighborhood search in vehicle routing problems 49 3.5. Iterated local search 50 3.5.1. Principle 50 3.5.2. Iterated local search in vehicle routing problems 52 3.6. Guided local search 54 3.6.1. Principle 54 3.6.2. Guided local search in vehicle routing problems 55 3.7. Large neighborhood search 56 3.7.1. Principle 56 3.7.2. Large neighborhood search in vehicle routing problems 58 3.8. Transitional forms 59 3.8.1. Evolutionary local search principle 59 3.8.2. Application to vehicle routing problems 60 3.9. Selected examples 61 3.9.1. GRASP for the location-routing problem 61 3.9.2. Granular tabu search for the CVRP 65 3.9.3. Adaptive large neighborhood search for the pickup and delivery problem with time windows 69 3.10. Conclusion 74 Chapter 4. Metaheuristics Based on a Set of Solutions 77 4.1. Genetic algorithm and its variants 77 4.1.1. Genetic algorithm 77 4.1.2. Memetic algorithm 79 4.1.3. Memetic algorithm with population management 79 4.1.4. Genetic algorithm and its variants in vehicle routing problems 80 4.2. Scatter search 82 4.2.1. Scatter search principle 82 4.2.2. Scatter search in vehicle routing problems 83 4.3. Path relinking 83 4.3.1. Principle  84 4.3.2. Path relinking in vehicle routing problems 85 4.4. Ant colony optimization 86 4.4.1. Principle 86 4.4.2. ACO in vehicle routing problems 89 4.5. Particle swarm optimization 89 4.5.1. Principle 89 4.5.2. PSO in vehicle routing problems 90 4.6. Other approaches and their use in vehicle routing problems 91 4.7. Selected examples 92 4.7.1. Scatter search for the periodic capacitated arc routing problem 92 4.7.2. PR for the muti-depot periodic VRP 97 4.7.3. Unified genetic algorithm for a wide class of vehicle routing problems 101 4.8. Conclusion 106 Chapter 5. Metaheuristics Hybridizing Various Components 109 5.1. Hybridizing metaheuristics  109 5.1.1. Principle 110 5.1.2. Application to vehicle routing problems 111 5.1.3. Selected examples 112 5.2. Matheuristics 122 5.2.1. Principle 123 5.2.2. Application to vehicle routing problems 124 5.2.3. Selected examples 128 5.3. Conclusion 144 Conclusion 145 Bibliography 149 Index 167