Skip to main content

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

Berbotto, Leonardo, García-Quiles, Sergio, Nogales, Francisco J. (2013) A Randomized Granular Tabu Search heuristic for the split delivery vehicle routing problem. Annals of Operation Research, . pp. 1-20. ISSN 0254-5330. (doi:10.1007/s10479-012-1282-3) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:32971)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. (Contact us about this Publication)
Official URL
http://dx.doi.org/10.1007/s10479-012-1282-3

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.

Item Type: Article
DOI/Identification number: 10.1007/s10479-012-1282-3
Additional information: Published online ahead of print January 2013
Uncontrolled keywords: Vehicle routing problem – Split deliveries – Tabu search – Granular neighborhood
Subjects: H Social Sciences > HA Statistics > HA33 Management Science
Divisions: Divisions > Kent Business School - Division > Kent Business School (do not use)
Depositing User: Catherine Norman
Date Deposited: 14 Jan 2013 15:24 UTC
Last Modified: 16 Feb 2021 12:44 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/32971 (The current URI for this page, for reference purposes)
  • Depositors only (login required):