A Construction Heuristic for the Split Delivery Vehicle Routing Problem

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,.

DOI: 10.4236/ajor.2012.22018                

Abstract

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.

Keywords

Vehicle Routing Problem; Transportation; Construction Heuristics

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, Vol. 6, No. 1, 1959, pp. 80-91. doi:10.1287/mnsc.6.1.80
[2]	P. Toth and D. Vigo, “The Vehicle Routing Problem,” Society for Industrial and Applied Mathematics, Philadelphia, 2002.
[3]	P. Toth and D. Vigo, “Models, Relaxations and Exact Approaches for the Capacitated Vehicle Routing Problem,” Discrete Applied Mathematics, Vol. 123, No. 1-3, 2002, pp. 487-512. doi:10.1016/S0166-218X(01)00351-1
[4]	J. F. Cordeau, M. Gendreau, G. Laporte, J.-Y. Potvin and F. Semet, “A Guide to Vehicle Routing Heuristics,” Journal of the Operational Research Society, Vol. 53, 2002, pp. 512-522. doi:10.1057/palgrave.jors.2601319
[5]	J. F. Cordeau, M. Gendreau, A. Hertz, G. Laporte and J. S. Sormany, “New Heuristics for the Vehicle Routing Problem,” In: A. Langevin and D. Riopel, Eds., Logistics Systems: Design and Optimization, Springer, 2005, pp. 270-297. doi:10.1007/0-387-24977-X_9
[6]	M. Dror and P. Trudeau, “Savings by Split Delivery Routing,” Transportation Science, Vol. 23, No. 2, 1989, pp. 141-145. doi:10.1287/trsc.23.2.141
[7]	M. Dror and P. Trudeau, “Split Delivery Routing,” Naval Research Logistics, Vol. 37, 1990, pp. 383-402.
[8]	M. Dror, G. Laporte and P. Trudeau, “Vehicle Routing with Split Deliveries,” Discrete Applied Mathematics, Vol. 50, No. 3, 1994, pp. 239-254. doi:10.1016/0166-218X(92)00172-I
[9]	C. Archetti and M. G. Speranza, “An Overview on the Split Delivery Vehicle Routing Problem,” Operations Research Proceedings, Part IV, 2006, pp. 123-127.
[10]	C. Archetti and M. G. Speranza, “The Split Delivery Vehicle Routing Problem: A Survey,” The Vehicle Routing Problem: Latest Advances and New Challenges,” Operations Research/Computer Science Interfaces Series, Vol. 43, Part I, 2008, pp. 103-122. doi:10.1016/0166-218X(92)00172-I
[11]	D. J. Gulczynski, B. Golden and E. Wasil, “Recent Developments in Modeling and Solving the Split Delivery Vehicle Routing Problem,” Tutorials in Operations Research, INFORMS, 2008, pp. 170-180.
[12]	B. L. Golden and A. A. Assad, “Vehicle Routing: Methods and Studies,” North-Holland, Amsterdam, 1988.
[13]	P. W. Frizzell and J. W. Giffin, “The Split Delivery Vehicle Scheduling Problem with Time Windows and Grid Network Distances,” Computers and Operations Research, Vol. 22, No. 6, 1995, pp. 655-667. doi:10.1016/0305-0548(94)00040-F
[14]	P. W. Frizzell and J. W. Giffin, “The Bounded Split Delivery Vehicle Routing Problem with Grid Network Distances,” Asia Pacific Journal of Operational Research, Vol. 9, 1992, pp. 101-116.
[15]	C. Archetti, M. Savelsbergh and A. Hertz, “A Tabu Search Algorithm for the Split Delivery Vehicle Routing Problem,” Transportation Science, Vol. 40, No. 1, 2006, pp. 64-73. doi:10.1287/trsc.1040.0103
[16]	C. Archetti, M. Savelsbergh and M. G. Speranza, “Worst- Case Analysis for Split Delivery Vehicle Routing Problems,” Transportation Science, Vol. 40, No. 2, 2006, pp. 226-234. doi:10.1287/trsc.1050.0117
[17]	C. Archetti, M. Savelsbergh and M. G. Speranza, “To Split or Not to Split: That Is the Question,” Transportation Research Part E, Vol. 44, No. 1, 2008, pp. 114-123. doi:10.1016/j.tre.2006.04.003
[18]	C. Lee, M. A. Epelman, C. C. White and Y. A. Bozer, “A Shortest Path Approach to the Multiple-Vehicle Routing Problem with Split Pick-Ups,” Transportation Research Part B, Vol. 40, No. 4, 2006, pp. 265-284. doi:10.1016/j.trb.2004.11.004
[19]	J. M. Belenguer, M. C. Martinez and E. A. Mota, “Lower Bound for the Split Delivery VRP,” Operations Research, Vol. 48, No. 5, 2000, pp. 801-810. doi:10.1287/opre.48.5.801.12407
[20]	M. Jin, K. Liu and R. O. Bowden, “A Two-Stage Algorithm with Valid Inequalities for the Split Delivery Vehicle Routing Problem,” International Journal of Production Economics, Vol. 105, No. 1, 2007, pp. 228-242. doi:10.1016/j.ijpe.2006.04.014
[21]	M. Jin, K. Liu and B. Eksioglu, “A Column Generation Algorithm for the Vehicle Routing Problem with Split Delivery,” Proceedings of the 2007 Industrial Engineering Research Conference, Nashville, 19-23 May 2007.
[22]	S. Chen, B. Golden and E. Wasil, “The Split Delivery Vehicle Routing Problem: Applications, Test Problems, and Computational Results,” Networks, Vol. 94, No. 4, 2007, pp. 318-329. doi:10.1002/net.20181
[23]	S. Chen, “A Study of Four Network Problems in Transportation, Telecommunications, and Supply Chain Management,” Dissertation Thesis, University of Maryland, 2007.
[24]	G. Clarke and J. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, No. 4, 1964, pp. 568-581. doi:10.1287/opre.12.4.568
[25]	W. Burrows, “The Vehicle Routing Problem with Loadsplitting: A Heuristic Approach,” 24th Annual Conference of the Operational Research Society of New Zealand, 1988, pp. 33-38.
[26]	R. E. Aleman, “A Guided Neighborhood Search Applied to the Split Delivery Vehicle Routing Problem,” Dissertation Thesis, Wright State University, 2009.
[27]	K. Liu, “A Study on the Split Delivery Vehicle Routing Problem,” Dissertation Thesis, Mississippi State University, 2005.
[28]	M. A. Nowak, “The Pickup and Delivery Problem with Split Loads,” Dissertation Thesis, Georgia Institute of Technology, 2005.
[29]	J. H. Wilck IV, “Solving the Split Delivery Vehicle Routing Problem,” Dissertation Thesis, Pennsylvania State University, 2009.
[30]	P. Mullaseril, M. Dror and J. Leung, “Split-Delivery Routing Heuristics in Livestock Feed Distribution,” Journal of the Operational Research Society, Vol. 48, 1997, pp. 107-116.
[31]	G. Sierksma and G. A. Tijssen “Routing Helicopters for Crew Exchanges on Off-Shore Locations,” Annals of Operations Research, Vol. 76, 1998, pp. 261-286. doi:10.1023/A:1018900705946
[32]	S. Song, K. Lee and G. Kim, “A Practical Approach to Solving a Newspaper Logistics Problem Using a Digital Map,” Computers and Industrial Engineering, Vol. 43, No. 1-2, 2002, pp. 315-330. doi:10.1016/S0360-8352(02)00077-3
[33]	M. M. Syslo, N. Deo and J. S. Kowalik, “Discrete Optimization Algorithms with PASCAL Programs,” Prentice- Hall, Englewood Cliffs, 1983.