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 Savelsbergh, M. W. P. Search for Related Content

An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem

Department of Quantitative Methods, University of Brescia, 25122 Brescia, Italy
Department of Quantitative Methods, University of Brescia, 25122 Brescia, Italy
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
archetti{at}eco.unibs.it
speranza{at}eco.unibs.it
mwps{at}isye.gatech.edu

The split delivery vehicle routing problem is concerned with serving the demand of a set of customers with a fleet of capacitated vehicles at minimum cost. Contrary to what is assumed in the classical vehicle routing problem, a customer can be served by more than one vehicle, if convenient. We present a solution approach that integrates heuristic search with optimization by using an integer program to explore promising parts of the search space identified by a tabu search heuristic. Computational results show that the method improves the solution of the tabu search in all but one instance of a large test set.

Key Words: vehicle routing; split delivery; tabu search; integer programming
History: Received: December 2005; revised: January 2007; accepted: April 2007.

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]

				D. Espinoza, R. Garcia, M. Goycoolea, G. L. Nemhauser, and M. W. P. Savelsbergh Per-Seat, On-Demand Air Transportation Part II: Parallel Local Search Transportation Science, August 1, 2008; 42(3): 279 - 291. [Abstract] [PDF]