An Iterated Local Search heuristic for the Split Delivery Vehicle Routing Problem
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)
* : Corresponding author
Rua Passo da Pátria 156, Bloco E - 3 andar, São Domingos, Niterói-RJ, 24210-240 -
Brésil
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.
| Subject : | : | typdoc_1455 |
| Language of text | : | English |
| Topics | : | Heuristics and meta-heuristics |
| Keywords | : | Metaheuristics ; Vehicle Routing ; Split Deliveries ; Iterated Local Search |
| PDF version | : |  PDF version |
