Ir al menú de navegación principal Ir al contenido principal Ir al pie de página del sitio

Vol. 26 Núm. 46 (2017)

Articulos

Análisis comparativo de vecindarios granulares en una búsqueda tabú para el problema de ruteo de vehículos con flota heterogénea y costos variables (HFVRP)

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

Publicado 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).

Resumen

En el problema de ruteo de vehículos con flota heterogénea y costos variables (HFVRP) se debe determinar el conjunto de rutas que se han de desarrollar para satisfacer las demandas de los clientes, teniendo en cuenta la minimización de la suma de los costos totales de la distancia recorrida. Algoritmos heurísticos basados en búsquedas locales utilizan comúnmente movimientos simples (vecindarios) para generar soluciones factibles en problemas relacionados con diseños de rutas. En este artículo se realiza un análisis comparativo de vecindarios granulares en una búsqueda tabú para el HFVRP. La comparación se ha realizado en términos de la calidad de la solución encontrada. Los experimentos computacionales, realizados sobre instancias de benchmarking para el HFVRP, muestran la eficiencia y efectividad de la implementación de algunos vecindarios en algoritmos metaheurísticos de trayectoria, como es la Búsqueda Tabú.

Palabras clave

Búsqueda tabú, Flota heterogénea, Problema de ruteo de vehículos, Vecindarios granulares

PDF (English) XML (English)

Citas

  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

Descargas

Los datos de descargas todavía no están disponibles.