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 Belenguer, J. M. Articles by Mota, E. Search for Related Content

A Lower Bound for the Split Delivery Vehicle Routing Problem

Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain
Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain
Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain
jose.belenguer{at}uv.es
m.carmen.martinez{at}uv.es
enrique.mota{at}ur.ed

In this paper we consider the Split Delivery Vehicle Routing Problem (SDVRP), a relaxation of the known Capacitated Vehicle Routing Problem (CVRP) in which the demand of any client can be serviced by more than one vehicle. We define a feasible solution of this problem, and we show that the convex hull of the associated incidence vectors is a polyhedron (P_SDVRP), whose dimension depends on whether a vehicle visiting a client must service, or not, at least one unit of the client demand. From a partial and linear description of P_SDVRP and a new family of valid inequalities, we develop a lower bound whose quality is exhibited in the computational results provided, which include the optimal resolution of some known instances—one of them with 50 clients. This instance is, as far as we know, the biggest one solved so far.

Subject classifications: Transportation, vehicle routing: a case with split demands, study of the polyhedron; Programming, integer, cutting plane: based on the polyhedral study, computational results are reported.
History: Received May 1997; revision received April 1998; accepted November 1998.

This article has been cited by other articles:

				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]

				C. Archetti, M. W. P. Savelsbergh, and M. G. Speranza Worst-Case Analysis for Split Delivery Vehicle Routing Problems Transportation Science, May 1, 2006; 40(2): 226 - 234. [Abstract] [PDF]

				C. Archetti, M. G. Speranza, and A. Hertz A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem Transportation Science, February 1, 2006; 40(1): 64 - 73. [Abstract] [PDF]