An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem Claudia Archetti 1, Martin Savelsbergh 2, and M. Grazia Speranza 1 1 University of Brescia, Department of Quantitative Methods, Brescia, Italy farchetti, speranzag@eco.unibs.it 2 School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, U.S.A. mwps@isye.gatech.edu Abstract. The split delivery vehicle routing problem is concerned with serving the demand of a set of customers with a °eet of capacitated vehicles at minimum cost. A customer, contrary to what is assumed in the classical vehicle routing problem, 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 ex- plore promising parts of the search space identiŻed by a tabu search heuristic. Computational results show that the method is able to im- prove the solution of the tabu search in all but one instance of a large test set. Keywords: split delivery vehicle routing problem, tabu search, integer programming.