AJOR  Vol.2 No.2 , June 2012
A Construction Heuristic for the Split Delivery Vehicle Routing Problem
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.

Cite this paper
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.
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.

 
 
Top