ISSN 0718-3291 Versión Impresa

ISSN 0718-3305 Versión en línea

Volumen 17 N° 2, Mayo - Agosto 2009

pdf Índice

Modelo ACO para la recolección de residuos por contenedores

Eduardo Salazar Hornig1                  Nelson Ruiz Fuentealba2

  

1 Departamento de Ingeniería Industrial. Universidad de Concepción. Casilla 160-C. Concepción, Chile. E-mail: esalazar@udec.cl
2 Programa de Magíster en Ingeniería Industrial. Universidad de Concepción. Concepción, Chile.


RESUMEN

ACO es una metaheurística inspirada en el comportamiento de las colonias de hormigas para solucionar problemas de optimización combinatoria, por medio de la utilización de agentes computacionales simples que trabajan de manera cooperativa y se comunican mediante rastros de feromona artificiales. En este trabajo se presenta un modelo para resolver el Problema de Recolección de Residuos Domiciliarios por Contenedores, el que aplica un concepto de secuencias parciales de recolección que deben ser unidas para minimizar la distancia total de recolección. El problema de unir las secuencias parciales se representa como un TSP, el que es resuelto mediante un algoritmo ACO. En base a recomendaciones de la literatura, se calibran experimentalmente los parámetros del algoritmo y se recomiendan rangos de valores que representan buenos rendimientos promedio. El modelo se aplica a un sector de recolección de la comuna de San Pedro de la Paz, Chile, obteniéndose rutas de recolección que reducen la distancia total recorrida respecto de la actual ruta utilizada y de la solución obtenida con otro modelo desarrollado previamente.

Palabras clave: Recolección de residuos domiciliarios, contenedores, optimización de rutas, TSP, ACO.

 

ABSTRACT 

ACO is a metaheuristic inspired in the behavior of natural ant colonies to solve combinatorial optimization problems, based on simple agents that work cooperatively communicating by artificial pheromone trails. In this paper a model to solve the municipal waste collection problem by containers is presented, which applies a concept of partial collection sequences that must be joined to minimize the total collection distance. The problem to join the partial collection sequences is represented as a TSP, which is solved by an ACO algorithm. Based on the literature, algorithm parameters are experimentally calibrated and range of variations that represents good average solutions are recommended. The model is applied to a waste collection sector of the San Pedro de la Paz commune in Chile, obtaining recollection routes with less total distance with respect to the actual route utilized and to the solution obtained by a previously developed approach. 

Keywords: Waste collection, containers, route optimization, TSP, ACO.


REFERENCIAS 

[1] R. Abu and H. Hiyassat. "Optimizing the Parameters of Ant Colony Algorithms using the Genetic". Proc. International Conference on Computational Intelligence, ICCI 2004, pp. 228-231. 2004.

[2] A. Agarwal, M.H. Lim, M.J. Er and C.Y. Chew. "ACO for a New TSP in Region Coverage". Proc. IEEE/RCJ International Conference of Intelligent Robots & Systems (IROS 2005), pp. 3176-3181. 2005.

[3] L. Anderson and A. Nigam. "A Mathematical Model for the Optimization of Waste Management System". Report No. 68-1. Sanitary Engineering Research Laboratory (SERL). University of California at Berkeley,USA. 1968.

[4] D. Asmar, A. Elshamli and S. Areibi. "A Comparative Assessment of ACO Algorithms within a TSP Environment". Dynamics of Continuous Discrete and Impulsive Systems - Series B - Applications & Algorithms 1, pp. 462-467, Special Issue SI 2005.

[5] L. Bodin, G. Fagin, R. Welebny and J. Greenberg. "The Design of a Computerized Sanitation Vehicle Routing and Scheduling System for the Town of the Oyster Bay, New York". Computers and Operations Research. Vol. 16 Nº 1, pp. 45-54. 1989.

[6] G. Clarke and J. Wright. "Scheduling of Vehicles From a Central Depot to a Number of Delivery Points". Operations Research. Vol. 12 Nº 4, pp. 568-581. 1964.

[7] M. Dorigo, G. Di Caro, L. Gambardella. "Ant Algorithms for Discrete Optimization". Artificial Life. Vol. 5 Nº 2, pp. 137-172. 1999.

[8] M. Dorigo and G. Di Caro. "The Ant Colony Optimization Metaheuristics - New Ideas in Optimization". Mc.Graw Hill, London UK, pp. 11-32. 1999.

[9] M. Dorigo and L. Gambardella. "Ant Colonies for the Traveling Salesman Problem". BioSystems, Vol. 43, pp. 73-81. 1997a.

[10] M. Dorigo and L. Gambardella. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem". IEEE Transactions on Evolutionary Computation. Vol. 1 Nº 1, pp. 53-66. 1997b.

[11] M. Dorigo, V. Maniezzo, A. Colorni. "Ant System: Optimization by a Colony of Cooperative Agents". IEEE Transactions on System, Man and Cybernetics - Part B Vol. 26 Nº 1, pp. 29-41. 1996.

[12] M. Dorigo, V. Maniezzo and A. Colorni. "Possitive feedback as a search strategy". Technical Report Nº 91-016. Dipartimento di Elettronica Politecnico di Milano. Italy. 1991.

[13] D. Eisentein and A. Iyer. "Garbage Collection in Chicago - a Dynamic Scheduling Model". Management Science. Vol. 43 Nº 7, pp. 922-933. 1997.

[14] D. Gaertner and K. Clark. "On Optimal Parameters for Ant Colony Optimization Algorithms". Proc. International Conference on Artificial Intelligence (ICAI 05), pp. 83 - 89, CSReA Press. 2005.

[15] W. Jewells. "Optimal Flows Through Networks with Gains". Operations Research. Vol. 10 Nº 4, pp. 476-499. 1962.

[16] T. Kulkar. "Optimizing Solid Waste Collection in Brussels". European Journal of Operational Research. Vol. 90 Nº 1, pp. 71-77. 1996.

[17] N. Karadimas, G. Kouzas, I. Anagnostopoulos and V. Loumos. "Urban Solid Waste Collection and Routing: The Ant Colony Strategic Approach". International Journal of Simulation. Vol. 6 Nº 12-13, pp. 45-53. 2005.

[18] P. Lazo. "Aplicación de un Procedimiento de Ruteo para la Recolección de Contenedores de Residuos Sólidos Domiciliarios en San Pedro de la Paz". Memoria para optar al Título de Ingeniero Civil Industrial. Universidad de Concepción. Concepción, Chile. 2005.

[19] L. Marcin and T. White. "Using Genetic Algorithms to Optimize ACS-TSP". Proc. of the Third International Workshop on Ant Algorithms, 282-287. In Lecture Notes in Computer Science. Vol. 2463. Springer Verlag. Berlin, Heidelberg. 2002.

[20] R. Mansini and M.G. Speranza. "A Linear Programming Model for the Separate Refuse Collection Service". Computers and Operations Research. Vol. 25 Nº 7-8, pp. 659-673. 1998.

[21] E. Salazar y J. Escalona. "Análisis Paramétrico de Ant Colony System Aplicado al Problema de Secuenciamiento SOP". Revista Ingeniería de Sistemas. Vol. XVIII Nº 1. 2004.

[22] D. Sculli, K.C. Mok, S.H. Cheung. "Scheduling Vehicles for Refuse Collection". Journal of the Operations Research Society. Vol. 38 Nº 3, pp. 233-239. 1987.

[23] T. Stützle, M. Dorigo. "ACO Algorithms for the Traveling Salesman Problem". In: K. Miettinen, P. Neittaanmäki, M. M. Mäkelä and J. Périaux, editors, Evolutionary Algorithms in Engineering and Computer Science, chapter 9, pp. 163-183. John Wiley & Sons. Chichester, United Kingdom. 1999.


Recibido 3 de septiembre de 2007, aceptado 14 de abril de 2009


Artículos Relacionados

# Título Ver
1
Análisis numérico del comportamiento del aire en un sistema de distribución de aire acondicionado empleando los modelos de turbulencia K-?, RNG K-? y el modelo de las tensiones de Reynolds (2008)
Luz Rodríguez Collado, María Collado Contreras, Edgar Rodríguez Malaver, Luis Patiño
HTML | PDF
2
Aplicación de un algoritmo ACO al problema de taller de flujo de permutación con tiempos de preparación dependientes de la secuencia y minimización de makespan (2011)
Eduardo Salazar Hornig, Natalia Pavón Weber
HTML | PDF
3
Control de demanda eléctrica aplicando algoritmos genéticos (2017)
Davel Borges Vasconcellos, Pedro Puch González, Geovanny Frías González
PDF


Otros Artículos

# Título Ver
1
Esquemas de interpolación para la modelación del cierre de la válvula (2018)
John Twyman Q.
PDF
2
Un sistema heterogéneo Multicore/GPU para acelerar la búsqueda por similitud en estructuras métricas (2014)
Roberto Uribe-Paredes, Diego Cazorla, Enrique Arias, José Luis Sánchez
HTML | PDF
3
Efecto de la secuencia anaeróbica-óxica-anóxica (AOA) en la eliminación de materia orgánica, fósforo y nitrógeno en un SBR modificado a escala de laboratorio (2017)
Mauricio Ramos Ramos, Juan F. Muñoz Paredes, Julio C. Saldarriaga Molina
PDF

Desarrollado por: Cristian Díaz Fonseca - cfonseca@matiasluke.cl