Metaheuristics for Logistics (Computer Engineering: Metaeuristics Set)

This book describes the main classical combinatorial problems that can be encountered when designing a logistics network or driving a supply chain. It shows how these problems can be tackled by metaheuristics, both separately and using an integrated approach. A huge number of techniques, from the simplest to the most advanced ones, are given for helping the reader to implement efficient solutions that meet its needs. A lot of books have been written about metaheuristics (methods for solving hard optimization problems) and supply chain management (the field in which we find a huge number of combinatorial optimization problems) in the last decades. So, the main reason of this book is to describe how these methods can be implemented for this class of problems. Cover 1 Title Page 5 Copyright 6 Contents 7 Introduction 13 PART 1: Basic Notions 19 Chapter 1: Introductory Problems 21 1.1. The “swing states” problem 21 1.2. Adel and his camels 23 1.3. Sauron’s forges 25 1.3.1. Problem 1: The inspection of the forges 26 1.3.2. Problem 2: The production of the deadly weapon 27 Chapter 2: A Review of Logistic Problems 31 2.1. Some history 31 2.1.1. The Fermat–Torricelli point 31 2.1.2. The Monge problem 32 2.1.3. The Seven Bridges of Königsberg and the Icosian Game 33 2.2. Some polynomial problems 34 2.2.1. The assignment problem 34 2.2.2. The transportation problem 35 2.2.3. The Minimum-Cost Spanning Tree problem 37 2.3. Packing problems 38 2.3.1. The knapsack problem 38 2.3.2. The bin packing problem 39 2.4. Routing problems 40 2.4.1. The traveling salesman problem 41 2.4.2. The vehicle routing problem (VRP) 42 2.5. Production scheduling problems 42 2.5.1. The flow-shop scheduling problem (FSSP) 44 2.5.2. The job-shop scheduling problem (JSSP) 47 2.6. Lot-sizing problems 49 2.7. Facility location problems 51 2.7.1. The Uncapacitated Plant Location Problem (UPLP) 51 2.7.2. The Dynamic Location Problem (DLP) 53 2.8. Conclusion 54 Chapter 3: An Introduction to Metaheuristics 55 3.1. Optimization problems 55 3.2. Metaheuristics: basic notions 57 3.2.1. Intensification and diversification 58 3.2.2. Neighborhood systems 58 3.3. Individual-based metaheuristics 59 3.3.1. Local search 59 3.3.1.1. Deterministic descent 60 3.3.1.2. Stochastic descent 61 3.3.2. Simulated Annealing 62 3.3.3. The kangaroo algorithm 64 3.3.4. Iterated local search 66 3.3.5. Tabu Search 67 3.4. Population-based metaheuristics 68 3.4.1. Evolutionary algorithms 69 3.4.2. The ant colony algorithm 70 3.4.3. Particle Swarm Optimization 71 3.5. Conclusion 73 Chapter 4: A First Implementation of Metaheuristics 75 4.1. Representing a list of objects 75 4.2. The implementation of a local search 77 4.2.1. The construction of an initial solution 77 4.2.2. Description of basic moves 78 4.2.3. The implementation of stochastic descent (LS) 80 4.3. The implementation of individual-based metaheuristics 82 4.3.1. Simulated annealing (SA) 82 4.3.2. Iterated local search (ILS) 84 4.14. Conclusion 84 PART 2: Advanced Notions 87 Chapter 5: The Traveling Salesman Problem 89 5.1. Representing a solution: the two-level tree structure 89 5.2. Constructing initial solutions 92 5.2.1. A greedy heuristic: nearest neighbor 92 5.2.2. A simplification heuristic: the Christofides algorithm 94 5.3. Neighborhood systems 96 5.3.1. The Lin & Kernighan neighborhood 97 5.3.2. Ejection chain techniques 101 5.4. Some results 104 5.5. Conclusion 106 Chapter 6: The Flow-Shop Problem 107 6.1. Representation and assessment of a solution 107 6.2. Construction of the initial solution 108 6.2.1. Simplification heuristics: CDS 109 6.2.1.1. The two-machine flow-shop 109 6.2.1.2. Principle of CDS heuristics 110 6.2.2. A greedy heuristic: NEH 112 6.3. Neighborhood systems 115 6.3.1. Improvement of the insertion movements 116 6.3.2. Variable-depth neighborhood search 119 6.3.2.1. Effective suppression of a part 119 6.3.2.2. Description of the neighborhood 121 6.4. Results 125 6.5. Conclusion 125 Chapter 7: Some Elements for Other Logistic Problems 127 7.1. Direct representation versus indirect representation 127 7.2. Conditioning problems 129 7.2.1. The knapsack problem 129 7.2.2. The bin-packing problem 130 7.2.2.1. Indirect representation 130 7.2.2.2. Direct representation 131 7.3. Lot-sizing problems 132 7.4. Localization problems 133 7.5. Conclusion 135 PART 3: Evolutions and Current Trends 137 Chapter 8: Supply Chain Management 139 8.1. Introduction to supply chain management 139 8.2. Horizontal synchronization of the supply chain 140 8.2.1. The beer game 141 8.2.2. The bullwhip effect 143 8.3. Vertical synchronization of a supply chain 144 8.4. An integral approach of the supply chain 145 8.5. Conclusion 147 Chapter 9: Hybridization and Coupling Using Metaheuristics 149 9.1. Metaheuristics for the optimization of the supply chain 149 9.2. Hybridization of optimization methods 151 9.2.1. Classification of hybrid methods 151 9.2.2. Illustration by example 152 9.2.3. “Metaheuristic/local search” hybridization 153 9.2.4. Metaheuristic hybridization/Exact Methods 153 9.3. Coupling of optimization methods and performance evaluations 156 9.3.1. Double complexity 156 9.3.2. Coupling of optimization method/simulation model 157 9.4. Conclusion 159 Chapter 10: Flexible Manufacturing Systems 161 10.1. Introduction to the FMS challenges 161 10.2. The job-shop problem with transport 163 10.2.1. Definition of the problem 163 10.3. Proposal for a metaheuristic/simulation coupling 166 10.3.1. Representation of a solution 166 10.3.2. Simulation method 167 10.3.3. Optimization method 170 10.3.4. Results 171 10.4. Workshop layout problem 172 10.4.1. Aggregated model and exact resolution 172 10.4.2. Detailed model and approximate solutions 175 10.5. Conclusion 177 Chapter 11: Synchronization Problems Based on Vehicle Routings 179 11.1. Inventory routing problem 180 11.1.1. Presentation of the problem 180 11.1.1.1. Introductory example 180 11.1.1.2. Linear program of the IRP 181 11.1.2. Resolution by metaheuristics 184 11.2. The location-routing problem 185 11.2.1. Definition of the problem 185 11.2.2. Solution with metaheuristics 189 11.3. Conclusion 190 Chapter 12: Solution to Problems 191 12.1. The swing state problem 191 12.2. Adel and his camels 194 12.2.1. First question 194 12.2.2. Second question 195 12.2.3. Third question 198 12.3. The forges of Sauron 198 12.3.1. The inspection of the forges 198 12.3.2. Production of the lethal weapon 201 Conclusion 203 Bibliography 205 Index 215