Paper Info
Title
A column generation approach for the split delivery vehicle routing problem
Abstract
In this article we present a branch-and-price-and-cut method for the solution of the split delivery vehicle routing problem (SDVRP). The SDVRP is the problem to serve customers with a fleet of capacitated vehicles at minimum traveling cost. With respect to the classical vehicle routing problem, where each customer is visited exactly once, in the SDVRP a customer may be visited any number of times. The exact method we propose is based on a decomposition of the problem where the possible routes, with the delivery quantities, are generated in the subproblem. The generated routes are also used to find a heuristic solution to the problem. We consider both the case where the fleet of vehicles is unlimited and the case where the fleet is limited to the minimum possible number of vehicles. We solve to optimality instances with larger size with respect to previous approaches, find new best solutions to several benchmark instances and reduce the optimality gap on most of the benchmark instances. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), 241–254 2011 © 2011 Wiley Periodicals, Inc.
Year
DOI
Venue
2011
10.1002/net.20467
Networks
Keywords
Field
DocType
benchmark instance,minimum possible number,split delivery vehicle,heuristic solution,delivery quantity,wiley periodicals,exact method,column generation approach,inc. networks,capacitated vehicle,branch-and-price-and-cut method,classical vehicle,column generation
Vehicle routing problem,Mathematical optimization,Heuristic,Column generation,Mathematics
Journal
Volume
Issue
ISSN
58
4
0028-3045
Citations 
PageRank 
References 
21
0.92
17
Authors
3
Name
Order
Citations
PageRank
C. Archetti11999.69
Nicola Bianchessi223613.72
M. G. Speranza329419.55