{"id":1667,"date":"2019-06-21T10:13:15","date_gmt":"2019-06-21T13:13:15","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=1667"},"modified":"2022-03-29T10:38:35","modified_gmt":"2022-03-29T13:38:35","slug":"investigadores-utilizan-algoritmos-en-grafos-para-mejorar-la-recoleccion-de-residuos-urbanos","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/investigadores-utilizan-algoritmos-en-grafos-para-mejorar-la-recoleccion-de-residuos-urbanos\/","title":{"rendered":"Investigadores utilizan algoritmos en grafos para mejorar la recolecci\u00f3n de residuos urbanos"},"content":{"rendered":"

Mediante un trabajo conjunto de transferencia tecnol\u00f3gica, investigadores del Instituto de Ciencias de la Computaci\u00f3n (ICC) y del Instituto de C\u00e1lculo (IC) de Exactas, desarrollaron algoritmos en grafos para dise\u00f1ar mecanismos eficientes en la recolecci\u00f3n de residuos urbanos y reciclables en 4 municipios de la Argentina: Bariloche, Concordia, Salta y Tucum\u00e1n. El proyecto se llev\u00f3 a cabo\u00a0 con la Secretar\u00eda de Asuntos Municipales del Ministerio del Interior.<\/strong><\/em><\/p>\n

\u00bfQu\u00e9 es un grafo y por qu\u00e9 los grafos est\u00e1n en todas partes? Un grafo es una estructura matem\u00e1tica compuesta de puntos que se conocen como nodos o v\u00e9rtices, los cuales est\u00e1n unidos a trav\u00e9s de flechas o enlaces que reciben el nombre de aristas (ver nota anterior del ICC<\/a>). Los grafos pueden usarse para modelar problemas concretos, y algunos de ellos pueden ser resueltos gracias al desarrollo de algoritmos que utilizan distintas t\u00e9cnicas.<\/p>\n

M\u00e1s all\u00e1 de ser un tema te\u00f3rico propio de los fundamentos de las ciencias de la computaci\u00f3n, resulta sorprendente la diversidad de aplicaciones donde los grafos est\u00e1n presentes: Redes sociales<\/strong> (las personas de la red son v\u00e9rtices y sus conexiones aristas, puede haber distintos tipos de v\u00ednculos que hacen que las conexiones sean bidireccionales o dirigidas), Camino m\u00ednimo y aplicaciones de<\/strong> tr\u00e1nsito <\/strong>(dados dos v\u00e9rtices de un grafo, encontrar un camino o secuencia que lleve de un v\u00e9rtice al otro logrando que la suma del peso de las aristas que lo componen sea m\u00ednima. Se aplica modelando una red de tr\u00e1nsito como un grafo, y el camino m\u00ednimo ser\u00e1 el camino sugerido para ir de un lugar a otro, tal como sucede en Google Maps), Redes ferroviarias<\/strong> (un ejemplo interesante es el que describe el esquema de transporte \u00f3ptimo en la red ferroviaria sovi\u00e9tica y la forma \u00f3ptima de desconectar la misma red)(1), Log\u00edstica<\/strong> (problema de Pick up & Delivery o c\u00f3mo hacer para no alterar el orden de las cajas que se acomodan en un cami\u00f3n que hace repartos), Flujo de ca\u00f1er\u00edas de agua<\/strong> (cu\u00e1l es el m\u00e1ximo de agua que se puede enviar por una ca\u00f1er\u00eda y cu\u00e1les son los puntos de corte de una red sanitaria), etc.<\/p>\n

\u201cActualmente estamos avanzando en el estudio de algoritmos polinomiales para diversos problemas de optimizaci\u00f3n en clases particulares de grafos, que nos ayuden a tener m\u00e1s conocimiento sobre dichos problemas y enriquecer el estado del arte<\/em>\u201d, puntualiza Flavia Bonomo<\/strong>, investigadora y vice-directora del ICC.<\/p>\n

En particular, uno de los \u00faltimos resultados publicados es sobre coloreo de grafos (ver nota anterior del DC<\/a>), y otro sobre recubrimiento de v\u00e9rtices por cliques, con o sin peso en los v\u00e9rtices. A fin de encarar estos problemas, la investigadora y doctora en ciencias de la computaci\u00f3n, recurre a t\u00e9cnicas tales como Dividir y Conquistar, la cual consiste en dividir el problema en subproblemas m\u00e1s peque\u00f1os y definir c\u00f3mo unir la soluci\u00f3n de esos subproblemas para obtener la soluci\u00f3n del problema global.<\/p>\n

\u201cEsta t\u00e9cnica a veces puede implementarse y otras veces no, ya que depende del problema y la clase de grafos con que trabajemos<\/em>\u201d, afirma Bonomo. Y complementa: \u201cPor ejemplo<\/em>, cuando hay grafos que admiten un punto de corte, es decir un v\u00e9rtice que cuando lo extraigo el grafo me queda disconexo, se pueden resolver ciertos problemas en cada una de las componentes conexas que quedan despu\u00e9s de eliminar el punto de corte y combinar estas soluciones en una soluci\u00f3n de grafo general. Obviamente, no siempre es tan f\u00e1cil. La descripci\u00f3n t\u00e9cnica de cada uno de los dos algoritmos antes mencionados ocupa unas 20 p\u00e1ginas <\/em>\u201d.<\/p>\n

\n
\"\"<\/figure>\n<\/div>\n

Frente a este panorama, la investigadora aclara que uno de sus desaf\u00edos es poder encontrar generalidades de los problemas cl\u00e1sicos de optimizaci\u00f3n combinatoria, que permitan resolverlos en un marco com\u00fan dentro de alguna clase de grafos. Eso se ha logrado, por ejemplo, para clases de grafos definidas por tener un cierto par\u00e1metro de \u201cancho\u201d acotado.<\/p>\n

Grafos que ayudan al recorrido de camiones de basura<\/strong><\/p>\n

A pedido de la Secretar\u00eda 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\u00e9cnicas de optimizaci\u00f3n combinatoria, contribuyendo a modelar el problema de recolecci\u00f3n de residuos urbanos y reciclables y mejorar el recorrido de los camiones. Los resultados obtenidos fueron transferidos a 4 municipios del pa\u00eds: Bariloche, Concordia, Salta y Tucum\u00e1n. El trabajo de transferencia tecnol\u00f3gica estuvo coordinado por Guillermo Dur\u00e1n<\/strong> (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<\/strong> (Bariloche), Oscar Lin<\/strong> (Concordia), Diego Delledone<\/strong> (Salta) y Javier Marenco<\/strong> (Tucum\u00e1n). Cabe recalcar que el grupo de investigadores ya ten\u00eda experiencia en trabajos similares desarrollados en el municipio de Mor\u00f3n (provincia de Buenos Aires) y en la zona sur de la Ciudad Aut\u00f3noma de Buenos Aires.<\/p>\n

\n
\"\"
Flavia Bonomo<\/figcaption><\/figure>\n<\/div>\n

Bonomo, quien estuvo a cargo de Bariloche, comenta que la metodolog\u00eda utilizada en cada una de las ciudades fue muy similar. Cada investigador formado\u00a0 -con su grupo de investigadores en formaci\u00f3n- viaj\u00f3 a la ciudad beneficiaria del proyecto, se reuni\u00f3 con el organismo encargado de la recolecci\u00f3n, entrevist\u00f3 a los trabajadores del servicio, observ\u00f3 el funcionamiento de los camiones, la capacidad de cada cami\u00f3n, sigui\u00f3 por GPS el recorrido y analiz\u00f3 las caracter\u00edsticas de las zonas de recolecci\u00f3n a trav\u00e9s de planos de recorridos de los veh\u00edculos.<\/p>\n

\u201cAplicamos algoritmos de zonificaci\u00f3n en grafos, t\u00e9cnicas de programaci\u00f3n lineal entera y mejoramos algunos de los algoritmos de ruteo que ya ten\u00edamos desarrollados, permitiendo explorar m\u00e1s posibilidades de recorridos que las que se le suelen ocurrir a un humano, a ojo, para determinar el \u00f3ptimo.\u00a0 De este modo, encontramos soluciones m\u00e1s eficientes para disminuir tiempos, costos y mejorar la calidad de trabajo de los recolectores, beneficiando tanto a los organismos de recolecci\u00f3n como a los ciudadanos destinatarios del servicio<\/em>\u201d, describe la investigadora del ICC.<\/p>\n

Cada ciudad tuvo problemas muy espec\u00edficos que fueron trabajados entre investigadores y referentes locales. A su vez, el grupo de investigadores convoc\u00f3 a un estudiante de licenciatura local en cada uno de los municipios, para activar la colaboraci\u00f3n con universidades del interior.<\/p>\n

En Bariloche, por ejemplo, estuvo presente el factor de que los recolectores hac\u00edan grandes recorridos a pie dejando el cami\u00f3n 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\u00f3n y en su recorrido.<\/p>\n

Mientras que en el caso de Salta, la recolecci\u00f3n estaba concesionada y operada por una empresa privada, por lo que se pidi\u00f3 que organicen los recorridos de los \u201ccarreros\u201d (que utilizan carros tirados a caballo y cobran a otras personas por retirar basura y escombros de las casas particulares) mediante algoritmos de optimizaci\u00f3n.<\/p>\n

En tanto que en Concordia, los investigadores trabajaron en dos tipos de recorridos: 1) Recolecci\u00f3n de residuos en todos los frentes domiciliarios y de los contenedores de la zona centro. 2) Recolecci\u00f3n de residuos en contenedores asignados a instituciones. El problema fue muy parecido al del \u201cviajante de comercio\u201d: visitar los distintos containers<\/em> pero no necesariamente pasar por todas las cuadras.<\/p>\n

Por \u00faltimo, para Tucum\u00e1n se trat\u00f3 de resolver el \u201cproblema del cartero chino\u201d, donde el cami\u00f3n debe pasar s\u00ed o s\u00ed por todas las cuadras pero optimizando su recorrido. Dado que hab\u00eda dos turnos, diurno y nocturno, el proyecto se aboc\u00f3 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.<\/p>\n

(1) El ejemplo es reportado en el art\u00edculo de Alexander Schrijver \u201cOn the History of the Transportation and Maximum Flow Problems\u201d<\/a>: Un art\u00edculo de A.N. Tolstoi (1930) describe el esquema de transporte \u00f3ptimo en la red ferroviaria sovi\u00e9tica, mientras que un reporte clasificado de T. E. Harris y F. S. Ross (1955) describe la forma \u00f3ptima de desconectar la misma red.<\/p>\n<\/div>

<\/div><\/div><\/div><\/div><\/div>","protected":false},"excerpt":{"rendered":"","protected":false},"author":9,"featured_media":1669,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[71,12],"tags":[45,48,43],"class_list":["post-1667","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-actualidad","category-noticias","tag-algoritmos","tag-grafos","tag-optimizacion-combinatoria"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/1667","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=1667"}],"version-history":[{"count":6,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/1667\/revisions"}],"predecessor-version":[{"id":2152,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/1667\/revisions\/2152"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/1669"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=1667"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=1667"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=1667"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}