Skip to main navigation menu Skip to main content Skip to site footer

Vol. 26 No. 46 (2017)

Papers

Comparative analysis of granular neighborhoods in a Tabu Search for the vehicle routing problem with heterogeneous fleet and variable costs (HFVRP)

https://doi.org/10.19053/01211129.v26.n46.2017.7321

Published 2017-09-05

John Wilmer Escobar
Universidad del Valle (Cali-Valle del Cauca, Colombia)

Wilson Adarme-Jaimes
Universidad Nacional de Colombia (Bogotá-Distrito Capital, Colombia)

Nicolás Clavijo-Buriticá
Pontificia Universidad Javeriana Cali (Cali-Valle del Cauca, Colombia).

Abstract

In the vehicle routing problem with heterogeneous fleet and variable costs (HFVRP), the group of routes to be developed to satisfy the demand of the customer must be determined, considering the minimization of the total costs of the travelled distance. Heuristic algorithms based on local searches use simple movements (neighborhoods) to generate feasible solutions to problems related to route design. In this article, we conduct a comparative analysis of granular neighborhoods in a Tabu Search for the HFVRP, in terms of the quality of the obtained solution. The computational experiments, performed on instances of benchmarking for the HFVRP, showed the efficiency and effectiveness of implementing some neighborhoods in metaheuristic algorithms of path, such as the Tabu Search.

Keywords

Granular neighborhoods, Heterogeneous fleet, Tabu search, Vehicle routing problems

PDF XML

References

  1. J. Engblom, T. Solakivi, J. Töyli, and L. Ojala. Multiple-method analysis of logistics costs, 2012. DOI: https://doi.org/10.1016/j.ijpe.2012.01.007
  2. J. K. Lenstra, and A. H. G. Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11 (2), pp. 221-227, 1981. DOI: http://doi.org/10.1002/net.3230110211. DOI: https://doi.org/10.1002/net.3230110211
  3. D. E. Puenayán, J.C. Londoño, J. W. Escobar, and R. Linfati. “Un algoritmo basado en búsqueda tabú granular para la solución de un problema de ruteo de vehículos considerando flota heterogénea,” Revista Ingenierías Universidad de Medellín, vol. 13 (25), pp. 81-98, 2014. DOI: https://doi.org/10.22395/rium.v13n25a6
  4. P. Toth, and D. Vigo, “The granular tabu search and its application to the vehicle-routing problem,” Informs Journal on Computing, vol. 15 (4), pp. 333-346, 2003. DOI: http://doi.org/10.1287/ijoc.15.4.333.24890. DOI: https://doi.org/10.1287/ijoc.15.4.333.24890
  5. M. Schneider, and A. Stenger, Designing granular solution methods for routing problems with time windows. Technical Report Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL), 2015.
  6. É. D. Taillard, “A heuristic column generation method for the heterogeneous fleet VRP. Revue française d'automatique, d'informatique et de recherche opérationnelle,” Recherche opérationnelle, vol. 33 (1), pp. 1-14, 1999.
  7. B. Golden, A. Assad, L. Levy, and F. Gheysens, “The fleet size and mix vehicle routing problem,” Computers & Operations Research, vol. 11 (1), pp. 49-66, 1984. DOI: http://doi.org/10.1016/0305-0548(84)90007-8. DOI: https://doi.org/10.1016/0305-0548(84)90007-8
  8. A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Computers & Operations Research, vol. 40 (10), pp. 2519-2531, 2013. DOI: http://doi.org/10.1016/j.cor.2013.01.013.
  9. R. Baldacci, and A. Mingozzi, “A unified exact method for solving different classes of vehicle routing problems,” Mathematical Programming, vol. 120 (2), pp. 347-380, 2009. DOI: http://doi.org/10.1007/s10107-008-0218-9. DOI: https://doi.org/10.1007/s10107-008-0218-9
  10. A. Subramanian, P. H. V. Penna, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for the heterogeneous fleet vehicle routing problem,” European Journal of Operational Research, vol. 221 (2), pp. 285-295, 2012. DOI: http://doi.org/10.1016/j.ejor.2012.03.016. DOI: https://doi.org/10.1016/j.ejor.2012.03.016
  11. A. Subramanian, E. Uchoa, and L. S. Ochi, “A hybrid algorithm for a class of vehicle routing problems,” Computers & Operations Research, vol. 40 (10), pp. 2519-2531, 2013. DOI: http://doi.org/10.1016/j.cor.2013.01.013. DOI: https://doi.org/10.1016/j.cor.2013.01.013
  12. J. Brandão, “A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem,” Computers & Operations Research, vol. 38 (1), pp.140-151, 2011. DOI: http://doi.org/10.1016/j.cor.2010.04.008. DOI: https://doi.org/10.1016/j.cor.2010.04.008
  13. J. Brandão, “A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem,” European Journal of Operational Research, vol. 195 (3), pp. 716-728, 2009. DOI: http://doi.org/10.1016/j.ejor.2007.05.059. DOI: https://doi.org/10.1016/j.ejor.2007.05.059
  14. H. Jia, Y. Li, B. Dong, and H. Ya, “An improved tabu search approach to vehicle routing problem,” Procedia-Social and Behavioral Sciences, vol. 96, pp.1208-1217, 2013. DOI: http://doi.org/10.1016/j.sbspro.2013.08.138. DOI: https://doi.org/10.1016/j.sbspro.2013.08.138
  15. L. S. Ochi, D. S. Vianna, L. M. Drummond, and A. O. Victor, “An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet,” Genetic programming, Springer Berlin Heidelberg, pp. 187-195, 1998. DOI: http://doi.org/10.1007/BFb0055938. DOI: https://doi.org/10.1007/BFb0055938
  16. L. S. Ochi, D. S. Vianna, L. M. Drummond, and A. O. Victor, “A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet,” Parallel and Distributed Processing, Springer Berlin Heidelberg, pp. 216-224, 1998. DOI: http://doi.org/10.1007/3-540-64359-1_691. DOI: https://doi.org/10.1007/3-540-64359-1_691
  17. P. H. V. Penna, A. Subramanian, and L. S. Ochi, “An iterated local search heuristic for the heterogeneous fleet vehicle routing problem,” Journal of Heuristics, vol. 19 (2), pp.201-232, 2013. DOI: http://doi.org/10.1007/s10732-011-9186-y. DOI: https://doi.org/10.1007/s10732-011-9186-y
  18. A. Imran, A. Salhi, and N. A. Wassan, “A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem,” European Journal of Operational Research, vol. 197(2), pp. 509-518, 2009. DOI: http://doi.org/10.1016/j.ejor.2008.07.022. DOI: https://doi.org/10.1016/j.ejor.2008.07.022
  19. C. Prins, “Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case,” Journal of Mathematical Modelling and Algorithms, vol. 1 (2), pp. 135-150, 2002. DOI: http://doi.org/10.1023/A:1016516326823. DOI: https://doi.org/10.1023/A:1016516326823
  20. X. Li, P. Tian, and Y. P. Aneja, “An adaptive memory programming metaheuristic for the heterogeneous fixed fleet vehicle routing problem,” Transportation Research Part E: Logistics and Transportation Review, vol. 46 (6), pp.1111-1127, 2010. DOI: http://doi.org/10.1016/j.tre.2010.02.004. DOI: https://doi.org/10.1016/j.tre.2010.02.004
  21. C. D. Tarantilis, C. T. Kiranoudis, and V. S. Vassiliadis, “A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem” Journal of the Operational Research Society, vol. 54 (1), pp. 65-71, 2003. DOI: http://doi.org/10.1057/palgrave.jors.2601443. DOI: https://doi.org/10.1057/palgrave.jors.2601443
  22. F. Li, B. Golden, and E. Wasil, “A record-to-record travel algorithm for solving the heterogeneous fleet vehicle routing problem,” Computers & Operations Research, vol. 34 (9), pp.2734-2742, 2007. DOI: http://doi.org/10.1016/j.cor.2005.10.015. DOI: https://doi.org/10.1016/j.cor.2005.10.015
  23. J. W. Escobar, and R. Linfati, “Un algoritmo metaheurístico basado en recocido simulado con espacio de búsqueda granular para el problema de localización y ruteo con restricciones de capacidad,” Revista Ingenierías Universidad de Medellín, vol. 11 (21), pp. 139-150, 2012.
  24. J. W. Escobar, R. Linfati, and P. Toth, “A two-phase hybrid heuristic algorithm for the capacitated location-routing problem,” Computers & Operations Research, vol. 40 (1), pp.70-79, 2013. DOI: http://doi.org/10.1016/j.cor.2012.05.008. DOI: https://doi.org/10.1016/j.cor.2012.05.008
  25. J. W. Escobar, R. Linfati, M. G. Baldoquin, and P. Toth, “A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem,” Transportation Research Part B, vol. 67 (C), pp. 344-356, 2014. DOI: http://doi.org/10.1016/j.trb.2014.05.014. DOI: https://doi.org/10.1016/j.trb.2014.05.014
  26. J. W. Escobar, R. Linfati, P. Toth, and M. G. Baldoquin, “A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem,” Journal of Heuristics, vol. 20 (5), pp. 483-509, 2014. DOI: http://doi.org/10.1007/s10732-014-9247-0. DOI: https://doi.org/10.1007/s10732-014-9247-0
  27. J. W. Escobar, “Heuristic Algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem,” 4OR - A Quarterly Journal of Operations Research, vol. 12 (1), pp. 99-100, 2014. DOI: https://doi.org/10.1007/s10288-013-0241-4
  28. R. Linfati, J. W. Escobar, and G. Gatica, “Un algoritmo metaheurístico para el problema de localización y ruteo con flota heterogénea,” Ingeniería y Ciencia, vol. 10 (19), pp.55-76, 2014. DOI: http://doi.org/10.17230/ingciencia.10.19.3. DOI: https://doi.org/10.17230/ingciencia.10.19.3
  29. R. Linfati, J. W. Escobar, and B. Cuevas, “An algorithm based on granular tabu search for the problem of balancing public bikes by using multiple vehicles,” Dyna, vol. 81 (186), pp.284-294, 2014. DOI: http://doi.org/10.15446/dyna.v81n186.45220. DOI: https://doi.org/10.15446/dyna.v81n186.45220
  30. J. W. Escobar, R. Linfati, and W. Adarme, “Un algoritmo metaheurístico híbrido para el problema de localización y ruteo con restricciones de capacidad,” Revista DYNA, vol. 82 (189), pp. 243-251, 2015. DOI: https://doi.org/10.15446/dyna.v82n189.48552
  31. S. Eilon, C. D. T. Watson-Gandy, and N. Christofides, Distribution management. London: Griffin, 1971.
  32. N. Christofides, A. Mingozzi, and P. Toth, Loading problems. N. Christofides and al., editors, Combinatorial Optimization, pp. 339-369, 1979.
  33. B. L. Golden, G. Laporte, and É. D. Taillard, “An adaptive memory heuristic for a class of vehicle routing problems with minmax objective,” Computers & Operations Research, vol. 24 (5), pp. 445-452, 1997. DOI: http://doi.org/10.1016/S0305-0548(96)00065-2. DOI: https://doi.org/10.1016/S0305-0548(96)00065-2
  34. J. Bernal J. W. Escobar, J. C. Paz, G. Gatica, and R. Linfati, “A probabilistic Granular Tabu Search for the Distance Constrained Capacitated Vehicle Routing Problem (DCVRP),” Journal of Industrial and Systems Engineering, pre-print.
  35. J. Bernal, J. W. Escobar, C. Marin, R. Linfati, and G. Gatica, “A comparison of granular heuristic algorithms for the Location-Routing Problem with Heterogeneous Fleet (LRPH),” Dyna, vol. 84 (200), pp. 193-201, 2017. DOI: http://doi.org/10.15446/dyna.v84n200.55533. DOI: https://doi.org/10.15446/dyna.v84n200.55533

Downloads

Download data is not yet available.