Escuela superior politécnica del litoral facultad de Ingeniería en Electricidad y Computación



Descargar 396.87 Kb.
Página9/10
Fecha de conversión24.03.2017
Tamaño396.87 Kb.
1   2   3   4   5   6   7   8   9   10

Generación Automática de Intersecciones


Para implementar el sistema de generación de rutas era imprescindible contar con los datos de latitud y longitud de cada una de las intersecciones de calles del área predefinida como alcance del prototipo. Para generar esta información se recurrió a las funciones del API’s de Google Maps según lo especificado en el capítulo 2.


La tarea de obtener la información de intersecciones de calles se realiza una sola vez y el aplicativo debe contar con esta información antes de su utilización. A continuación se detalla el proceso que se siguió para obtener los datos geocodificados:


    • El usuario accede a una página web la cual mostrará un mapa de Google Maps centrado en el área definida como alcance del prototipo implementado.

    • El usuario debe seleccionar la intersección con la cual desea iniciar la tarea para obtener los datos geocodificados.

    • Se tiene una opción que permite ir avanzando a la siguiente intersección en línea recta. Existe la opción que permite indicar la distancia que se desea avanzar para alcanzar la siguiente intersección.

    • En cualquier momento se puede parar y seleccionar la opción de obtener los datos geocodificados de todos los puntos marcados en el mapa.

    • Existe la opción que permite corregir el punto siguiente que se marca como intersección si este se está marcando de manera desviada de su posición correcta.

    • Existe la opción que permite avanzar en diferentes sentidos, los cuales son: este, oeste, norte y sur.

Los datos geográficos obtenidos para todos los puntos del mapa del área predefinida son almacenados luego en la base de datos.
En la figura 4.1, se muestra la interfaz para la generación automática de intersecciones.
c:\users\elizabeth\pictures\tesis\geocodificacion direcciones.jpg
Figura 4.1: Interfaz gráfica del módulo de generación automática de intersecciones de calles.


    1. Algoritmo para Determinar Orden de Visita de los Nodos


De acuerdo con lo especificado en el capítulo de diseño, TSP será el algoritmo a utilizarse para determinar en qué orden se visitará cada uno de los nodos que conforman las rutas. La técnica que el algoritmo TSP utiliza es la técnica Greedy con la heurística del vecino más próximo.


La implementación del algoritmo utiliza una estructura de datos adecuada para almacenar los enlaces entre los diversos puntos y sus respectivos costos.
El Costo de un punto a otro está dado por la distancia que existe entre ellos en línea recta. Los nodos que son considerados a ordenar son todos los nodos que pertenecen al grupo que se especifica como parámetro del método que implementa el ordenamiento.
El proceso de ordenamiento empieza en el punto de llegada/partida que en nuestro caso sería la dirección geográfica de la institución educativa. A partir de ahí se busca el siguiente punto a visitar seleccionando aquel que represente el de menor costo. Este proceso descrito se continúa hasta que se evalúen todos los nodos del grupo.

El algoritmo de ordenamiento es aplicado dos veces, la primera vez que se aplica es para el ordenamiento general de todos los nodos a ser considerados en la generación de rutas. La segunda vez que se aplica el algoritmo es cuando se tienen los nodos ya agrupados por ruta.


Utilizar el proceso de ordenamiento en dos etapas fue una decisión que se tomó durante la implementación del prototipo al observar que, utilizando el algoritmo de ordenación una sola vez, los nodos eran agrupados correctamente pero luego el orden a seguir dentro de cada grupo no era el óptimo.


Figura 4.2: Ordenamiento de los nodos usando TSP.












    1. Determinar Distancias Mínimas entre Nodos


De acuerdo con lo indicado en el diseño, para el módulo de visualización de rutas generadas se hace uso de la implementación del algoritmo A Star que permite obtener la distancia mínima entre dos nodos. En el diagrama de clases mostrado en el capítulo de diseño se muestra la clase AStarAlgorithm la cual implementa el método de distancias mínimas. Para determinar la distancia mínima entre dos puntos:




  • Se visitan todos los nodos vecinos de un punto y se determina aquel cuyo costo sea menor.

  • Se agrega este punto a la ruta y se verifica si se ha llegado a la meta.

  • Si aún no se llega a la meta se continúa con el nodo siguiente.

  • En el algoritmo se utilizan estructuras de datos adecuadas para el manejo de los nodos y sus respectivos costos. Las siguientes son las estructuras que se crean:



    • PriorityQueue queue – cola de prioridad para los costos.

    • HashMap nodes - estructura de tipo clave, valor para almacenar cada uno de los nodos a evaluar y determinar el de menor costo.

    • HashMap previous – estructura de tipo clave, valor para almacenar el nodo previo de un nodo en el proceso de determinar la distancia mínima de un punto a otro.




  • Para obtener los nodos que conforman la distancia o ruta mínima del punto inicio al punto meta se crea una lista en el que se añadirá como primer elemento el nodo meta y de reverso obtendremos el nodo previo empezando en el nodo meta, estos nodos que se obtiene se almacenan en la lista creada que contendrá la ruta más corta de un punto a otro.

En la figura 4.3, se ilustra cómo se determina la distancia o ruta mínima entre dos puntos.





Figura 4.3: Distancia mínima de un punto a otro.
Lo anteriormente descrito corresponde a determinar la distancia mínima de un punto a otro. Para poder determinar la distancia mínima de una determinada ruta, se procede a aplicar la implementación de distancia mínima de un punto a otro varia veces hasta que se consideren todos los puntos que conforman la ruta, el orden en que van tomando los puntos es de acuerdo con el ordenamiento obtenido a través de la implementación del algoritmo de TSP en sentido descendente.














1   2   3   4   5   6   7   8   9   10


La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal