Camino mínimo.

Básicamente es la funcionalidad incluída en el piloto. Se basa en recorrer el grafo siguiendo un algoritmo de A* (http://es.wikipedia.org/wiki/A%2A). También se ha implementado el mismo problema con Dijkstra (http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra) para comprobar que los dos ofrecen el mismo resultado. Además, Dijkstra había que implementarlo de todas formas para calcular matrices de distancias.

Una vez ejecutado el Solver, obtenemos un objeto Route con los arcos (con sus atributos) por los que pasa ese camino. Para mostrarlo al usuario, se dibuja y además se ha implementado un informe HTML con instrucciones de paso. Mostrar este informe debe ser opcional.

TSP (Travelling Salesman Problem).

Se trata de optimizar el órden de paradas de una ruta.

Sobre los problemas de TSP se ha escrito mucho (http://es.wikipedia.org/wiki/Problema_del_viajante). Es un problema NP-Completo, es decir, que para muchos paradas, no podemos poner a un ordenador a explorar todas las posibilidades porque no acabaría nunca. Para solucionarlo, hay que utilizar algoritmos que te aseguren una buena solución, aunque no se puede asegurar que esa solución sea la óptima (la mejor de todas).

Para abordar el problema, vamos a utilizar algoritmos genéticos, que nos vendrán bien luego para realizar otro tipo de optimizaciones más complejas (definir ventanas de tiempo para cada visita, por ejemplo). El código que podemos usar está en C++, así que hay que portarlo a Java: http://www.codeproject.com/cpp/tspapp.asp

Las entradas son las mismas que para un camino mínimo. Solo hay que incluir un botón más en el Gestor de Paradas para "optimizar el orden de paradas" y 1 check box: "Volver al orígen"

Matriz de Distancias

Llamamos matriz de distancias a una tabla con las distancias y tiempos (costePrincipal, costeSecundario) de unos puntos orígen a unos puntos destino.

Si los orígenes son los mismos que los destinos la matriz es cuadrada, y en la diagonal habrá ceros.

Para hacer el cálculo, implementaremos la función distOneToMany, que calculará las distancias (y tiempos) de un punto al resto. Esta función se llamará para cada punto orígen.

Para que la matriz sea útil, proporcionamos una implementación que la escribe con forma de tabla:

idNodo1 idNodo2 costePrin costeSec

en un fichero plano de texto (el fichero puede ser enorme, cuidado con poner más de 10.000 puntos).

idNodo1 es el índice (basado en cero) de un punto orígen idNodo2 es el índice (basado en cero) de un punto destino

Si no hay conexión entre dos nodos, pondremos un -1. De esta forma, esta opción podrá servir también para aquellos que deseen una matriz de conectividad (solo hay que sustituir los -1 por cero y cualquier otra cosa por un 1.

Para el cálculo, usamos el algoritmo de Dijkstra e internamente se comprueba si se ha llegado a un nodo destino. De esta forma, no hace falta revisar toda la red. Cuando se han encontrado todos los destinos, se puede parar.

En cuanto a interfaz de usuario, el geoproceso necesita como entrada los puntos orígen y destino. En el diálogo se podrán escoger 2 capas de puntos, y habrá 1 checkBox para indicar que los orígenes son los mismos que los destinos, y un checkBox que indique si queremos que se utilicen 2 campos (idArc y pct) de la/s capa/s de entrada. El propósito de esto es no tener que reubicar los puntos sobre la red si realizamos otra matriz, no reubicar los que ya hemos ubicado alguna vez.

Pondremos otra opción de menu que calcule esos campos sobre toda una capa de puntos, o solo sobre los seleccionados. De esta forma, podemos ahorrar tiempo en capas muy grandes.

NOTA: COMENTAR ESTO CON MANUEL POR SI ES LIOSO Y NO MERECE LA PENA.

Localizar Ubicación más cercana

Una vez que tenemos el código para calcular la matriz de distancias, es muy sencillo hacer esta opción.

El usuario ubicará una serie de flags en la red que serán los puntos candidatos, y ubicará un punto que será el orígen desde el que se calcularán las distancias. Se podrá hacer con un click encima de un arco, o por coordenadas.

Una vez hecho esto, se llama a distOneToMany, y se reordenan los puntos destino según la distancia.

Al usuario se le mostrará esa lista ordenada, con información sobre la distancia y tiempo de cada punto. Si sobre ese cuadro de diálogo se selecciona un destino, se habilitarán 2 botones: uno de zoom a ese flag y otro de "Ver ruta" que mostrará el camino a seguir para llegar hasta ese destino.

Para calcular ese camino, no hace falta volver a lanzar el algoritmo de Dijkstra o A*. La red está etiquetada hasta que se haga un nuevo cálculo, así que se puede recorrer de manera inversa para obtener las features por las que se ha pasado. Usaremos la función getRouteFor(Flag destino).

Area de servicio

Son zonas de influencia asociadas a puntos. Se pueden utilizar de varias formas, así que para simplificar el uso creo que lo mejor será hacer un Wizard para guiar al usuario.

En la primera pantalla, el usuario escogerá si quiere partir de una capa de puntos o de los flags ya añadidos al gestor de paradas.

Si se escoge la opción de capa de puntos, se podrá escoger también un campo que defina el coste máximo de cada área. Si ese campo contiene números separados por punto y coma, se crearán tantas áreas como costes se especifiquen.

En la segunda pantalla se podrá editar o añadir los costes de cada área, bien de manera global o individualizada. Habrá un checkbox para "Definir todas iguales" y un textBox para rellenar los costes (separados por ;). Si el check no está marcado, se habilitará una tabla con todos los flags, y un campo de "Areas de Servicio" que será editable. También se podrán habilitar o deshabilitar los flags que no queremos que entren en el cálculo.

Para hacer el cálculo, utilizamos una vez más un algoritmo de Dijkstra. En el evento "edgeVisited" podemos poner el código que cree el área de influencia del coste correspondiente. Se crearán tantas listas de Features como áreas de influencia se definan para cada nodo.

Con esas listas, podemos mostrar las áreas de servicio de varias formas:

• Crear una capa de líneas con 3 campos nuevos: costePrin, costeSec, idFlag asociado. Dentro de los costes, ponemos las distancias y tiempos a los tramos, y en idFlag ponemos el id del Flag más cercano. Con esta capa se pueden conseguir gradaciones de colores que indiquen la proximidad a un determinado flag.
• Crear una capa con esas líneas convertidas en polígonos. La idea es utilizar los límites de costes separados por ; para seleccionar esos intervalos y usar los arcos y nodos para generar los polígonos que van a ser las áreas de influencia. El algoritmo para hacer esos poligonos, si son convexos ya está desarrollado (convex-hull). Si deseamos soportar polígonos cóncavos (zonas más precisas), el algoritmo está por desarrollar. En una primera aproximación lo haremos con convexos.

El usuario podrá escoger si desea los polígonos como anillos o no y si los desea intersectados o no.

También puede ser interesante (sobretodo para presentaciones) etiquetar los nodos con las costes y el flag asociado de manera rápida.

Arbol de recubrimiento de coste mínimo.

Se trata de encontrar un subconjunto de aristas que pasan por todos los nodos con un coste mínimo. (La suma de los costes de las aristas es mínimo). (Minimum Spanning Tree o MST en la literatura anglosajona)

En este enlace se explica el algoritmo de Prim con dibujos y en castellano:

http://es.wikipedia.org/wiki/Algoritmo_de_Prim

y en esta, el algoritmo de Kruskal:

http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal

Siguiendo esos enlaces, encontramos código en java para resolver el problema. Solo hay que adaptarlo a nuestros objetos.

Este problema viene bien para las empresas que abren zanjas. Por ejemplo, una empresa que pone tuberías y tiene que dar servicio a una urbanización. Si cada casa es un nodo, y las calles son los arcos, el problema consiste en hallar un arbos de recubrimiento mínimo (MST) que de servicio a todas las casas, y que nos permita abrir el mínimo número de metros de zanja.

El parámetro de entrada es una capa lineal con una red cargada. El resultado será seleccionar los arcos que forman el MST, es decir, una selección. Luego el usuario, puede exportar esa selección a otra capa si lo desea.

Cálculo de afección de la red.

Este problema se da en redes de agua, por ejemplo. Supongamos que se estropea una cañería. Nos interesa saber qué llave de paso hay que cerrar para evitar que se escape el agua. También nos interesará saber qué parte de la red se va a ver afectada cuando cerremos esa llave. Es decir, qué zona se va a quedar sin agua.

Son dos problemas entonces:

1.- Encontrar un punto "aguas arriba" (es decir, recorriendo la red en sentido inverso) que cumpla una determinada condición. El usuario puede seleccionar los puntos que busca de alguna capa de puntos (seleccionar por atributo los que representen llaves de paso, por ejemplo). Esa selección, la añade a la red como colección de Flags usando el Gestor de Paradas. Después, ejecutará una opción de menú "Encontrar flags más cercanos en sentido inverso" ("Reverse-Find" en inglés). Con eso encontramos las llaves de paso más cercanas que podemos manipular para aislar el tramo defectuoso de la red.

El algoritmo a emplear es parecido al Dijkstra, pero ahora nos interesa recorrerla red en sentido inverso: la exploración se hace desde el nodo destino al nodo orígen de las aristas.

2.- Una vez cerradas esas llaves, nos interesa saber qué parte de nuestra red se queda sin agua (no tiene conexión). Para eso, basta con poner barreras en las llaves de paso y luego utilizar el siguiente nodo a la barrera para obtener su área de influencia. Esa será la zona afectada por el corte de servicio. Es decir, el código para esta opción ya lo tenemos, y el trabajo será guiar al usuario con un wizard del tipo:

1. Haga click en el punto de corte.
2. Seleccione la capa con los puntos a buscar "aguas arriba". Se utilizarán solo los seleccionados si hay selección.
3. Mostrar el punto más cercano (llave de paso), e internamente poner una barrera, seleccionar el siguiente nodo y la red afectada por el corte.