A New Approach to the Optimization of the CVRP through Genetic Algorithms

Mariano Frutos, Fernando Tohmé

Department of Economics, National University of the South, Bahía Blanca, Argentina.
Department of Engineering, National University of the South, Bahía Blanca, Argentina.

DOI: 10.4236/ajor.2012.24058                

Abstract

This paper presents a new approach to the analysis of complex distribution problems under capacity constraints. These problems are known in the literature as CVRPs (Capacitated Vehicle Routing Problems). The procedure introduced in this paper optimizes a transformed variant of a CVRP. It starts generating feasible clusters and codifies their ordering. In the next stage the procedure feeds this information into a genetic algorithm for its optimization. This makes the algorithm independent of the constraints and improves its performance. Van Breedam problems have been used to test this technique. While the results obtained are similar to those in other works, the processing times are longer.

Keywords

Vehicle Routing Problem; Genetic Algorithms; Modeling; Optimization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	D. Ambrosino and A. Sciomachen, “A Food Distribution Network Problem: A Case Study,” IMA Journal of Management Mathematics, Vol. 18, No. 1, 2007, pp. 33-53. doi:10.1093/imaman/dpl012
[2]	L. D. Bodin and B. L. Golden, “Classification in Vehicle Routing and Scheduling,” Networks, Vol. 11. No. 2, 1981, pp. 97-108. doi:10.1002/net.3230110204
[3]	S. N. Kumar and R. Panneerselvam, “A Survey on the Vehicle Routing Problem and Its Variants,” Intelligent Information Management, Vol. 4, No. 3, 2012, pp. 66-74. doi:10.4236/iim.2012.43010
[4]	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
[5]	E. Mota, V. Campos and A. Corbéran, “A New Metaheuristic for the Vehicle Routing Problem with Split Demands,” In: J. van Hemert and C. Cotta, Eds., Evolutionary Computation in Combinatorial Optimization, Lecture Notes in Computer Science Vol. 4446, Springer-Verlag, Berlin, 2007, pp. 121-129. doi:10.1007/978-3-540-71615-0_11
[6]	R. Tavakkoli-Moghaddam, N. Safaei, M. Kah and M. Rabbani, “A New Capacitated Vehicle Routing Problem with Split Service for Minimizing Fleet Cost by Simulated Annealing,” Journal of the Franklin Institute, Vol. 344, No. 5, 2007, pp. 406-425. doi:10.1016/j.jfranklin.2005.12.002
[7]	J. M. Belenguer, E. Benavent, N. Labadi, C. Prins and M. Reghioui, “Split Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic,” Transportation Science, Vol. 44, No. 2, 2010, pp. 206-220. doi:10.1287/trsc.1090.0305
[8]	S. R. Thangiah, A. Fergany and S. Awan, “Real-Time Split-Delivery Pickup and Delivery Time Window Problems with Transfers,” Central European Journal of Operations Research, Vol. 15, No. 4, 2007, pp. 329-349. doi:10.1007/s10100-007-0035-x
[9]	M. Desrochers, J. Desrosiers and M. M. Solomon, “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows,” Operations Research, Vol. 40, No. 2, 1002, pp. 342-354. doi:10.1287/opre.40.2.342
[10]	C. G. Lee, M. A. Epelman, C. White and Y. A. Bozer, “A Shortest Path Approach to the Multiple-Vehicle Routing Problem with Split Pick-Ups,” Transportation Research, Vol. 40, No. 4, 2006, pp. 265-284. doi:10.1016/j.trb.2004.11.004
[11]	P. Belfiore and H. T. I. Yoshizaki, “Scatter Search for a Real-Life Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries in Brazil,” European Journal of Operational Research, Vol. 199, No. 3, 2009, pp. 750-758. doi:10.1016/j.ejor.2008.08.003
[12]	J. H. Wilck IV and T. M. Cavalier, “A Construction Heuristic for the Split Delivery Vehicle Routing,” American Journal of Operations Research, Vol. 2, No. 2, 2012, pp. 153-162. doi:10.4236/ajor.2012.22018
[13]	Y. Nagao and H. Nagamochi, “A DP-Based Heuristic Algorithm for the Discrete Split Delivery Vehicle Routing Problem,” Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vol. 1, No. 2, 2007, pp. 217-226. doi:10.1299/jamdsm.1.217
[14]	Y. Yu, H. Chen and F. Chu, “A New Model and Hybrid Approach for Large Scale Inventory Routing Problems,” European Journal of Operational Research, Vol. 189, No. 3, 2008, pp. 1022-1040. doi:10.1016/j.ejor.2007.02.061
[15]	M. A. Nowak, O. Ergun and C. C. White, “An Empirical Study on the Benefit of Split Loads with the Pickup and Delivery Problem,” European Journal of Operational Research, Vol. 198, No. 3, 2009, pp. 734-740. doi:10.1016/j.ejor.2008.09.041
[16]	Z. Shen, M. M. Dessouky and F. Ordó?ez, “A Two-Stage Vehicle Routing Model for Large-Scale Bioterrorism Emergencies,” Networks, Vol. 54, No. 4, 2009, pp. 255-269. doi:10.1002/net.20337
[17]	L. Moreno, M. P. de Aragao and E. Uchoa, “Improved Lower Bounds for the Split Delivery Vehicle Routing Problem,” Operations Research Letters, Vol. 38, No. 4, 2010, pp. 302-306. doi:10.1016/j.orl.2010.04.008
[18]	M.-C. Bolduc, G. Laporte, J. Renaud and F. F. Boctor, “A Tabu Search Heuristic for the Split Delivery Vehicle Routing Problem with Production and Demand Calendars,” European Journal of Operational Research, Vol. 202, No. 1, 2010, pp. 122-130. doi:10.1016/j.ejor.2009.05.008
[19]	U. Derigs, B. Li and U. Vogel, “Local Search-Based Metaheuristics for the Split Delivery Vehicle Routing Problem,” Journal of the Operational Research Society, Vol. 61, No. 9, 2009, pp. 1356-1364. doi:10.1057/jors.2009.100
[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]	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. doi:10.1504/IJMHEUR.2010.033123
[22]	R. E. Aleman, X. Zhang and R. R. Hill, “An Adaptive Memory Algorithm for the Split Delivery Vehicle Routing Problem,” Journal of Heuristics, Vol. 16, No. 3, 2010, pp. 441-473. doi:10.1007/s10732-008-9101-3
[23]	S. Basu, “Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey,” American Journal of Operations Research, Vol. 2 No. 2, 2012, pp. 163-173. doi:10.4236/ajor.2012.22019
[24]	D. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley Longman Publishing Co., Inc., Boston, 1989.
[25]	A. Van Breedam, “An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selection of Problems with Vehicle Related, Customer-Related, and Time-Related Constraints,” Ph.D. Thesis, University of Antwerp—RUCA, Antwerpen, 1994.
[26]	E. Alba and B. Dorronsoro, “A Hybrid Cellular Genetic Algorithm for the Capacitated Vehicle Routing Problem,” In: Engineering Evolutionary Intelligent Systems, Chapter 13, Studies in Computational Intelligence, Springer- Verlag, Heidelberg, 2008, pp. 379-422. doi:10.1007/978-3-540-75396-4_14