A Lower Bound for the Split Delivery Vehicle Routing Problem

J. M. Belenguer (), M. C. Martinez () and E. Mota ()
Additional contact information
J. M. Belenguer: Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain
M. C. Martinez: Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain
E. Mota: Departament d'Estadística i Investigació Operativa, Universitat de València, Dr. Moliner, 50, Burjassot, CP.- 46100, Spain

Operations Research, 2000, vol. 48, issue 5, 801-810

Abstract: 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.

Keywords: 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 (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.5.801.12407 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:48:y:2000:i:5:p:801-810

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().