An iterated local search heuristic for the split delivery vehicle routing problem

作者：Silva Marcos Melo^*; Subramanian Anand; Ochi Luiz Satoru

来源：Computers & Operations Research, 2015, 53: 234-249.

DOI：10.1016/j.cor.2014.08.005

• Metaheuristics
• Vehicle routing
• Split deliveries
• Iterated local search

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.

• 出版日期2015-1