A lower bound for the split delivery vehicle routing problem

A lower bound for the split delivery vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor20021741
Country: United States
Volume: 48
Issue: 5
Start Page Number: 801
End Page Number: 810
Publication Date: Sep 2000
Journal: Operations Research
Authors: , ,
Keywords: transportation: general
Abstract:

In this paper we consider the Split Delivery Vehicle Routing Problem (SDVRP), a relaxation of the known Capacitated Vehicle Routing Problem 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 (PSDVRP), 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 PSDVRP 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.

Reviews

Required fields are marked *. Your email address will not be published.