A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem

C. Archetti (), M. G. Speranza () and A. Hertz ()
Additional contact information
C. Archetti: Dipartimento Metodi Quantitativi, Università degli Studi di Brescia, Contrada Santa Chiara 50, 25122 Brescia, Italia
M. G. Speranza: Dipartimento Metodi Quantitativi, Università degli Studi di Brescia, Contrada Santa Chiara 50, 25122 Brescia, Italia
A. Hertz: Département de Mathématiques et de Génie Industriel, École Polytechnique, CP 6079, succ. Centre-ville, Montréal, Canada H3C 3A7

Transportation Science, 2006, vol. 40, issue 1, 64-73

Abstract: We describe a tabu search algorithm for the vehicle routing problem with split deliveries. At each iteration, a neighbor solution is obtained by removing a customer from a set of routes where it is currently visited and inserting it either into a new route or into an existing route that has enough residual capacity. The algorithm also considers the possibility of inserting a customer into a route without removing it from another route. The insertion of a customer into a route is done by means of the cheapest insertion method. Computational experiments are reported for a set of benchmark problems, and the results are compared with those obtained by the algorithm proposed by Dror and Trudeau.

Keywords: split delivery vehicle routing problem; triangle inequality; metaheuristics; tabu search (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (49)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1040.0103 (application/pdf)

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:inm:ortrsc:v:40:y:2006:i:1:p:64-73

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().