An iterated local search heuristic for the split delivery vehicle routing problem. (January 2015)

• Record Type: Journal Article
• Authors: Silva, Marcos Melo; Subramanian, Anand; Ochi, Luiz Satoru
• Is Part Of: Computers & operations research. Volume 53(2015)
• Page Start: 234
• Page End: 249
• Publication Date: 2015-01
• Subjects: Metaheuristics -- Vehicle routing -- Split deliveries -- Iterated local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2014.08.005
• Languages: English
• ISSNs: 0305-0548

Abstract

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.