Metaheuristics for Vehicle Routing Problems

Nacima Labadie is Associate Professor with accreditation to supervise research (HDR) at the Industrial Systems Optimization Laboratory of the Charles Delaunay Institute at the University of Technology of Troyes in France. Her research mainly focuses on arc routing and team orienteering problems.Christian Prins is Full Professor at the Industrial Systems Optimization Laboratory of the Charles Delaunay Institute at the University of Technology of Troyes in France. His research focuses on the many variants of vehicle routing problems.Caroline Prodhon is Associate Professor with accreditation to supervise research (HDR) at the Industrial Systems Optimization Laboratory of the Charles Delaunay Institute at the University of Technology of Troyes in France. Her research focuses on location-routing problems.

• Notations and Abbreviations ix Introduction  xiiiChapter 1. General Presentation of Vehicle Routing Problems 11.1. Logistics management and combinatorial optimization 11.1.1. History of logistics 21.1.2. Logistics as a science 51.1.3. Combinatorial optimization 51.2. Vehicle routing problems 61.2.1. Problems in transportation optimization 61.2.2. Vehicle routing problems in other contexts 71.2.3. Characteristics of vehicle routing problems 71.2.4. The capacitated vehicle routing problem 111.3. Conclusion 13Chapter 2. Simple Heuristics and Local Search Procedures 152.1. Simple heuristics 162.1.1. Constructive heuristics 162.1.2. Two-phase methods 192.1.3. Best-of approach and randomization 222.2. Local search 232.2.1. Principle 232.2.2. Classical moves 242.2.3. Feasibility tests 252.2.4. General approach from Vidal et al 282.2.5. Multiple neighborhoods  302.2.6. Very constrained problems 332.2.7. Acceleration techniques 332.2.8. Complex moves 362.3. Conclusion 37Chapter 3. Metaheuristics Generating a Sequence of Solutions 393.1. Simulated annealing (SA) 393.1.1. Principle 393.1.2. Simulated annealing in vehicle routing problems 403.2. Greedy randomized adaptive search procedure: GRASP 413.2.1. Principle 413.2.2. GRASP in vehicle routing problems 433.3. Tabu search 443.3.1. Principle 443.3.2. Tabu search in vehicle routing problems 453.4. Variable neighborhood search 473.4.1. Principle 473.4.2. Variable neighborhood search in vehicle routing problems 493.5. Iterated local search 503.5.1. Principle 503.5.2. Iterated local search in vehicle routing problems 523.6. Guided local search 543.6.1. Principle 543.6.2. Guided local search in vehicle routing problems 553.7. Large neighborhood search 563.7.1. Principle 563.7.2. Large neighborhood search in vehicle routing problems 583.8. Transitional forms 593.8.1. Evolutionary local search principle 593.8.2. Application to vehicle routing problems 603.9. Selected examples 613.9.1. GRASP for the location-routing problem 613.9.2. Granular tabu search for the CVRP 653.9.3. Adaptive large neighborhood search for the pickup and delivery problem with time windows 693.10. Conclusion 74Chapter 4. Metaheuristics Based on a Set of Solutions 774.1. Genetic algorithm and its variants 774.1.1. Genetic algorithm 774.1.2. Memetic algorithm 794.1.3. Memetic algorithm with population management 794.1.4. Genetic algorithm and its variants in vehicle routing problems 804.2. Scatter search 824.2.1. Scatter search principle 824.2.2. Scatter search in vehicle routing problems 834.3. Path relinking 834.3.1. Principle  844.3.2. Path relinking in vehicle routing problems 854.4. Ant colony optimization 864.4.1. Principle 864.4.2. ACO in vehicle routing problems 894.5. Particle swarm optimization 894.5.1. Principle 894.5.2. PSO in vehicle routing problems 904.6. Other approaches and their use in vehicle routing problems 914.7. Selected examples 924.7.1. Scatter search for the periodic capacitated arc routing problem 924.7.2. PR for the muti-depot periodic VRP 974.7.3. Unified genetic algorithm for a wide class of vehicle routing problems 1014.8. Conclusion 106Chapter 5. Metaheuristics Hybridizing Various Components 1095.1. Hybridizing metaheuristics  1095.1.1. Principle 1105.1.2. Application to vehicle routing problems 1115.1.3. Selected examples 1125.2. Matheuristics 1225.2.1. Principle 1235.2.2. Application to vehicle routing problems 1245.2.3. Selected examples 1285.3. Conclusion 144Conclusion 145Bibliography 149Index 167