En este trabajo presentamos el problema de redistribución de barridos en una ciudad y dos técnicas para la resolución del mismo. La primera, es una adaptación del algoritmo propuesto en \cite{Bonomo_2013} para el problema de segmentación de viviendas, la cual, dadas las diferencias entre los problemas, resultó ser inviable en la práctica debido a los elevados tiempos de ejecución. La segunda, es una heurística basada en la utilización del algoritmo de BFS ejecutado en paralelo para un mismo grafo, comenzando desde diferentes puntos del mismo. Esta heurística demostró lograr soluciones satisfactorias en tiempos de ejecución aceptables.
Este trabajo deja pendientes varias alternativas de trabajo futuro, las cuales pretendemos desarrollar en los próximos meses para completar un trabajo de tesis de licenciatura a presentar en la Facultad de Ciencias Exactas y Naturales de la Universidad de Buenos Aires. Los siguientes son algunos de estos aspectos a desarrollar en el futuro:
Con respecto al algoritmo basado en el modelo de PLE, queda por ver si existe alguna manera de reducir los tiempos de ejecución de manera de poder utilizar el mismo para resolver las instancias de este problema utilizadas.
La heurística desarrollada utiliza un técnica similar a la de GRASP \cite{Resende_2001}, aunque no cuenta con la mejora de las soluciones por medio de alguna técnica de búsqueda local. Sería muy interesante desarrollar alguna heurística de búsqueda local para mejorar las soluciones finales obtenidas por el algoritmo.
Otro punto interesante a evaluar para este problema es el desarrollo de un algoritmo genético \cite{1989}. Este tipo de algoritmos ha demostrado ser capaz de obtener resultados muy buenos para problemas de optimización combinatoria similares al problema de los barridos. No queda muy claro a primera vista qué característica de las soluciones podrían explotarse para su combinación en la creación de nuevas soluciones. Sin embargo, un estudio de este estilo podría resultar en una mejora de las soluciones propuestas en este trabajo y por lo tanto representa un potencialmente interesante trabajo futuro, tanto en la teoría como en la práctica.