Metaheuristics for Vehicle Routing Problems

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