El reto de la planificación de rutas en el sector de la recogida de residuos urbanos

Uno de los principales desafíos a los que se enfrentan las empresas de servicios urbanos en sus ofertas técnicas para la recogida y limpieza de residuos es minimizar los costos de transporte asociados a los itinerarios de recogida. Por lo general el problema en el diseño de rutas se solventa con una mezcla de herramientas básicas, instinto y años de experiencia. Pero, ¿podemos resolverlo de una manera más lógica, optimizada y sistemática posible?

Este tipo de problemas es posiblemente uno de los más complejos de resolver en el ámbito GIS. Frente a la teoría, nos encontramos con una realidad en la que los gestores de los servicios buscan calcular las mejores rutas para sus camiones en sistemas complejos, con múltiples restricciones y requiriendo diseños de itinerarios en tiempos reducidos.

Mapa con una ruta de recogida de residuos urbanos.
Mapa con una ruta de recogida de residuos urbanos. Este tipos de análisis GIS son muy complejos debido a que implican factores como el amplio número de paradas, la consideración de costes asimétricos o las restricciones de capacidad y descarga.

En muchos casos una simple inspección visual del tramero de calles puede revelar rápidamente la mejor ruta a tomar, pero por lo general estas aproximaciones no siempre devuelven el resultado correcto. Existen factores como las restricciones de tráfico o las prohibiciones de giros que a simple vista no son fáciles de incluir en la definición del problema y que se materializan en rutas más laberínticas de lo inicialmente estimado. Esto a la postre puede invalidar soluciones que a priori se veían acertadas.

NP-hard: cuando resolver un problema te puede llevar toda una vida

En el cálculo de rutas de recogidas estamos hablando de un problema de los denominados NP-hard, los cuales son problemas computacionalmente complejos entre los que se incluyen el conocido como problema del vendedor viajante o TSP (Travelling Sales Problem).

En este famoso problema se espera que un viajante, que vive en una de las ciudades, haga un viaje de ida y vuelta visitando todas las demás ciudades y regresando a casa. En realidad, no importa qué ciudad sea el punto de partida, el requisito es que el coste total recorrido sea lo más pequeño posible.

Resulta que la cuestión, a priori sencilla, es realmente muy difícil de resolver, particularmente si uno insiste en encontrar la respuesta perfecta.

Los problemas HP-hard son difíciles no solo porque son muy complicados de responder, sino porque las soluciones son muy difíciles de comprobar.

Simplificándolo y para no perdernos en los fundamentos matemáticos que subyacen debajo, NP se refiere a “polinomio no determinista”, y de manera simple NP-hard viene a significar que para un problema de este tipo encontrar una solución requiere en esencia probar muchas combinatorias diferentes. Pero incluso si alguien te da la respuesta, es a su vez difícil verificar si esta es la correcta.

Cuando un neofito se enfrenta por primera vez al reto de calcular las rutas óptimas de recogida de residuos, un rápido vistazo suele llevar a la falsa suposición de que dar con la solución no puede llevar mucho tiempo. Pero en el problema del vendedor viajante la complejidad aumenta exponencialmente a medida que se incrementa los puntos por los que debe pasar la ruta, por lo que si estos son excesivamente grandes no se puede garantizar que el algoritmo encontrará el camino más corto dentro de un límite de tiempo razonable.

Debido a lo complicado de este tipo de problemas normalmente se utilizan algoritmos heurísticos que lo que obtienen como “soluciones” son aproximaciones. Algunas de estas soluciones pueden ser muy cercanas a la realidad, en cambio otras pueden alejarse de ella.

Para simplificarlo veamos gráficamente las siguientes ilustraciones que sintetiza las diferentes maneras de resolver el camino mínimo mediante un algoritmo voraz y uno heurístico:

Búsqueda de la ruta de coste mínimo mediante el algoritmo de Dijkstra
Algoritmo de Dijkstra
(imagen: Subh83)

  • Visita todos los nodos, avanzando nodo a nodo siempre por el camino que lleve menos coste.
  • Está demostrado matemáticamente que siempre encuentra la ruta óptima (la de menor coste).
  • Consume mucho tiempo.
Búsqueda de la ruta de coste mínimo mediante el algoritmo A*
Algoritmo A*
(imagen: Subh83)

  • Hace uso de funciones heurísticas: se sacrifica la exactitud de la solución en favor de un tiempo de respuesta corto o aceptable.
  • Avanza nodo a nodo siempre por el camino que lleve menos coste y por el cuál cree que se acerca más al destino.
  • Devuelve una solución óptima que quizá no sea la mejor.
  • Es mucho más rápido que Dijkstra pero consume más recursos.

Podemos ver como el conocido algoritmo de Dijkstra analiza todo el grafo para calcular la ruta más corta entre el nodo de inicio y todos los demás. Mientras A*, uno de los algoritmos más utilizados para resolver el TSP, utiliza una regla de “sentido común”, avanzando inicialmente en línea recta hacia el punto de destino (la solución teórica perfecta) y explorando rutas alternativas una vez choca contra un obstáculo.

Llegados a este punto podemos pensar que ya solo necesitamos una herramienta en nuestro Sistema de Información Geográfica (GIS) que de solución al problema del viajante y obtendremos nuestro mejor itinerario de recogida.
Los principales Sistemas de Información Geográfica disponen de herramientas para resolver el problema del vendedor viajero (QGIS/GRASS, ArcGIS, pgRouting, etc.) pero existe un importante matiz: la solución que devuelve TSP por definición es una única ruta, mientras que en la recogida de residuos es necesario un conjunto óptimo de rutas para una flota de vehículos: el problema se complica de nuevo.

El problema de generación de rutas para vehículos

Hay que cambiar de enfoque ya que nos enfrentamos por lo tanto a un problema de enrutamiento de vehículos o VRP (Vehicle Routing Problem), una variante más compleja y menos conocida del problema del viajante (TSP).

VRP surgió como una generalización del TSP para los casos en los que la capacidad de los vehículos que realizan la ruta sea limitada, siendo necesario realizar varios viajes. En el caso de la recogida de basuras el problema se enmaraña más si cabe convirtiéndose en un VRP especializado, al tener que incluir variantes inherentes a los servicios de recogida de Residuos Sólidos Urbanos (RSU) que afectan a la solución. Y es que existen condicionantes que van más allá de los de la propia topología de la red de calles:

  • La recogida puede ser selectiva o no.
  • La capacidad de transporte de los camiones es limitada: las rutas se deben calcular en función del límite teórico de contenedores que cada tipo de camión puede recoger.
  • Los camiones tienen una autonomía que condicionará la distancia recorrida: existe un número máximo de viajes al vertedero que pueden realizar antes de regresar a la base a repostar.
  • Los camiones pueden ser de carga trasera o lateral (y estos a su vez de derecha o izquierda). En función de la disposición de los contenedores en la vía se debe utilizar un camión de un tipo u otro, lo que afectará al recorrido.
  • Las recogidas pueden tener una ventana de tiempo: se realizan en horarios específicos que hay que considerar.
  • Los tiempos de recorrido no deben exceder los turnos de recogida.
  • Los límites de velocidad, el tráfico relacionado, la prohibición de giros en U, las limitaciones de tonelaje o gálibo o la imposibilidad del camión de dar marcha atrás para descargar contenedores son algunos otros de los factores que dificultan el diseño de los itinerarios.

Como ya se puede intuir, qué tan complejo es resolver un VRP dependerá de las diferentes características o restricciones que deben ser consideradas.

Descarga de un contenedor de fracción resto en un camión de carga lateral.
La carga lateral de los contenedores es uno más de los condicionantes en el diseño de rutas para la recogida de residuos urbanos (imagen: Diario de Madrid).

Todo ello hace que, de un “sencillo” problema TSP de costes que a priori se puede considerar suficiente para resolver el rompecabezas, se pase a necesitar un algoritmo mucho más especializado.

VPR desde una perspectiva de modelado GIS

Existen dos enfoques principales para resolver el problema de cálculo de rutas para la recogida de basuras: uno sustentado en programación matemática y otro a nivel GIS, ambos con sus ventajas e inconvenientes:

  • El acercamiento al problema mediante un enfoque teórico de programación matemática puede manejar grandes redes, pero devuelve una solución parcial cuando es aplicada en la vida real, a lo que hay que añadir que no pueden gestionar completamente las restricciones de la red que involucra al problema de ruteo.
  • Abordar este problema desde una perspectiva GIS permite la incorporación de impedancias, características del relieve y restricciones en el modelado de la red desde un óptica de optimización espacial. Por contra su mayor problema radica en que los GIS no suelen ser la mejor herramienta para calcular la optimización de rutas cuando el número de puntos por los que tienen que pasar las rutas es muy alto.

En el ámbito GIS el uso de algoritmos para conseguir una zonificación espacial y clusterización de contenedores atendiendo a sus características de recogida y fracción, junto con la utilización de funciones de ruteo de vehículos que incorpora pgRouting (las cuáles precisamente se desarrollaron originalmente para la recogida de basura), son una buena aproximación para abordar el problema. Estas últimas permiten manejar restricciones de capacidad (CVRP), ventanas de tiempo (VRPTW) o múltiples lugares de descarga (VRPPD), cuestiones fundamentales en la planificación de este tipo de itinerarios de limpieza urbana.

En definitiva y para finalizar, debemos quedarnos con la idea de que aún con todos los avances tecnológicos y teóricos logrados hoy en día, la alta complejidad que supone definir itinerarios de recogida de contenedores de residuos en ciudades sigue siendo un problema de difícil resolución. Actualmente solo se puede resolver mediante algoritmos que buscan encontrar la mejor solución posible en un tiempo razonable, por lo tanto no vale la pena buscar soluciones exactas.
Aun así, y a pesar de las limitaciones mencionadas, la obtención de resultados para la planificación de rutas en la recogida de residuos urbanos mediante GIS suponen una buena aproximación con una sistematización del proceso y un ahorro en tiempo y personal nada despreciables. Y todo debido a que en el proceso se consideran una cantidad de variables y condicionantes que obtener los mejores itinerarios difícilmente podría abarcarse manualmente.

Esta web usa cookies para mejorar su experiencia en la navegación. Si continua utilizando este sitio acepta su uso. Más información

Las opciones de cookie en este sitio web están configuradas para "permitir cookies" para ofrecerte una mejor experiéncia de navegación. Si sigues utilizando este sitio web sin cambiar tus opciones o haces clic en "Aceptar" estarás consintiendo las cookies de este sitio.

Cerrar