Wednesday 26
Heuristics and meta-heuristics
Nicolas Dupin
› 10:30 - 11:00 (30min)
› Bât. C - Sigalas
An Iterated Local Search heuristic for the Split Delivery Vehicle Routing Problem
Marcos De Melo Da Silva  1, *@  , Anand Subramanian  2@  , Luiz Satoru Ochi  3@  
1 : Laboratoire d'Informatique de Paris-Nord  (LIPN)  -  Website
Institut Galilée, Université Paris XIII - Paris Nord
Institut Galilée 99, avenue J.B Clément 93430 VILLETANEUSE -  France
2 : Universidade Federal da Paraíba  (UFPB)
Departamento de Engenharia de Produção, Centro de Tecnologia, Campus I - Bloco G, Cidade Universitária, João Pessoa-PB, 58051-970 -  Brésil
3 : Instituto de Computação - Universidade Federal Fluminense  (IC-UFF)
Rua Passo da Pátria 156, Bloco E - 3 andar, São Domingos, Niterói-RJ, 24210-240 -  Brésil
* : Corresponding author

This work concerns the Split Delivery Vehicle Routing Problem (SDVRP). This problem is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) since the customers' demands are allowed to be split. We deal with the cases where the fleet is unlimited (SDVRP-UF) and limited (SDVRP-LF). In order to solve them, we propose a multi-start Iterated Local Search (ILS) based heuristic that includes classical CVRP neighborhood structures, as well as those specifically designed for the SDVRP, in the local search phase. Extensive computational experiments were carried out on benchmark instances available in the literature. The results obtained are highly competitive and a number of new improved solutions are reported.

Online user: 2