Un estudio comparativo de algoritmos metaheurísticos sobre instancias reales de recolección de RSU

Abstract

La gestión de la recolección de Residuos Sólidos Urbanos es una tarea compleja que deben enfrentar los gobiernos locales, consumiendo gran parte de su presupuesto. La utilización de herramientas computacionales que sirvan de apoyo a la toma de decisiones puede contribuir a mejorar la eficiencia del sistema y disminuir los costos asociados. En el presente trabajo se propone la evaluación de distintas herramientas informáticas exactas y metaheurísticas sobre casos reales de la ciudad de Bahía Blanca. Particularmente, se propone la utilización de CPLEX para resolver un problema de programación matemática y su comparación con algortimos metaheurísticos basados en las técnicas de Simulated Annealing y Large Neighborhood Search. Los resultados muestran que CPLEX encuentra limitaciones para resolver los escenarios más grandes. Por otro lado, las herramientas heurísticas propuestas son competitivas, obteniendo valores cercanos a los métodos exactos con tiempos de cómputo mucho menores. Las herramientas heurísticas también son validadas con respecto a conocidos benchmarks de la literatura.

The management of the Municipal Solid Waste collection is a complex task that local governments must face, consuming a large part of their budget. The use of computational tools that support decision-making can contribute to improve the efficiency of the system and reduce the associated costs. This paper proposes the evaluation of different exact and metaheuristic tools on real-world scenarios in the city of Bahía Blanca. In particular, the use of CPLEX is proposed to solve a mathematical programming problem and it is compared with two metaheuristic algorithms based on Simulated Annealing and Large Neighborhood Search techniques. The results show that the exact tool face limitations to solve the larger scenarios. On the other hand, the proposed heuristic tools are competitive, obtaining values that are close to the exact solution in much smaller computing times. The heuristic tools are also validated with respect to well-known benchmarks of the literature.