Una comparación de algoritmos basados en trayectoria granular para el problema de localización y ruteo con flota heterogénea (LRPH)

Publicado

2017-01-01

A comparison of trajectory granular based algorithms for the location-routing problem with heterogeneous fleet (LRPH)

Una comparación de algoritmos basados en trayectoria granular para el problema de localización y ruteo con flota heterogénea (LRPH)

Palabras clave:

Location-routing problem, heterogeneous fleet, simulated annealing, variable neighborhood search, probabilistic tabu search, metaheuristic algorithms (en)
Problema de localización y ruteo, flota heterogénea, recocido simulado, búsqueda de vecindario variable, búsqueda tabú probabilística, algoritmos metaheurísticos (es)

Descargas

Autores/as

José Alfonso Bernal-Moyano Universidad del Valle https://orcid.org/0000-0003-3167-5134
John Willmer Escobar Velasquez University of Bologna https://orcid.org/0000-0001-6175-9553
Cesar Marín-Moreno Universidad Tecnológica de Pereira https://orcid.org/0000-0002-7354-7838
Rodrigo Linfati Universidad del Bío-Bío https://orcid.org/0000-0002-7659-383X
Gustavo Gatica Universidad Andres Bello https://orcid.org/0000-0002-1816-6856

Resumen (en)
Resumen (es)

We consider the Location-Routing Problem with Heterogeneous Fleet (LRPH) in which the goal is to determine the depots to be opened, the customers to be assigned to each open depot, and the corresponding routes fulfilling the demand of the customers and by considering a heterogeneous fleet. We propose a comparison of granular approaches of Simulated Annealing (GSA), of Variable Neighborhood Search (GVNS) and of a probabilistic Tabu Search (pGTS) for the LRPH. Thus, the proposed approaches consider a subset of the search space in which non-favorable movements are discarded regarding a granularity factor. The proposed algorithms are experimentally compared for the solution of the LRPH, by taking into account the CPU time and the quality of the solutions obtained on the instances adapted from the literature. The computational results show that algorithm GSA is able to obtain high quality solutions within short CPU times, improving the results obtained by the other proposed approaches.

Nosotros consideramos el problema de localización y ruteo de vehículos con flota heterogénea (LRPH) en el cual la meta es determinar los depósitos a ser abiertos, los clientes asignados a cada deposito, y las rutas que satisfagan la demanda de los clientes considerando una flota heterogénea. Nosotros proponemos una comparación de algoritmos granulares de Recocido Simulado (GSA), Búsqueda de Vecindario Variable (GVNS) y Tabú Search probabilístico (pGTS) para el LRPH. De esta manera, los algoritmos propuestos consideran un subconjunto del espacio en el cual los movimientos menos favorables son descartados según un factor de granularidad. Los algoritmos propuestos son comparados experimentalmente para la solución del LRPH, considerando el tiempo de CPU y la calidad de la solución obtenida en instancias adaptadas de la literatura. Los resultados computacionales muestran que el algoritmos GSA es capaz de obtener buenas soluciones en tiempos computacionales reducidos, mejorando los resultados obtenidos por los otros algoritmos propuestos.

Descargas

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

Citas

Applegate, D.L., Bixby, R.E., Chvatal, V. and Cook, W.J., The traveling salesman problem: A computational study (Princeton series in applied mathematics), Princeton, NJ, USA, Princeton University Press, 2007.

Garey, M.R. and Johnson, D.S., Computers and Intractability; A guide to the theory of NP-Completeness, New York, NY, USA, W.H. Freeman & Co., 1990.

Fortnow, L., The status of the P versus NP problem, Commun. ACM, 52(9), pp. 78-86, 2009. DOI: 10.1145/1562164.1562186

Linfati, R., Escobar, J.W. y Gatica, G., Un algoritmo metaheurístico para el problema de localización y ruteo con flota heterogénea, Ingeniería y Ciencia, 10(19), pp. 55-76, 2014. DOI: 10.17230/ingciencia.10.19.3

Escobar, J.W., Heuristic algorithms for the capacitated location-routing problem and the multi-depot vehicle routing problem, 4OR, 12(1), pp. 99-100, 2014. DOI: 10.1007/s10288-013-0241-4.

Escobar, J.W., Linfati, R. and Toth, P., A two-phase hybrid heuristic algorithm for the capacitated location-routing problem, Computers & Operations Research, 40(1), pp. 70-79, 2013. DOI: 10.1016/j.cor.2012.05.008

Escobar, J.W., Linfati, R., Baldoquin, M.G. and Toth, P., A granular variable tabu neighborhood search for the capacitated location- routing problem, Transportation Research Part B: Methodological, 67, pp. 344-356, 2014. DOI: 10.1016/j.trb.2014.05.014.

Escobar, J.W., Linfati, R. and Adarme-Jaimes, W., A hybrid metaheuristic algorithm for the capacitated location routing problem, DYNA, 82(189), 243-251, 2015. DOI: 10.15446/dyna.v82n189.48552.

Bookbinder, J.H. and Reece, K.E., Vehicle routing considerations in distribution system design, European Journal of Operational Research, 37(2), pp. 204-213, 1988. DOI: 10.1016/0377-2217(88)90330-X.

Salhi, S. and Fraser, M., An integrated heuristic approach for the combined location vehicle fleet mix problem, Studies in Locational Analysis, 8, pp. 3-21, 1996.

Wu, T.H., Low, C. and Bai, J.W., Heuristic solutions to multi-depot location-routing problems, Computers & Operations Research, 29(10) pp. 1393-1415, 2002. DOI: 10.1016/S0305-0548(01)00038-7.

Ambrosino, D. and Grazia, M., Distribution network design: New problems and related models, European Journal of Operational Research, 165(3), pp. 610-624, 2005. DOI: 10.1016/j.ejor.2003.04.009.

Gunnarsson, H., Rönnqvist, M. and Carlsson, D., A combined terminal location and ship routing problem, Journal of the Operational Research Society, 57(8), pp. 928-938, 2005. DOI: 10.1057/palgrave.jors.2602057.

Toth, P. and Vigo, D., The granular tabu search and its application to the vehicle-routing problem, INFORMS Journal on Computing, 15(4), pp. 333-346, 2003. DOI: 10.1287/ijoc.15.4.333.24890.

Salhi, S., Imran, A. and Wassan, N.A., The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation, Computers & Operations Research, 52(1), pp. 315-325, 2014. DOI: 10.1016/j.cor.2013.05.011.

Lin, S. and Kernighan, B., An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21(2), pp. 498-516, 1973. DOI: 10.1287/opre.21.2.498.

Helsgaun, K., An effective implementation of the Lin-Kernighan traveling salesman heuristic, European Journal of Operational Research, 126(1), pp. 106-130, 2000. DOI: 10.1016/S0377-2217(99)00284-2.

Barcelo, J. and Casanovas, J., A heuristic Lagrangean algorithm for the capacitated plant location problem, European Journal of Operational Research, 15(2), pp. 212-226, 1984. DOI: 10.1016/0377-2217(84)90211-X.

Klincewicz, J. and Luss, H., A Lagrangian relaxation heuristic for capacitated facility location with single-source constraints, Journal of the Operational Research Society, 37(5), pp. 495-500, 1986. DOI: 10.2307/2582672.

Mladenović, N. and Hansen, P., Variable neighborhood search. Computers & Operations Research, 24(11), pp. 1097-1100, 1997. DOI: 10.1016/S0305-0548(97)00031-2.

Bernal, J., Escobar, J.M, Paz, J.C., Linfati, R. and Gatica, G., A probabilistic granular tabu search for the distance constrained capacitated vehicle routing problem, Int. J. Industrial and Systems Engineering, In press, 2016.

Gendreau, M., Hertz, A. and Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40(10), pp. 1276-1290, 1994. DOI: 10.1287/mnsc.40.10.1276.

Tuzun, D. and Burke, L., A two-phase tabu search approach to the location routing problem, European Journal of Operational Research, 116(1), pp. 87-99. DOI: 10.1016/S0377-2217(98)00107-6

Prins, C., Prodhon, C. and Wolfler-Calvo, R., Nouveaux algorithmes pour le problème de localisation et routage sous contraintes de capacité, MOSIM, 4(2), pp. 1115-1122, 2004.

Barreto, S., Análise e Modelização de Problemas de localização-distribuição. PhD Thesis, University of Aveiro, Aveiro, Portugal, 2004, 340 P.

Golden, B., Assad, A., Levy, L. and Gheysens, F., The fleet size and mix vehicle routing problem, Computers & Operations Research, 11(1), pp. 49-66, 1984. DOI: 10.1016/0305-0548(84)90007-8.

Licencia

Derechos de autor 2017 DYNA

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.

El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.