Comunicación presentada al I Congreso Ciudades Inteligentes:
Autores
- Javier Ferrer, Investigador, Universidad de Málaga
- Enrique Alba, Investigador, Universidad de Málaga
- Francisco Chicano, Investigador, Universidad de Málaga
Resumen
La recogida eficiente de residuos es un aspecto prioritario según el plan de implementación operativa europeo para Smart Cities and Communities. Como participantes en el nodo EIP-6904 proponemos un sistema software inteligente que mejora la eficiencia en la recogida de residuos. Este sistema resuelve los dos grandes problemas para los servicios de recogida: (1) determinar qué contenedores se deben recoger cada día y (2) cuál es la ruta óptima para cada uno de los camiones. Frente al carácter estático de los planes de recogida actuales, nosotros proponemos un sistema dinámico de predicciones de llenado que, gracias a nuevas técnicas de inteligencia artificial, nos permite estimar el momento óptimo de recogida y calcular la mejor ruta para hacerlo. Se esperan una reducción importante del tiempo, el consumo de combustible y ahorro en plantilla, así como una mejora en la calidad de vida de los ciudadanos y la sostenibilidad urbana.
Introducción
El tratamiento de los residuos se ha convertido en una necesidad en un mundo globalizado donde sabemos que nuestros recursos no son inagotables. Además, los residuos ofrecen una oportunidad de negocio, ya que el reciclaje de los productos que contienen cristal, metal, papel, cartón, plástico, etc. nos permite una reutilización posterior de los mismos en la elaboración de nuevos productos. Incluso los residuos antes considerados como desperdicio pueden usarse para conseguir electricidad (bio-masa). La gestión de residuos es un proceso que implica la recolección, trasporte, procesado, reciclaje y monitorización de los nuevos materiales. Principalmente, la recolección es la fase más importante y costosa del ciclo porque la realización de esta labor implica el trabajo de muchas personas y vehículos. Esta importancia de la fase de recolección viene avalada por estudios (Teixeira et al., 2004) que revelan que la recolección significa más del 70% de todos los costes asociados con el tratamiento de los residuos. Por ello, nuestro esfuerzo se centra en la recolección de residuos en un área metropolitana.
La gestión y planificación de la recogida de residuos tiene un amplio margen de mejora, ya que la consideración al mismo tiempo de una gran plantilla, vehículos, calles, situaciones en la ciudad, horarios, capacidades, localización de contenedores, etc., da lugar a problemas que requieren una solución con algoritmos eficientes y si es posible inteligentes. Esto va a suponer una mejora en el servicio al ciudadano, un ahorro en los costes económicos para la administración y una mejora medioambiental global. Algunos sectores de la población discuten la utilidad del sistema actual de recogida, ya que dudan de un sistema que efectúa viajes innecesarios a contenedores casi vacíos. La razón es que las emisiones contaminantes generadas por los viajes extra podrían perjudicar más el medio ambiente que el beneficio de su recolección. Esto es especialmente crítico en el caso de la recogida selectiva, donde el volumen de residuos suele ser menor que en el contenedor de residuos orgánicos. En ese caso una buena planificación de las recogidas es un aspecto aún más fundamental.
Actualmente la recolección de los residuos se realiza sin un análisis de la demanda y además, la construcción de las rutas de recogida se suele dejar en manos de los conductores de los camiones. Esto es muy mejorable, ya que existe información global, experiencias pasadas, consideraciones técnicas y restricciones que así quedan sin considerarse. Con el crecimiento de las ciudades y su área metropolitana, la importancia de un sistema eficiente de recolección es cada vez mayor. Por tanto, nuestra propuesta es un sistema inteligente para la recogida de residuos que está diseñado para resolver los dos grandes problemas a los que se enfrentan los servicios de recogida: 1) determinar qué contenedores se deben recoger cada día y (2) cuál es la ruta óptima para cada uno de los camiones.
El problema de la recogida de residuos municipales (Beliën, et al., 2014), se ha estudiado fundamentalmente desde la perspectiva de las autoridades locales, ya que tienen la necesidad de cuantificar la cantidad de residuos generados por la población en general para poder gestionarlos. Concretamente existen estudios sobre el uso de técnicas de series temporales para predecir las cantidades de residuos generados por una ciudad completa, por ejemplo, Xiamen en China (Xu et al., 2013). En este caso, estos investigadores tratan el problema de la predicción de las cantidades de residuos globalmente (grano grueso), mientras que nosotros nos enfrentamos a la predicción de cada uno de los contenedores por separado (grano fino), lo que supone una dificultad mayor debido a las características propias de la situación de cada contenedor (localización, costumbres ciudadanos, densidad poblacional, etc.). En esta línea, también se ha estudiado el impacto de la intervención de las autoridades locales en la recogida de residuos (Cole et al., 2014), siendo ésta relevante a medio-largo plazo. Con respecto al uso de técnicas de optimización para generar la ruta de los vehículos, todavía hay pocos trabajos relacionados directamente con el problema de la recogida de residuos. Podríamos destacar un estudio realizado en Portugal (Teixeira et al., 2004), pero que tan sólo se centra en las rutas generadas, no en la cantidad de residuos depositados en cada contenedor, ni en cómo se distribuye esa cantidad de residuos en diferentes días, siendo las rutas generadas totalmente estáticas. Las principales contribuciones de este trabajo son pues las siguientes:
- Diseño de un sistema inteligente para mejorar la planificación de la recogida de residuos municipales y su recogida utilizando rutas óptimas.
- Generación inteligente de predicciones de llenado basadas en series temporales a partir de datos históricos.
- Discusión de los resultados obtenidos en una caso de estudio preliminar con 250 contenedores.
En la siguiente sección se trata el problema de la recogida de residuos, desde el punto de vista de la generación de rutas óptimas para los vehículos de recogida, así como el problema de predicción de llenado de los contenedores. A continuación, explicamos brevemente nuestra propuesta de sistema inteligente para la planificación de la recogida de residuos. Después procedemos a la presentación y discusión de los resultados obtenidos en un caso de estudio de recogida selectiva. Para finalizar, destacamos una serie de conclusiones y líneas de trabajo futuras.
El problema de la recogida de residuos
El problema de la recogida de residuos consiste en planificar cómo se va a realizar la recogida de residuos en un área determinada. Básicamente esta tarea consiste en determinar la asignación de los recursos disponibles (vehículos y conductores) a rutas de recogida, es decir, queremos que se visiten los contenedores de residuos que nos convenga recoger en el momento más adecuado (idealmente cuando su porcentaje de llenado esté cercano al 100%). Entre las labores más importantes que hay que realizar podemos destacar la generación de las rutas de recogida por jornada y por tipo de residuo, y sobre todo determinar la frecuencia de visitas que necesita un determinado contenedor. Este problema es realmente complejo, ya que necesitamos modelar el comportamiento de la población que deposita sus residuos en ese determinado contenedor.
Generación de Rutas Óptimas
Esencialmente el objetivo de la generación óptima de rutas es conseguir que nuestros vehículos recorran la menor distancia posible cuando realizan una ruta de recogida de residuos, cumpliendo con las restricciones que se impongan. El problema que subyace es conocido en la literatura como Vehicle Routing Problem (VRP) (Golden et al., 2008). Esto quiere decir que la solución que buscamos implica la visita a un número de clientes (contenedores) con una flota de vehículos (camiones de recogida). Los vehículos comienzan el viaje desde el depósito principal, visitan un número de contenedores para su recolección, y vuelven al depósito de origen. La complejidad de este problema es elevada (NP-duro en terminología científica) pero además se incrementa con las características variables del mismo:
- Tamaño del Vehículo: Restricciones de tamaño para algunos contenedores situados en zonas céntricas; variabilidad de tamaños disponibles para la toma de decisiones.
- Capacidad del Vehículo: La capacidad de cada vehículo debe ser tenida en cuenta por el número máximo de contenedores que puede recoger sin volver al depósito. Variedad de capacidades.
- Residuo que recoge el vehículo: Hay camiones que sólo se pueden encargar de cierto residuo y hay camiones que pueden cargar diferentes residuos, pero no a la vez.
- Número de Depósitos: Podríamos disponer de un depósito o de múltiples.
- Ventanas de Tiempo: Se podrían establecer restricciones de tiempo sobre los contenedores.
- Tipo de residuos: Diferentes residuos no se pueden transportar en el mismo camión. Además, gracias a la recogida selectiva, algunos residuos que no huelen (papel, vidrio, plásticos) tienen frecuencias de recogida menores, siendo el único requisito que no se desborde el contenedor.
El principal objetivo es minimizar el coste global del proceso de recogida. Usando este objetivo podemos expresar otros objetivos en función del coste: la distancia recorrida por los camiones podemos expresarla como gasto en combustible, el número de camiones usados como la amortización del vehículo, el tiempo empleado en la recogida como salario del empleado, la cantidad de residuo recogido como beneficio, etc. Además, debemos cumplir las restricciones impuestas por el modelo, como puede ser que los contenedores recogidos no superen la capacidad total del vehículo. Esta exigencia de la calidad de servicio tan evidente es uno de los grandes problemas del servicio de recogida, puesto que para realizar una recogida eficiente debemos recoger tan sólo los contenedores que estén cercanos al 100% de llenado, pero sin que se sobrepase.
Predicciones de Llenado
Actualmente los planes de recogida suelen ser estáticos, esto quiere decir que las rutas se definen una vez y posteriormente se repiten con la frecuencia que el encargado del servicio haya planificado: típicamente algunas serán diarias, otras en días alternos, etc. Normalmente estas planificaciones no se apoyan en herramientas de decisión inteligentes, sino que se basan en la experiencia y datos difusos aportados por los conductores. En la Figura 1 podemos observar cómo funcionan los planes estáticos de recogida (izquierda) frente a nuestra propuesta con planes dinámicos (derecha).
Un gran inconveniente que afecta a la recogida es que la demanda es desconocida, o lo que es lo mismo, no conocemos a priori la carga o capacidad actual de los contenedores y por lo tanto desconocemos también cuándo vamos a llenar la capacidad de un camión. Esto implica además la posibilidad de que encontremos dos escenarios opuestos: 1) que un contenedor se haya desbordado o 2) que apenas contenga residuos. El primer escenario tiene un impacto directo sobre la calidad de servicio, ya que no podemos olvidar que el servicio de recogida debe mantener altos estándares de satisfacción para los ciudadanos y la sostenibilidad de la ciudad. El segundo escenario redunda en la eficiencia del servicio, puesto que se produce un coste extra al acudir a un contenedor que no necesitaba ser recogido. Este coste es especialmente relevante cuando los contenedores se encuentran en posiciones lejanas al depósito final, o lejanas a otros conjuntos de contenedores. La predicción que proponemos sobre la capacidad de los contenedores nos va a permitir aliviar los problemas descritos anteriormente, ya que vamos a disponer de unas estimaciones de llenado que nos van a dar la posibilidad de planificar rutas dinámicas en función del porcentaje de llenado estimado. El uso de estos porcentajes para cada uno de los contenedores del sistema hace que tengan entidad propia, y las planificaciones se puedan generar atendiendo a las necesidades de cada contenedor y no dependan los unos de los otros, como ocurre cuando la planificación es estática.
Sistema inteligente de recogida de residuos
Nuestra propuesta para mejorar la planificación de la recogida de residuos es un paquete software que se basa principalmente en dos módulos diferentes: el predictor de llenado de los contenedores y el módulo de generación de rutas. A partir de un histórico de datos de recogida por contenedor, o bien utilizando la información de sensores volumétricos para conocer el porcentaje de llenado del contenedor en tiempo real, (1) se realizan predicciones sobre la capacidad actual de un contenedor, (2) se generan las rutas óptimas de recogida, (3) se gestionan eventos en tiempo real, y (4) se monitorizan todos los componentes del sistema (Ver Figura 2).
Nuestro sistema software va a resolver los dos grandes problemas a los que se enfrentan los servicios de recogida: (a) ¿qué contenedores se deben recoger? y (b) ¿en qué orden se visitan para minimizar el coste? Para resolver la primera de estas preguntas necesitamos técnicas avanzadas: vamos a estimar el porcentaje de llenado para saber cuándo debemos ir a recoger un contenedor y así realizar esta labor de la mejor forma posible; vamos a ahorrar combustible y reducir las emisiones de gases contaminantes gracias a que vamos a minimizar el número de visitas innecesarias. Para el desarrollo del módulo pronosticador nos hemos apoyado en el aprendizaje automático computacional para desarrollar un algoritmo capaz de utilizar técnicas de análisis de series temporales para el pronóstico de eventos futuros. Este algoritmo de series temporales está desarrollado en el marco de la plataforma WEKA. (Mark Hall, 2009). Hemos optado por las series temporales como base, ya que se ha probado en la literatura que son eficaces cuando disponemos de suficientes datos históricos. (Jalili & Noori, 2008). Una vez que nuestro sistema obtiene una predicción de llenado diaria para cada uno de los contenedores, podemos calcular después cuando cierto contenedor se encuentra en el rango de recogida definido por el experto, típicamente [80%-100%].
Una vez que hemos definido el subconjunto de contenedores que se encuentra en dicho rango, pasamos la información al módulo generador de rutas que nos devolverá las mejores rutas para esta jornada de recogida. Para el cálculo óptimo de rutas hemos optado por utilizar técnicas inspiradas en la Naturaleza, que han demostrado ser capaces de resolver con éxito variantes de VRP, por ejemplo: Algoritmos de Colonias de Hormigas, Algoritmos Genéticos o Enfriamiento simulado. Somos especialistas en resolver problemas complejos como este, donde además se puede incluir toma de decisiones multi-criterio, cómputo paralelo en la sede de la empresa de recogida e inteligencia computacional. Estas técnicas permiten resolver el problema que considera a toda la ciudad, con datos reales, con preferencias de la empresa de recogidas y con las numerosas restricciones mencionadas para las que la industria actual busca una solución integral.
Caso de estudio: Recogida selectiva
En este trabajo vamos a ilustrar el funcionamiento de parte del sistema que gestiona la planificación de recogidas con una instancia real de una ciudad de tamaño medio costera del sur de España. En este caso vamos a centrarnos en el funcionamiento del módulo de predicciones que es una parte novedosa de nuestro sistema y que nos va a permitir conseguir gran ahorro en el funcionamiento de nuestro servicio de recogida. La instancia que vamos a usar es de recogida selectiva, particularmente nos vamos a centrar en 250 contenedores de papel y cartón del área metropolitana de la ciudad escogida. La elección de una instancia de recogida selectiva es más atractiva para demostrar la potencia de nuestro enfoque, ya que la frecuencia de recogida de estos contenedores es muy variable, y no suele ser diaria como ocurre con la mayoría de contenedores de residuos orgánicos.
En esta instancia partimos de datos históricos del año 2013 de 250 contenedores, estos datos indican para cada día del año el porcentaje estimado de llenado del contenedor, por parte del conductor del vehículo, si se ha pasado por él, y no contiene dato alguno si ese día no se ha realizado su recogida. Por tanto, el sistema debe deducir qué ha ocurrido en los días que no tenemos datos. Este problema lo hemos suavizado con un pre-procesamiento de los datos que nos ha permitido obtener el incremento de carga estimado de cada uno de los contenedores de la instancia para cada día. En los experimentos usando nuestro algoritmo de series temporales hemos realizado la predicción de llenado para el mes de Enero de 2014, y posteriormente lo hemos comparado con los datos reales que se obtuvieron en dicho mes, con el mismo procedimiento que se obtuvieron los datos históricos de los que partimos. Los resultados más relevantes de nuestros experimentos son los siguientes:
- Conseguimos un ahorro del 16,61% en número de visitas a los contenedores, apareciendo un porcentaje de llenado superior al 100% en tan sólo un 5,2% de las ocasiones, lo que supone un escaso número de desbordamientos.
- La mediana del error producido en la estimación del porcentaje de llenado es del 15,13%. Este dato nos indica el margen de error mediano, y gracias a conocer esta información podemos aumentar o disminuir este margen para asegurar la calidad de servicio deseada.
- Con nuestras estimaciones recogemos un 11,01% de media más de residuos en cada visita a un contenedor, lo que redunda en la eficiencia del servicio de recogida.
En la Figura 3 podemos observar el coste mensual del servicio de recogida para este caso de estudio con 250 contenedores frente al coste en que se incurriría utilizando las predicciones de llenado. El ahorro experimentado es de 2118€ mensuales en un servicio que tiene un coste de poco más de 12700€. Este ahorro es significativo, y puede incrementarse si se utiliza este sistema con los demás tipos de residuos.
A la luz de los resultados obtenidos con nuestro algoritmo de predicción de llenado de contenedores, podemos concluir que gracias a las estimaciones proporcionadas se pueden reducir considerablemente las visitas a los contenedores, y consecuentemente los costes asociados al servicio de recogida. Este ahorro en número de visitas se puede desglosar en ahorro de combustible, ahorro en horas de salario de conductores, amortización de vehículos, etc. Además, gracias a la información que nos proporciona nuestro sistema podemos aumentar la calidad de servicio, a la vez que reducimos costes, comportamiento más que deseable ya que estos objetivos deseables suelen estar contrapuestos.
Conclusiones y trabajo futuro
En este trabajo hemos presentado nuestra propuesta de sistema inteligente para la planificación de la recogida de residuos, ilustrando el algoritmo de predicción basado en series temporales. La cada vez más compleja situación medioambiental y el crecimiento de las ciudades hacen que este problema sea hoy por hoy inmanejable. El objetivo principal de nuestro paquete software es reducir los costes de un servicio de recogida de residuos, a la vez que se aumenta la calidad de servicio al ciudadano. En el caso de estudio que hemos analizado en este trabajo, se ponen de manifiesto las mejoras de rendimiento conseguidas gracias al uso de un sistema inteligente de predicción, frente a la planificación estática basada en la experiencia. Un ahorro del 16,61% de las visitas mensuales a contenedores es un ahorro significativo, todo esto sin tener que hacer grandes inversiones de ningún tipo. El trabajo futuro que desarrollamos es la integración del módulo de predicciones con el de generación de rutas. Pensamos que cuando se realice esta integración podremos reducir aún más el número de visitas necesarias y los costes derivados de ellas. Vamos a incluir con cierta flexibilidad en la misma ruta los contenedores cercanos a los que se deben recoger obligatoriamente y así reducir los costes.
Agradecimientos
Queremos agradecer su asesoramiento sobre recogida de residuos al departamento de medioambiente de la empresa Hermanos Padilla, S.L. Además, queremos agradecer la financiación del Ministerio de Economía y Competitividad, y fondos FEDER con la beca BES-2012-055967, a la Universidad Técnica de Ostrava con el contrato OTRI 8.06/5.47.4142, a la Universidad de Málaga y Andalucía Tech.
Referencias
- Beliën, J., De Boeck, L., & Van Ackere, J. (2014). Municipal Solid Waste Collection and Management Problems: A Literature Review. Transportation Science, 48 (1), 78-102.
- Cole, C., Quddus, M., Wheatley, A., Osmani, M., & Kay, K. (2014). The impact of Local Authorities’ interventions on household waste collection: a case study approach using time series modelling. Waste Management, 64, 266-272.
- Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). The Vehicle Routing Problem. (Vol. 43). (E. A, Ed.) Springer.
- Jalili, M., & Noori, R. (2008). Prediction of Municipal Solid Waste Generation by Use of Artificial Neural Network: A Case Study of Mashhad. International Journal of Environmental Research, 2 (1), 13-22.
- Mark Hall, E. F. (2009). The WEKA Data Mining Software: An Update. SIGKDD Explorations, 11 (1).
- Teixeira, J., Pais Antunes, A., & Pinho de Sousa, J. (2004). Recyclable waste collection planning – a case study. European Journal of Operational Research , 543-554.
- Xu, L., Gao, P., Cui, S., & Liu, C. (2013). A hybrid procedure for MSW generation forecasting at multiple time scales in Xiamen City, China. 33 (6), 1324-1331.
Nota: Este artículo fue presentado y publicado en el Libro de Comunicaciones del I Congreso Ciudades Inteligentes.