Author(s)

Joseph Hubert Wilck IV, Tom M. Cavalier

Industrial and Information Engineering Department, University of Tennessee, Knoxville, USA.
ndustrial and Manufacturing Engineering Department, Pennsylvania State University,.

The Split Delivery Vehicle Routing Problem (SDVRP) is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) where customers may be assigned to multiple routes. A new construction heuristic is developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. With respect to the total travel distance, the construction heuristic compares favorably versus a column generation method and a two-phase method. In addition, the construction heuristic is computationally faster than both previous methods. This construction heuristic could be useful in developing initial solutions, very quickly, for a heuristic, algorithm, or exact procedure.

Vehicle Routing Problem; Transportation; Construction Heuristics

J. Wilck IV and T. Cavalier, "A Construction Heuristic for the Split Delivery Vehicle Routing Problem," American Journal of Operations Research, Vol. 2 No. 2, 2012, pp. 153-162. doi: 10.4236/ajor.2012.22018.