Investigadores utilizan algoritmos en grafos para mejorar la recolección de residuos urbanos

Mediante un trabajo conjunto de transferencia tecnológica, investigadores del Instituto de Ciencias de la Computación (ICC) y del Instituto de Cálculo (IC) de Exactas, desarrollaron algoritmos en grafos para diseñar mecanismos eficientes en la recolección de residuos urbanos y reciclables en 4 municipios de la Argentina: Bariloche, Concordia, Salta y Tucumán. El proyecto se llevó a cabo  con la Secretaría de Asuntos Municipales del Ministerio del Interior.

¿Qué es un grafo y por qué los grafos están en todas partes? Un grafo es una estructura matemática compuesta de puntos que se conocen como nodos o vértices, los cuales están unidos a través de flechas o enlaces que reciben el nombre de aristas (ver nota anterior del ICC). Los grafos pueden usarse para modelar problemas concretos, y algunos de ellos pueden ser resueltos gracias al desarrollo de algoritmos que utilizan distintas técnicas.

Más allá de ser un tema teórico propio de los fundamentos de las ciencias de la computación, resulta sorprendente la diversidad de aplicaciones donde los grafos están presentes: Redes sociales (las personas de la red son vértices y sus conexiones aristas, puede haber distintos tipos de vínculos que hacen que las conexiones sean bidireccionales o dirigidas), Camino mínimo y aplicaciones de tránsito (dados dos vértices de un grafo, encontrar un camino o secuencia que lleve de un vértice al otro logrando que la suma del peso de las aristas que lo componen sea mínima. Se aplica modelando una red de tránsito como un grafo, y el camino mínimo será el camino sugerido para ir de un lugar a otro, tal como sucede en Google Maps), Redes ferroviarias (un ejemplo interesante es el que describe el esquema de transporte óptimo en la red ferroviaria soviética y la forma óptima de desconectar la misma red)(1), Logística (problema de Pick up & Delivery o cómo hacer para no alterar el orden de las cajas que se acomodan en un camión que hace repartos), Flujo de cañerías de agua (cuál es el máximo de agua que se puede enviar por una cañería y cuáles son los puntos de corte de una red sanitaria), etc.

“Actualmente estamos avanzando en el estudio de algoritmos polinomiales para diversos problemas de optimización en clases particulares de grafos, que nos ayuden a tener más conocimiento sobre dichos problemas y enriquecer el estado del arte”, puntualiza Flavia Bonomo, investigadora y vice-directora del ICC.

En particular, uno de los últimos resultados publicados es sobre coloreo de grafos (ver nota anterior del DC), y otro sobre recubrimiento de vértices por cliques, con o sin peso en los vértices. A fin de encarar estos problemas, la investigadora y doctora en ciencias de la computación, recurre a técnicas tales como Dividir y Conquistar, la cual consiste en dividir el problema en subproblemas más pequeños y definir cómo unir la solución de esos subproblemas para obtener la solución del problema global.

“Esta técnica a veces puede implementarse y otras veces no, ya que depende del problema y la clase de grafos con que trabajemos”, afirma Bonomo. Y complementa: “Por ejemplo, cuando hay grafos que admiten un punto de corte, es decir un vértice que cuando lo extraigo el grafo me queda disconexo, se pueden resolver ciertos problemas en cada una de las componentes conexas que quedan después de eliminar el punto de corte y combinar estas soluciones en una solución de grafo general. Obviamente, no siempre es tan fácil. La descripción técnica de cada uno de los dos algoritmos antes mencionados ocupa unas 20 páginas ”.

Frente a este panorama, la investigadora aclara que uno de sus desafíos es poder encontrar generalidades de los problemas clásicos de optimización combinatoria, que permitan resolverlos en un marco común dentro de alguna clase de grafos. Eso se ha logrado, por ejemplo, para clases de grafos definidas por tener un cierto parámetro de “ancho” acotado.

Grafos que ayudan al recorrido de camiones de basura

A pedido de la Secretaría de Asuntos Municipales del Ministerio del Interior, investigadores del IC e ICC de Exactas-UBA, trabajaron conjuntamente para desarrollar algoritmos eficientes en grafos mediante técnicas de optimización combinatoria, contribuyendo a modelar el problema de recolección de residuos urbanos y reciclables y mejorar el recorrido de los camiones. Los resultados obtenidos fueron transferidos a 4 municipios del país: Bariloche, Concordia, Salta y Tucumán. El trabajo de transferencia tecnológica estuvo coordinado por Guillermo Durán (investigador y director del IC) y participaron los siguientes investigadores formados, del IC y el ICC, coordinando el proyecto de cada una de las respectivas ciudades: Flavia Bonomo (Bariloche), Oscar Lin (Concordia), Diego Delledone (Salta) y Javier Marenco (Tucumán). Cabe recalcar que el grupo de investigadores ya tenía experiencia en trabajos similares desarrollados en el municipio de Morón (provincia de Buenos Aires) y en la zona sur de la Ciudad Autónoma de Buenos Aires.

Bonomo, quien estuvo a cargo de Bariloche, comenta que la metodología utilizada en cada una de las ciudades fue muy similar. Cada investigador formado  -con su grupo de investigadores en formación- viajó a la ciudad beneficiaria del proyecto, se reunió con el organismo encargado de la recolección, entrevistó a los trabajadores del servicio, observó el funcionamiento de los camiones, la capacidad de cada camión, siguió por GPS el recorrido y analizó las características de las zonas de recolección a través de planos de recorridos de los vehículos.

“Aplicamos algoritmos de zonificación en grafos, técnicas de programación lineal entera y mejoramos algunos de los algoritmos de ruteo que ya teníamos desarrollados, permitiendo explorar más posibilidades de recorridos que las que se le suelen ocurrir a un humano, a ojo, para determinar el óptimo.  De este modo, encontramos soluciones más eficientes para disminuir tiempos, costos y mejorar la calidad de trabajo de los recolectores, beneficiando tanto a los organismos de recolección como a los ciudadanos destinatarios del servicio”, describe la investigadora del ICC.

Cada ciudad tuvo problemas muy específicos que fueron trabajados entre investigadores y referentes locales. A su vez, el grupo de investigadores convocó a un estudiante de licenciatura local en cada uno de los municipios, para activar la colaboración con universidades del interior.

En Bariloche, por ejemplo, estuvo presente el factor de que los recolectores hacían grandes recorridos a pie dejando el camión detenido. Esto conllevaba riesgos de accidentes para los trabajadores. Al mismo tiempo, se tuvo en cuenta el factor de desnivel del terreno que influye en la capacidad de carga del camión y en su recorrido.

Mientras que en el caso de Salta, la recolección estaba concesionada y operada por una empresa privada, por lo que se pidió que organicen los recorridos de los “carreros” (que utilizan carros tirados a caballo y cobran a otras personas por retirar basura y escombros de las casas particulares) mediante algoritmos de optimización.

En tanto que en Concordia, los investigadores trabajaron en dos tipos de recorridos: 1) Recolección de residuos en todos los frentes domiciliarios y de los contenedores de la zona centro. 2) Recolección de residuos en contenedores asignados a instituciones. El problema fue muy parecido al del “viajante de comercio”: visitar los distintos containers pero no necesariamente pasar por todas las cuadras.

Por último, para Tucumán se trató de resolver el “problema del cartero chino”, donde el camión debe pasar sí o sí por todas las cuadras pero optimizando su recorrido. Dado que había dos turnos, diurno y nocturno, el proyecto se abocó a reducir la cantidad de zonas nocturnas de manera tal de liberar camiones para dedicar a la zona de las avenidas principales de la ciudad.

(1) El ejemplo es reportado en el artículo de Alexander Schrijver “On the History of the Transportation and Maximum Flow Problems”: Un artículo de A.N. Tolstoi (1930) describe el esquema de transporte óptimo en la red ferroviaria soviética, mientras que un reporte clasificado de T. E. Harris y F. S. Ross (1955) describe la forma óptima de desconectar la misma red.