Los principales objetivos entonces son:
Balancear la carga, teniendo en cuenta la dificultad de las calles.
Que los recorridos de un barrendero sean cuadras contiguas.
Que los recorridos sean simples, en el sentido de que no se extiendan por tramos muy alejados del punto de inicio.
Partimos de la base de que la ciudad puede modelarse matematicamente como un grafo, es decir: un cojunto de nodos que representan las intersecciones, y un conjunto de ejes que representan las calles.
Con esta representación de la ciudad, pensamos en la idea de usar un algoritmo bien conocido en el area de grafos, llamado Breadth First Search (ó Busqueda en Anchura). Este es un algoritmo que, partiendo de un nodo inicial, recorre el resto del grafo. Además, lo hace con la propiedad de que siempre recorre primero los nodos vecinos inmediatos a un nodo, luego los vecinos de estos, y así sucesivamente. Modificaremos este algoritmo para lograr una variante que busca cubrir todos los ejes del grafo, en vez de los nodos, también con la propiedad de cubrir primero los ejes vecinos al punto inicial, y luego los ejes vecinos a estos.
Volviendo al mundo real, si pensamos que cada barrendero empieza en una determinada intersección, podemos correr este algoritmo sobre cada barrendero, para que recorra las cuadras más cercanas al punto inicial. Además, haremos que cada barrendero vaya avanzando de manera simultanea, siempre que sea posible sin chocarse con las cuadras de otro barrendero.
De esta manera, cumpliríamos con los objetivos de que los segmentos sean contiguos y simples.
Al no ser un método exacto, lo que hace la heurísitca es buscar muchas de este tipo de soluciones, cambiando distintos parametros, como ser las intersecciones iniciales de donde comienzan los barrenderos y el orden en que el algoritmo irá asignando calles a cada barrendero.
De entre todas las soluciones arrojadas, nos quedaremos con las que logren mejor balance de carga, y mayor simplicidad en sus recorridos.
Datos de Entrada
La ciudad, para el barrido de las calles, está dividida en zonas según la frecuencia con la que se barre cada una. Por un lado, AF brindó un archivo donde se marca cada zona y las calles que le corresponde barrer a la empresa. En otro archivo también se brindó información sobre qué calles son avenidas de la ciudad, para aplicarle esa dificultad. Por otro lado, utilizamos la información abierta de OpenStreetMap (OSM) para parsear la ciudad y generar los grafos de cada área.
Previamente a la generación del grafo, debimos etiquetar en cada calle su dificultad, y los numeros de manzana a los que pertenece una calle. De esta manera luego podemos determinar cuando ciertas cuadras forman una manzana, que usaremos más adelante para determinar si un recorrido es simple, según cuantas manzanas forma.
Además, como gracias al formato OSM contamos con las coordenadas geográficas de cada nodo, podemos determinar la distancia en metros de cada cuadra. Este valor será usado para el balanceo de carga, y será multiplicado por un factor según la dificultad de la misma.
Corrida de la Heurística
Una vez que tenemos el grafo, aplicamos la misma heurística repetidas veces, obteniendo distintas soluciones posibles, es decir, distintas asignaciones válidas de cuadras a barrenderos. Luego nos quedaremos con la mejor.
Cada corrida de la heurística implica varios pasos.
Primero, determinamos aleatóriamente los puntos iniciales de los que partirá cada barrendero. Aquí también debemos determinar con cuantos barrenderos contamos para cubrir todo el área. Como el algoritmo se corre muchas veces, cada configuración inicial nos dará una solución distinta.
Segundo, mientras queden ejes sin asignar, tomaremos a uno de los barrenderos, y ejecutaremos un paso del algoritmo BFS (siempre que sea posible), es decir, asignaremos una cuadra más a ese barrendero, siguiendo el orden que sigue el algoritmo BFS.
La manera en que elejimos al proximo barrendero es uno de los puntos parametrizables del algoritmo. Las distintas formas en las que podemos elegír a quien le asignaremos una cuadra más son:
De manera circular, comenzando por el primer barrendero de la lista hasta llegar al último y empezando de nuevo desde el primero. Se va asignando una cuadra a cada uno de manera cíclica, siempre y cuando el barrendero tenga una cuadra por la que pueda avanzar.
Según la cantidad de cuadras, sería tomar el próximo barrendero como aquél que menos cuadras tiene asignadas, y agregarle una cuadra más a ese.
Según los metros a barrer hasta el momento, es decir, ver que barrendero tiene la menor cantidad de metros asignados a él, considerando que la dificultad de las cuadras impactan sobre la cantidad de métros físicos.
Con estas últimas dos opciones, mejoramos la calidad de las soluciones, ya que de entrada serán soluciones que buscan balancear la carga de los barrenderos.
Para la tercer opción, otro punto imporante a parametrizar aquí es determinar que factor de dificultad es el mejor para cada tipo de cuadra. Es decir, qué tanto más dificil es una cuadra sobre otra influirá sobre el algoritmo y sobre las soluciones.
Por último, una vez que toda cuadra haya sido asignada a un barrendero, se calculan distintas funciones objetivo sobre las soluciones. Estas serán indicadores para decidir qué soluciones son mejores que otras. Entonces, para cada solución, calculamos:
La cantidad de manzanas que son barridas integramente por un barrendero. La idea es que asignar manzanas completas a un barrendero es mejor que asignarle distintas cuadras de distintas manzanas, pues tendrá un recorrido más complicado. Buscamos que este número sea alto.
La diferencia entre la cantidad máxima y mínima de manzanas visitadas por los barrenderos. Es decir, los recorridos serán más simples si los barrenderos se acotan a un área de pocas manzanas cada uno que a un recorrido que pase por muchas manzanas. Buscamos que este número sea bajo.
El balance de carga, es decir, la diferencia en metros entre el que más metros tiene asignados y el que menos. Buscamos que este número sea bajo, para que todos los barrenderos tengan asignados una cantidad similar de metros que barrer.
Imprimimos los resultados de estas funciones para cada solución, y luego las compararemos.
Datos de Salida
Además de los valores de las funciones objetivo, para cada solución generamos un archivo OSM. Esto nos permite inspeccionar una solución de manera visual, viendo en un mapa como quedan las calles asignadas a un barrendero, usando un visualizador de archivos OSM llamado JOSM.
De esta manera, de entre todas las soluciones obtenidas podemos concentrarnos en las que hayan dado mejores resultados numéricos, y luego inspeccionarlas visualmente.