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

Leonardo Berbotto, Sergio Garcia, FcoJavier Nogales

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
JournalAnnals of Operations Research
Early online date10 Jan 2013
Publication statusPublished - 2013

Keywords / Materials (for Non-textual outputs)

  • Vehicle routing problem
  • Split deliveries
  • Tabu search
  • Granular neighborhood


Dive into the research topics of 'A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem'. Together they form a unique fingerprint.

Cite this