ISSN-L: 0798-1015   •   eISSN: 2739-0071 (En línea)

Vol. 42 (Nº 16) Año 2021. Art. 1

Recibido: 02/04/2020 • Aprobado: 15/08/2021 • Publicado 30/08/2021
DOI: 10.48082/espacios-a21v42n16p01

Heuristic algorithm based on Ant Colony Optimization for the Capacitated Location-Routing problem with Homogeneous Fleet

Algoritmo heurístico basado en optimización para el problema de localización y ruteo con flota homogenea

GATICA, Gustavo 1
ESCOBAR, John W.2
LINFATI, Rodrigo 3 

Abstract
This paper considers the Capacitated Location-Routing Problem with Homogeneous Fleet (CLRP). The objective is to minimize the sum of the open depots' costs, the costs for the used vehicles, and the costs associated with the distances traveled. A metaheuristic algorithm of two phases for the CLRP is proposed. In the first phase, customers establish the clusters to be subsequently heuristically assigned to the depots. In the second phase, the initial routes are improved using an algorithm based on Ant Colony. The obtained results show the efficiency of the proposed approach.
Key words: capacitated location routing, ant colony, metaheuristic

Resumen
Este artículo considera el problema de localización y ruteo capacitado con flota homogénea (CLRP). El objetivo es minimizar la suma de los costos de los depósitos abiertos, los costos de los vehículos usados y los costos asociados con las distancias recorridas. Se propone un algoritmo metaheurístico de dos fases para el CLRP. En la primera fase, los clústeres son establecidos por los clientes para luego ser asignados heurísticamente a los depósitos. En la segunda fase, se mejoran las rutas iniciales mediante un algoritmo basado en Colonia de Hormigas. Los resultados obtenidos muestran la eficiencia del algoritmo propuesto.
Palabras clave: localizacion y ruteo capacitado, colonia de hormigas, metaheurística

FULL VERSION

References

Asmar, D., Elshamli, A., & Areibi, S. (2005). A comparative assessment of ACO algorithms within a TSP environment. Dynamics of Continous Discrete and Impulsive Systems-Series B-Applications & Algorithms, 1, 462-467.

Baldacci, R., Mingozzi, A., & Wolfler Calvo, R. (2011). An exact method for the capacitated location-routing problem. Operations research, 59(5), 1284-1296.

Barceló, J., & Casanovas, J. (1984). A heuristic Lagrangean algorithm for the capacitated plant location problem. European Journal of Operational Research, 15(2), 212-226.

Barreto, S. D. S. (2004). Análise e Modelização de Problemas de localização-distribuição (Doctoral dissertation, Universidade de Aveiro).

Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959). The shortest path through many points. In Mathematical Proceedings of the Cambridge Philosophical Society. Vol. 55, No. 4, pp. 299-327. Cambridge University Press.

Belenguer, J. M., Benavent, E., Prins, C., Prodhon, C., & Calvo, R. W. (2011). A branch-and-cut method for the capacitated location-routing problem. Computers & Operations Research, 38(6), 931-941.

Caballero, R., González, M., Guerrero, F. M., Molina, J., & Paralera, C. (2007). Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia. European Journal of Operational Research, 177(3), 1751-1763.

Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4), 568-581.

Colorni, A., Dorigo, M., & Maniezzo, V. (1992). An Investigation of some Properties of an" Ant Algorithm". In Ppsn, Vol. 92, No. 1992.

Contardo, Claudio., Cordeau, J. F., & Gendron, Bernard (2010). A branch-and-cut algorithm for the capacitated location-routing problem. In Conference CAOR (Vol. 10).

Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.

Dorigo, M. (1992). Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano.

Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.

Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66.

Dorigo M., Stützle T. (2019) Ant Colony Optimization: Overview and Recent Advances. In: Gendreau M., Potvin JY. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 272. Springer, Cham. https://doi.org/10.1007/978-3-319-91086-4_10.

Duhamel, C., Lacomme, P., Prins, C., & Prodhon, C. (2010). A GRASP× ELS approach for the capacitated location-routing problem. Computers & Operations Research, 37(11), 1912-1923.

Escobar, J. W., & Linfati, R. (2012). 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, 11(21), 139-150. Available in https://revistas.udem.edu.co/index.php/ingenierias/article/view/604/545

Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1), 70-79.

Escobar, J. W., Linfati, R., & Adarme-Jaimes, W. (2015). A hybrid metaheuristic algorithm for the capacitated location routing problem. Dyna, 82(189), 243-251.

Farkavcova, V. G., Rieckhof, R., & Guenther, E. (2018). Expanding knowledge on environmental impacts of transport processes for more sustainable supply chain decisions: A case study using life cycle assessment. Transportation Research Part D: Transport and Environment, 61, 68-83.

García, L. A. M. (2016). GESTION LOGISTICA INTEGRAL: las mejores practicas en la cadena de abastecimiento . Ecoe Ediciones. Retrieved from: https://www.ecoeediciones.com/wp-content/uploads/2016/12/Gestion-logistica-integral-2da-Edici%C3%B3n.pdf

Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman & Co. New York, NY, USA.

Harks, T., König, F. G., & Matuschke, J. (2013). Approximation algorithms for capacitated location routing. Transportation Science, 47(1), 3-22.

Helsgaun, K. (2000). An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130.

i Cos, J. P., & De Navascués, R. (1998). Manual de logística integral. Ediciones Díaz de Santos. Retrieved from: http://www.diazdesantos.com.co/libros/pau-i-cos-jordi-manual-de-logistica-integral-L03003450303.html

Laporte, G., Louveaux, F., & Mercure, H. (1989). Models and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research, 39(1), 71-78.

Linfati, R., Escobar, J. W., & Gatica, G. (2014). A metaheuristic algorithm for the location routing problem with heterogeneous fleet. Ingeniería y Ciencia, 10(19), 55-76.

Luna López, L. C. (2015). Localización de paradas y diseño óptimo de rutas para transporte de personal (Doctoral dissertation, Universidad Autónoma de Nuevo León).  Retrieved from: http://eprints.uanl.mx/9541/1/1080214944.pdf

Mehrjerdi, Y. Z., & Nadizadeh, A. (2013). Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. European Journal of Operational Research, 229(1), 75-84.

Negrotto, D. (2015). Algoritmos para el problema de localización y ruteo de vehículos con capacidades y premios (Doctoral dissertation, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Retrieved from: https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5818_Negrotto.pdf

Prins, C., Prodhon, C., & Calvo, R. W. (2006a). A memetic algorithm with population management (MA| PM) for the capacitated location-routing problem. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 183-194). Springer, Berlin, Heidelberg.

Prins, C., Prodhon, C., & Calvo, R. W. (2006b). Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR, 4(3), 221-238.

Prins, C., Prodhon, C., Ruiz, A., Soriano, P., & Wolfler Calvo, R. (2007). Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabu search heuristic. Transportation Science, 41(4), 470-483.

Stützle, T., & Ruiz, R. (2018). Iterated Local Search: A Concise Review. IRIDIA, Institut de Recherches Interdisciplinaires et de D´eveloppements en Intelligence Artificielle, Universite Libre de Bruxelles, Technical Report. Belgium

Tokgoz, E., & Trafalis, T. B. (2014). Manifold Location Routing Problem with Applications in Network Theory. In International Conference on Network Analysis, pp. 89-114. Springer, Cham.

Toro, E. M., Franco, J. F., Echeverri, M. G., & Guimarães, F. G. (2017). A multi-objective model for the green capacitated location-routing problem considering environmental impact. Computers & Industrial Engineering, 110, 114-125.

Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1-3), 487-512.

Tuzun, D., & Burke, L. I. (1999). A two-phase tabu search approach to the location routing problem. European journal of operational research, 116(1), 87-99.

Vasquez Delgado (2012), Implementación de un algoritmo basado en la Búsqueda Tabú para la resolución de un problema de ruteo de vehículos con ventana temporal de acceso. Capítulo 4 resolución del problema de ruteo de vehículos VRP, Francisco de asís. Escuela técnica superior de ingenieros, Universidad de Sevilla. pp. 27-39.

Vincent, F. Y., Lin, S. W., Lee, W., & Ting, C. J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288-299.

Watson-Gandy, C. D. T., & Dohrn, P. J. (1973). Depot location with van salesmen—a practical approach. Omega, 1(3), 321-329.

Webb, M. H. J. (1968). Cost functions in the location of depots for multiple-delivery journeys. Journal of the Operational Research Society, 19(3), 311-320.

Wu, T. H., Low, C., & Bai, J. W. (2002). Heuristic solutions to multi-depot location-routing problems. Computers & Operations Research, 29(10), 1393-1415.

1. Full Professor. Faculty of Engineering. Universidad Andres Bello. Chile. Contact e-mail.  ggatica@unab.cl

2. Full Professor. Department of Accouting and Finance. Universidad del Valle. Colombia. Contact e-mail.  john.wilmer.escobar@correounivalle.edu.co

3. Full Professor. Department of Industrial Engineering. Universidad del del Bío-Bío. Chile. Contact e-mail.  rlinfati@ubiobio.cl