This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Archetti, C. Articles by Hertz, A. Search for Related Content

A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem

Dipartimento Metodi Quantitativi, Università degli Studi di Brescia, Contrada Santa Chiara 50, 25122 Brescia, Italia
Dipartimento Metodi Quantitativi, Università degli Studi di Brescia, Contrada Santa Chiara 50, 25122 Brescia, Italia
Département de Mathématiques et de Génie Industriel, École Polytechnique, CP 6079, succ. Centre-ville, Montréal, Canada H3C 3A7
archetti{at}eco.unibs.it
speranza{at}eco.unibs.it
alain.hertz{at}gerad.ca

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.

Key Words: split delivery vehicle routing problem; triangle inequality; metaheuristics; tabu search
History: Received: April 2003; revised: October 2003; accepted: October 2003.

This article has been cited by other articles:

				J. W. Ohlmann, M. J. Fry, and B. W. Thomas Route Design for Lean Production Systems Transportation Science, August 1, 2008; 42(3): 352 - 370. [Abstract] [PDF]

				C. Archetti, M. G. Speranza, and M. W. P. Savelsbergh An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem Transportation Science, February 1, 2008; 42(1): 22 - 31. [Abstract] [PDF]

				M. Nowak, O. Ergun, and C. C. White III Pickup and Delivery with Split Loads Transportation Science, February 1, 2008; 42(1): 32 - 43. [Abstract] [PDF]