In the vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the vehicle capacity and where each customer is visited once. In the split delivery vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. Moreover, the demand of each customer can be greater than the capacity of the vehicles. The SDVRP is NP-hard, even under restricted conditions on the costs, when all vehicles have a capacity greater than two, while it is solvable in polynomial time when the vehicles have a maximum capacity of two. If the costs are symmetrical and satisfy the triangle inequality, the SDVRP with vehicles of maximum capacity two is reducible in polynomial time to a problem of possibly smaller size where each customer has unitary demand. We show that the cost savings that can be realized by allowing split deliveries is at most 50%. The variant of the VRP in which the demand of a customer may be larger than the vehicle capacity, but where each customer has to be visited a minimum number of times, will also be considered. We show that the cost savings that can be realized by allowing more than the minimum number of required visits is again at most 50%. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the vehicle capacity. Finally, we investigate situations in which demands are discrete and vehicle capacities are small. A simple and effective tabu search algorithm will be presented. At each iteration, a neighbour solution is obtained by removing a customer from a set of routes where it is currently visited, and by inserting it either into a new route, or into an existing route which 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 only other heuristic known for the SDVRP, the algorithm proposed by Dror and Trudeau. M. Dror, P. Trudeau, Split delivery routing, Naval Research Logistics 37, 383–402 (1990). C.Archetti, A. Hertz, M.G. Speranza, A tabu search algorithm for the split delivery vehicle routing problem, to appear in Transportation Science. C.Archetti, R.Mansini, M.G. Speranza, Complexity and reducibility of the skip delivery problem, to appear in Transportation Science. C.Archetti, M.Savelsbergh, M.G. Speranza, Worst-case analysis for split delivery vehicle routing problems, to appear in Transportation Science.