A Genetic Algorithm for the Split Delivery Vehicle Routing Problem

Joseph Hubert Wilck IV, Tom M. Cavalier

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

DOI: 10.4236/ajor.2012.22024                

Abstract

The Split Delivery Vehicle Routing Problem (SDVRP) allows customers to be assigned to multiple routes. Two hybrid genetic algorithms are developed for the SDVRP and computational results are given for thirty-two data sets from previous literature. With respect to the total travel distance and computer time, the genetic algorithm compares favorably versus a column generation method and a two-phase method.

Keywords

Vehicle Routing Problem; Transportation; Genetic Algorithm

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]	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
[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]	B. L. Golden and A. A. Assad, “Vehicle Routing: Methods and Studies,” North-Holland, Amsterdam, 1988.
[7]	P. Toth and D. Vigo, “The Vehicle Routing Problem,” Society for Industrial and Applied Mathematics, Philadelphia, 2002.
[8]	G. Laporte and I. H. Osman, “Routing Problems: A Bibliography,” Annals of Operations Research, Vol. 61, No. 1, 1995, pp. 227-262. doi:10.1007/BF02098290
[9]	M. Reimann, “Analysing Risk Orientation in a Stochastic VRP,” European Journal of Industrial Engineering, Vol. 1, No. 2, 2007, pp. 111-130. doi:10.1504/EJIE.2007.014105
[10]	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
[11]	M. Dror and P. Trudeau, “Split Delivery Routing,” Naval Research Logistics, Vol. 37, 1990, pp. 383-402.
[12]	M. Affenzeller, S. Winkler, S. Wagner and A. Beham, “Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications (Numerical Insights),” Chapman & Hall, 2009. doi:10.1201/9781420011326
[13]	P. Damodaran, N. S. Hirani and M. C. Velez-Gallego, “Scheduling Identical Parallel Batch Processing Machines to Minimise Makespan Using Genetic Algorithms,” European Journal of Industrial Engineering, Vol. 3, No. 2, 2009, pp. 187-206. doi:10.1504/EJIE.2009.023605
[14]	G. B. Alvarenga, G. R. Mateus and G. de Tomi, “A Genetic and Set Partitioning Two-Phase Approach for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 34, No. 6, 2007, pp. 1561-1584. doi:10.1016/j.cor.2005.07.025
[15]	X. Wang, B. L. Golden and E. A. Wasil, “Using a Genetic Algorithm to Solve the Generalized Orienteering Problem,” In: B. Golden, S. Raghavan and E. Wasil, Eds., The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, 2008, pp. 263-274. doi:10.1007/978-0-387-77778-8_12
[16]	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
[17]	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
[18]	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.
[19]	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
[20]	R. E. Aleman and R. R. Hill, “A Tabu Search with Vocabulary Building Approach for the Vehicle Routing Problem with Split Demands,” International Journal of Metaheuristics, Vol. 1, No. 1, 2010, pp. 55-80.
[21]	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
[22]	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
[23]	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
[24]	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
[25]	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
[26]	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.
[27]	M. Jin, K. Liu and B. Eksioglu, “A Column Generation Approach for the Split Delivery Vehicle Routing Problem,” Operations Research Letters, Vol. 36, No. 2, 2008, pp. 265-270. doi:10.1016/j.orl.2007.05.012
[28]	S. Chen, B. Golden and E. Wasil, “The Split Delivery Vehicle Routing Problem: Applications, Test Problems, and Computational Results,” Networks, Vol. 49, No. 4, 2007, pp. 318-329. doi:10.1002/net.20181
[29]	W. Burrows, “The Vehicle Routing Problem with Loadsplitting: A Heuristic Approach,” 24th Annual Conference of the Operational Research Society of New Zealand, Auckland, 18-19 August 1988, pp. 33-38.
[30]	J. H. Wilck IV and T. M. Cavalier, “A Construction Heuristic for the Split Delivery Vehicle Routing Problem,” American Journal of Operations Research, in press, 2012.
[31]	R. E. Aleman, X. Zhang and R. R. Hill, “An Adaptive Memory Algorithm for the Split Delivery Routing Problem,” Journal of Heuristics, Available Online, 2008.
[32]	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.1007/978-0-387-77778-8_5
[33]	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.
[34]	R. E. Aleman, “A Guided Neighborhood Search Applied to the Split Delivery Vehicle Routing Problem,” Dissertation Thesis, Wright State University, 2009.
[35]	J. H. Wilck IV, “Solving the Split Delivery Vehicle Routing Problem,” Dissertation Thesis, Pennsylvania State University, 2009.
[36]	K. Liu, “A Study on the Split Delivery Vehicle Routing Problem,” Dissertation Thesis, Mississippi State University, 2005.
[37]	M. A. Nowak, “The Pickup and Delivery Problem with Split Loads,” Dissertation Thesis, Georgia Institute of Technology, 2005.
[38]	S. Chen, “A Study of Four Network Problems in Transportation, Telecommunications, and Supply Chain Management,” Dissertation Thesis, University of Maryland, 2007.
[39]	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.
[40]	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
[41]	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
[42]	D. Goldberg, “Genetic Algorithms in Search Optimization and Machine Learning,” Addison Wesley, Reading, 1989.
[43]	W. L. Winston and M. Venkataramanan, “Introduction to Mathematical Programming, Operations Research: Volume One,” 4th Edition, Thomson Learning, 2003.
[44]	M. Gendreau, G. Laporte and J.-Y. Potvin, “Vehicle Routing: Modern Heuristics,” In: E. Aarts and J. K. Lenstra, Eds., Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1997, pp. 323-330.
[45]	M. Gendreau, G. Laporte and J.-Y. Potvin, “Metaheuristics for the Capacitated VRP,” In: P. Toth and D. Vigo, Eds., The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, Philadelphia, 2002, pp. 140- 144.
[46]	B. M. Baker and M. A. Ayechew, “A Genetic Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 30, No. 5, 2003, pp. 787-800. doi:10.1016/S0305-0548(02)00051-5
[47]	G. Jeon, H. R. Leep and J. Y. Shim, “A Vehicle Routing Problem Solved by Using a Hybrid Genetic Algorithm,” Computers & Industrial Engineering, Vol. 53, No. 4, 2007, pp. 680-692. doi:10.1016/j.cie.2007.06.031
[48]	S. J. Louis and G. Li, “Augmenting Genetic Algorithms with Memory to Solve Traveling Salesman Problems,” Proceedings of the Joint Conference on Information Sciences, 1997.
[49]	A. Acan and Y. Tekol, “Chromosome Reuse in Genetic Algorithms,” Lecture Notes in Computer Science, GECCO 2003, LNCS 2723, Springer-Verlag, Berlin, 2003, pp. 695-705.