A Lower Bound for the Split Delivery Vehicle Routing Problem

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.