An iterated local search heuristic for the split delivery vehicle routing problem |
| |
Affiliation: | 1. Universidade Federal Fluminense, Instituto de Computação, Rua Passo da Pátria 156, Bloco E – 3° andar, São Domingos, Niterói-RJ 24210-240, Brazil;2. Universidade Federal da Paraíba, Departamento de Engenharia de Produção, Centro de Tecnologia, Campus I – Bloco G, Cidade Universitária, João Pessoa-PB 58051-970, Brazil |
| |
Abstract: | This paper 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 implemented a multi-start Iterated Local Search (ILS) based heuristic that includes a novel perturbation mechanism. Extensive computational experiments were carried out on benchmark instances available in the literature. The results obtained are highly competitive, more precisely, 55 best known solutions were equaled and new improved solutions were found for 243 out of 324 instances, with an average and maximum improvement of 1.15% and 2.81%, respectively. |
| |
Keywords: | Metaheuristics Vehicle routing Split deliveries Iterated local search |
本文献已被 ScienceDirect 等数据库收录! |
|