139,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 322
Veröffentlichungsjahr: 2016
Ähnliche
Table of Contents
Cover
Title
Copyright
Notations and Abbreviations
Introduction
1 General Presentation of Vehicle Routing Problems
1.1. Logistics management and combinatorial optimization
1.2. Vehicle routing problems
1.3. Conclusion
2 Simple Heuristics and Local Search Procedures
2.1. Simple heuristics
2.2. Local search
2.3. Conclusion
3 Metaheuristics Generating a Sequence of Solutions
3.1. Simulated annealing (SA)
3.2. Greedy randomized adaptive search procedure: GRASP
3.3. Tabu search
3.4. Variable neighborhood search
3.5. Iterated local search
3.6. Guided local search
3.7. Large neighborhood search
3.8. Transitional forms
3.9. Selected examples
3.10. Conclusion
4 Metaheuristics Based on a Set of Solutions
4.1. Genetic algorithm and its variants
4.2. Scatter search
4.3. Path relinking
4.4. Ant colony optimization
4.5. Particle swarm optimization
4.6. Other approaches and their use in vehicle routing problems
4.7. Selected examples
4.8. Conclusion
5 Metaheuristics Hybridizing Various Components
5.1. Hybridizing metaheuristics
5.2. Matheuristics
5.3. Conclusion
Conclusion
Bibliography
Index
End User License Agreement
Guide
Cover
Table of Contents
Begin Reading
Pages
C1
iii
iv
v
ix
x
xi
xiii
xiv
xv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
171
172
173
174
175
176
Metaheuristics for Vehicle Routing Problems
Volume 3
Nacima Labadie
Christian Prins
Caroline Prodhon
Metaheuristics Setcoordinated byNicolas Monmarché and Patrick Siarry
First published 2016 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2016
The rights of Nacima Labadie, Christian Prins and Caroline Prodhon to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2015959666
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-84821-811-6
Notations and Abbreviations
Here is a non-exhaustive list of the most common notations and abbreviations used in the book.
Notations
A
:
set of arcs.
c
ij
:
traveling cost between nodes
i
and
j
.
d
i
:
demand of customer
i
.
E
:
set of edges.
f
(
S
) :
cost of solution
S
.
G
:
a complete graph.
K
:
set of identical vehicles.
n
:
number of customers.
N
(
S
) :
subset of solutions close to
S
in term of structure (neighborhood).
Q
:
vehicles capacity.
R
i
:
route
i
.
S
:
a solution.
T
:
tour or sequence of customers.
V
:
set of nodes.
Abbreviations related to problems
CARP
:
capacitated arc routing problem.
CCVRP
:
cumulative capacitated vehicle routing problem.
CVRP
:
capacitated vehicle routing problem.
DARP
:
dial-a-ride problem.
HFVRP
:
heterogeneous fleet vehicle routing problem.
IRP
:
inventory routing problem.
LRP
:
location-routing problem.
LRP-2E
:
two-echelon location-routing problem.
MDVRP
:
multi-depot vehicle routing problem.
OVRP
:
open vehicle routing problem.
PCARP
:
periodic capacitated arc routing problem.
PDPTW
:
pick up and delivery vehicle routing problem with time windows.
PVRP
:
periodic vehicle routing problem.
RCPSP
:
resource-constrained project scheduling problem.
SCP
:
set covering problem.
SPP
:
set partitioning problem.
SDVRP
:
vehicle routing problem with split deliveries.
TOP
:
team orienteering problem.
TSP
:
traveling salesman problem.
TTRP
:
truck and trailer routing problem.
VRP-2E
:
two-echelon vehicle routing problem.
VRPs
:
family of vehicle routing problems.
VRPTW
:
vehicle routing problem with time windows.
Abbreviations related to methods
ACO
:
ant colony optimization.
ALNS
:
adaptive large neighborhood search.
ELS
:
evolutionary local search.
GA
:
genetic algorithm.
GLS
:
guided local search.
GRASP
:
greedy randomized adaptive search procedure
GTS
:
granular tabu search (also guided tabu search).
HGSADC
:
hybrid genetic search with adaptive diversity control.
ILS
:
iterated local search.
LNS
:
large neighborhood search
LS
:
local search.
MA
:
memetic algorithm.
MA
|
PM
:
memetic algorithm with population management.
PSO
:
particle swarm optimization.
PR
:
path relinking.
RVNS
:
reduced variable neighborhood search.
SA
:
simulated annealing.
SS
:
scatter search.
TS
:
tabu search.
VND
:
variable neighborhood descent.
VNS
:
variable neighborhood search.
VLSN
:
very large scale neighborhood search.
Introduction
Unlike heuristics, which are problem-dependent techniques which try to take full advantage of the features of the problem at hand but which usually get trapped in a local optimum when followed by a local search, metaheuristics can be defined as solution methods that control the exploration of a solution space by problem-independent techniques with higher level strategies. This allows them to explore the solution space more extensively with the aim of escaping from local optima and thus a hopefully obtain a better solution. These approaches include any scheme that resorts, for example, to one or more neighborhood structures, building or destroying procedures or combining components of several solutions. Notwithstanding their general structure, it is necessary to adapt the techniques according to the problem to solve by some fine-tuning of their intrinsic parameters. Metaheuristic methods have proved to be particularly effective for solving many types of complex problems.
This book is dedicated to these methods developed to one of the most important and studied categories of combinatorial optimization problems: the family of vehicle routing problems (VRPs). The aim of the basic version also called capacitated VRP (CVRP) is to determine the optimal set of routes to be performed by a fleet of capacitated vehicles to serve the demand of a given customer set.
More than 15 years have elapsed since Dantzig and Ramser introduced the problem in 1959 [DAN 59], and the number of models and solution methods has experienced a strong growth as exposed in [LAP 09]. Although the CVRP still attracts researchers, many variants are now investigated. This interest is motivated by two main concerns:
– this class of problems has a high practical relevance;
– it is challenging to solve given its considerable difficulty.
Despite the abundant activity on VRPs, the current exact methods are limited to problems of about 100 customers [BAL 08a], while real cases can reach 1,000 clients.
Therefore, a large number of metaheuristics have been proposed to solve very different problems of vehicle routing, as stated by the surveys periodically published on the subject. From procedures with tabu to hybrid approaches combining heuristic and exact methods, metaheuristics remain the favorite methods for dealing with realistic cases.
Several books are available on either metaheuristics [DRÉ 03, SIA 14] or VRPs [TOT 02] but, to the best of our knowledge, the only books addressing these two topics simultaneously are published PhD dissertations [EUC 12] or books with contributed chapters [GOL 08]. The aim here is more to provide a book for people wishing to discover and quickly master metaheuristics dedicated to VRPs. The particularity is to combine a tutorial with algorithms, examples, and a quick overview of the state-of-the art for such methods developed in the last decades for the CVRP and some of its main variants.
The key points are to present:
– a progressive approach, from the basics to several recent and efficient methods;
– different metaheuristics for the same VRP and, conversely, the way of adapting the same metaheuristic template to several problems;
– algorithms allowing the readers to implement the methods on a computer;
– an up-to-date bibliography focusing on the references which have a real interest.
The book consists of five chapters. After this introduction, the first chapter gives a general presentation that intends to make the readers more familiar with the related fields of logistics and combinatorial optimization.
This preamble is followed, in Chapter 2, with a description of significant heuristic methods classically applied 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 VRPs. 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 other kinds of methods (mixed integer programs, mathematical decompositions, etc.).
Thus, Chapter 3 begins with the class that works on a single solution at a time, making it evolve through a particular iterative process. This kind of exploration requires us to define at least one neighborhood to jump from an incumbent solution to another area of the solution space. Eight approaches are presented in this chapter, namely simulated annealing, greedy adaptive search procedure, tabu search, variable neighborhood search, iterated local search, guided local search, adaptive large neighborhood search and transitional forms such as evolutionary local search.
Chapter 4 exposes methods operating on a set of solutions. Their feature is to generate new solutions by either combining existing ones or by making agents cooperate through a learning process. Two main variants are put forward: those that combine solutions selected from a population such as genetic algorithms, memetic algorithms, scatter search and path relinking; the ones that make cooperate homogenous agents in their environment such as particle swarm optimization and ant colony optimization.
Chapter 5 is devoted to two main classes of hybrid methods: either by combining components from several stand alone metaheuristics, or by crossing exact algorithms with metaheuristics (leading to the so called matheuristics). The main motivation of this trend is to take advantage of the complementarity of different optimization strategies and cooperate in synergy.
Finally, the Conclusion closes the book and draws up some perspectives of the research on VRPs. In the three chapters detailing the different class of metaheuristics, several selected implementations of methods dedicated to typical VRPs are given as illustrative examples.
