A lower bound for the split delivery vehicle routing problem
成果类型：
Article
署名作者：
Belenguer, JM; Martinez, MC; Mota, E
署名单位：
University of Valencia
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.48.5.801.12407
发表日期：
2000
页码：
801-810
关键词：
摘要：
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 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.