Labadie Nacima - Metaheuristics for vehicle routing problems

1. 1 General Presentation of Vehicle Routing Problems
2. 2 Simple Heuristics and Local Search Procedures
3. 3 Metaheuristics Generating a Sequence of Solutions
4. 4 Metaheuristics Based on a Set of Solutions
5. 5 Metaheuristics Hybridizing Various Components

Volume 3

Metaheuristics Set
coordinated by
Nicolas 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 Georges 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

Here is a non-exhaustive list of the most common notations and abbreviations used in the book.

A :set of arcs.cij :traveling cost between nodes i and j.di :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.Ri :route i.S :a solution.T :tour or sequence of customers.V :set of nodes. 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. 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 procedureGTS :granular tabu search (also guided tabu search).HGSADC :hybrid genetic search with adaptive diversity control.ILS :iterated local search.LNS :large neighborhood searchLS :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.

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:

1. this class of problems has a high practical relevance;
2. 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: