A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem

Leonardo Berbotto (), Sergio García () and Francisco Nogales ()

Annals of Operations Research, 2014, vol. 222, issue 1, 153-173

Abstract: The Split Delivery Vehicle Routing Problem (SDVRP) is a variant of the classical Capacitated Vehicle Routing Problem where multiple visits to each customer are allowed. It is an NP-hard problem where exact solutions are difficult to obtain in a reasonable time. This paper shows a tabu search heuristic with granular neighborhood called Randomized Granular Tabu Search that uses a tabu search technique in a bounded neighborhood (granular) defined by the most promising arcs and introduces some new local operators in the local granular tabu search. The algorithm also uses a random selection of the move to be introduced at the current solution. In addition, the local search procedures can explore infeasible neighborhoods in terms of vehicle capacity. These two ideas help to escape from local optima. After the local search process, the algorithm solves one traveling salesman problem per route to improve the solution. Finally, a computational study shows that the proposed method improves many of the best-known solutions for the benchmark instances of the SDVRP literature. Copyright Springer Science+Business Media New York 2014

Keywords: Vehicle routing problem; Split deliveries; Tabu search; Granular neighborhood (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-012-1282-3 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:222:y:2014:i:1:p:153-173:10.1007/s10479-012-1282-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-012-1282-3

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().