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



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

Geocodificación de Direcciones Domiciliarias


La geocodificación de una dirección domiciliaria consiste en tomar la información dada usando zonas y nombres de calles y representarla como un punto geográfico expresado en unidades de latitud y longitud. A continuación se definen dos métodos que existen para geocodificar direcciones domiciliarias.



        1. Dispositivos GPS

Los dispositivos GPS son aparatos parecidos a un reproductor de mp4, pero cargados con cartografía digital que permite descifrar los datos del satélite y dibujar los mapas, marinos o terrestres. De esta manera en la pantalla dibuja un mapa con el sitio exacto del objeto indicando calles, rutas, ríos y accidentes geográficos del terreno a todo color [7]. La figura 5 muestra el modelo de un dispositivo GPS.



que_es_gps_clip_image001

Figura 2.5: Modelo de dispositivo GPS


Estos dispositivos hacen uso del Sistema de Posicionamiento Global, más conocido con las siglas GPS. GPS es un sistema global de navegación por satélite que permite determinar, en cualquier lugar del mundo, la posición de un objeto, persona, vehículo, etc., con una precisión hasta de centímetros, usando GPS diferencial, aunque lo habitual son unos pocos metros.
Para obtener la posición GPS de un punto específico se requiere estar ubicado en el lugar físicamente para de esta manera tener la lectura de los datos geográficos del punto. La lectura de los diferentes puntos de interés, pueden ser guardados en el dispositivo GPS para luego poder ser exportados a una PC y ser utilizados para hacer cálculos mediante un software específico. La figura 2.6 muestra la aplicación que se le puede dar a datos de posicionamiento geográfico obtenidos a través de un dispositivo GPS.
rutas_029b_small
Figura 2.6: Aplicación que muestra puntos geográficos obtenidos por un GPS.

    1. Uso del API de Google Maps


Google Maps provee un API que permite incluir mapas en una página web utilizando el lenguaje de programación JavaScript. Es posible añadir contenido al mapa a través de una variedad de servicios, lo que permite crear aplicaciones robustas de un sitio web.


Google Maps permite usar el API de forma gratuita, siempre y cuando el sitio web que lo utilice ofrezca servicios sin costo para los consumidores. Google Maps ofrece una serie de utilidades para la manipulación de mapas (desplazamiento en el mapa, zoom, etc.), mapas del mundo entero, fotos satelitales, la ruta más corta entre diferentes ubicaciones y muchas características interesantes. Google Maps es fácilmente integrable con cualquier sitio web.
Para hacer uso del API es necesario completar el registro, luego de lo cual se obtiene una clave necesaria para utilizar los scripts que mostrarán los mapas en las páginas web. La guía para desarrolladores y las referencias del API están publicadas en el web y pueden ser obtenidas de forma gratuita1.
En el anexo A se muestran 2 ejemplos del uso del API: cómo incluir un mapa de Google en una página web y cómo insertar marcadores a un mapa.
Para geocodificar una dirección domiciliaria utilizando el API

de Google Maps se procede de la siguiente forma:




  • Se agrega un mapa en una página web, centrado en el área de interés.




  • Se agrega el control que permite desplazarse en el mapa.




  • Se agrega código JavaScript para que el usuario pueda hacer clic en el mapa y el API responda a esta acción devolviendo los datos de latitud y longitud del punto donde se hizo clic.

  • Los datos de latitud y longitud del punto de interés pueden ser mostrados en un área de texto o directamente en pequeñas pantallas emergentes que ofrece el API.

En el anexo B se muestra el código usado para realizar la geocodificación de un punto geográfico de acuerdo con los pasos señalados en la lista anterior.


Para el desarrollo del prototipo propuesto se utilizará el último método expuesto para geocodificación de direcciones domiciliarias, de ese modo no es necesaria la adquisición de un dispositivo con GPS incluido.

Otro problema fundamental en la generación de rutas es el establecimiento de los nodos a visitar: cuáles serán los nodos intermedios y en qué orden serán visitados. En la sección siguiente se exponen conceptos relacionados al Problema del viajante: un modelo analizado ampliamente para la solución de problemas de generación de rutas.



    1. Problema del Viajante (Traveling Salesman Problem)


      1. Introducción


El problema del viajante consiste en encontrar una ruta de un número dado de nodos, visitando cada nodo exactamente una vez y retornando al nodo de partida donde la longitud de esta ruta es minimizada.


La primera instancia del problema del viajante fue propuesto por Euler en 1759 cuyo problema fue mover un caballo a todas las posiciones sobre un tablero de ajedrez exactamente una vez.

El problema del viajante ganó fama en un libro escrito por un vendedor Alemán en 1832 sobre cómo ser un vendedor viajante exitoso. En este libro se menciona el TSP, aunque no por ese nombre, y se sugiere que es posible cubrir muchas localizaciones sin visitar cualquier localización dos veces lo cual es el aspecto más importante de la programación de una ruta.


El problema del vendedor viajante puede ser declarado matemáticamente como sigue:

Dado un grafo de costos G = (V, E) donde el costo Cij sobre el enlace entre los nodos i y j es un valor no negativo, encontrar la ruta de todos los nodos que tenga el mínimo costo total.


El problema puede ser convenientemente modelado por un grafo ponderado, con los nodos del grafo representando las ciudades y los costos de los enlaces especificando las distancias. Entonces el problema puede ser declarado como el problema de encontrar el circuito Hamiltoniano más corto del grafo. La figura 2.7 presenta una pequeña instancia del problema y sus soluciones por este método [5].


Figura 2.7: Una solución a una pequeña instancia del problema del viajante por búsqueda exhaustiva.


Actualmente sólo el método que explora todas las combinaciones es el que permite resolver óptimamente el problema del viajante de cualquier tamaño, para resolverlo enumera cada posible ruta y busca por las rutas con costo mínimo. Cada posible ruta es una permutación de 123 … n, donde n es el número de nodos, así por lo tanto el número de rutas es n!. Cuando n aumenta, se vuelve imposible encontrar el costo de todos los nodos en tiempo polinomial. Muchos diferentes métodos de optimización han sido usados para tratar de resolver el TSP [8]. Para el prototipo propuesto se realizarán pruebas utilizando dos métodos de implementación del TSP.

      1. Aplicaciones


El problema del viajante tiene diferentes aplicaciones en el mundo real, haciendo de ello un problema muy interesante de resolver. Por ejemplo, algunas instancias del problema de ruteo de vehículos puede ser modelado como un problema del viajante (bus escolar, atención de llamadas de emergencia, servicio de correo expreso). Para este ejemplo el problema es encontrar cual cliente debe ser visitado por cual vehículo y el número mínimo de vehículos necesitados para visitar a cada cliente. Hay diferentes variaciones de este problema incluyendo encontrar el tiempo mínimo para visitar a todos los clientes.


El problema de cableado de computadoras puede también ser modelado como un TSP. Para este problema se tiene muchos módulos cada uno con un número de pines. Se necesita conectar un subconjunto de esos pines con cables de tal forma que ningún pin tiene más de dos cables conectados a él y la longitud del cable se reduce al mínimo.
La programación de trabajos sobre una máquina dado el tiempo que se requiere para cada trabajo y el tiempo que toma preparar la máquina para cada trabajo es también TSP. Se trata de minimizar el tiempo total para procesar cada trabajo.
Un robot debe ejecutar muchos diferentes operaciones para completar un proceso. En esta aplicación, opuesto a la programación de trabajos sobre una máquina, se tienen restricciones precedentes. Esto es un ejemplo de un problema que no puede ser modelado por un TSP pero los métodos usados para resolver el TSP podrían ser adaptados para resolver este problema.
Entre otras aplicaciones se tiene por ejemplo: el secuenciamiento de genes, ordenamiento de observaciones en telescopio (NASA), diseño de chips, tour mundial.















      1. Métodos para Resolver el TSP


Homaifar [9] afirma: “un enfoque que encontraría la solución de cualquier TSP es la aplicación de enumeración exhaustiva y evaluación. El procedimiento consiste en generar todas las posibles rutas y evaluar las longitudes correspondientes. La ruta con la longitud más pequeña es seleccionada como la mejor, la cual es garantizada a ser óptima”


El modelo de enumeración exhaustiva es factible para un número pequeño de ciudades, por ejemplo para n=6 existen 720 combinaciones posibles. Sin embargo, dado que el número total de rutas posibles es n!, esta estrategia se vuelve imposible de implementar para un escenario de 25 ciudades, en el cual se requeriría generar 1,55 * 1023combinaciones. Esto podría tomar millones de años de tiempo de procesamiento considerando que se genera y evalúa una ruta por nanosegundo. Por lo tanto, la solución se vuelve impráctica.
Debido al tiempo que se necesita para procesar todas las rutas, se hace necesario encontrar un algoritmo que nos dé una solución en un período de tiempo más corto. Anteriormente se dijo que el problema del viajante es un NP (no polinomial)-duro, lo cual significa que no hay un algoritmo conocido para resolver este problema en tiempo polinomial. De esta manera probablemente se tiene que sacrificar optimización en orden a lograr una buena respuesta en un tiempo más corto. Muchos algoritmos han sido tratados para el problema del viajante. Se explorarán unos pocos de estos en esta sección.

Algoritmos Greedy

El algoritmo Greedy da soluciones factibles, sin embargo no son siempre buenas. El enfoque Greedy sugiere construir una solución a través de una secuencia de pasos, cada expansión una solución parcial construida hasta el momento, hasta que una solución completa del problema es alcanzada. En cada paso, y este es el punto central de esta técnica, la elección hecha debe ser:




  • Factible, por ejemplo, tiene que satisfacer las restricciones del problema.

  • Localmente óptima, por ejemplo, tiene que ser la mejor elección local entre todas las elecciones factibles disponibles sobre ese paso.

  • Irrevocable, por ejemplo, una vez hecho, no puede ser cambiado en pasos subsecuentes del algoritmo.

Estos requerimientos explican el nombre de la técnica: en cada paso, se sugiere una selección “greedy”, escoger la mejor alternativa disponible con la confianza que una secuencia de elecciones óptimas locales producirán una solución óptima a todo el problema. Evitando la discusión filosófica de si la codicia es buena o mala, desde la perspectiva algorítmica, la pregunta es si una estrategia greedy funciona o no. En realidad, existen problemas para los cuales una secuencia de elección óptima local produce una solución óptima para todas las instancias del problema en cuestión. Sin embargo, hay otros para los cuales este no es el caso; para este tipo de problemas, un algoritmo greedy puede ser de valor si se busca una solución aproximada.
Existen varios algoritmos Greedy propuestos para resolver TSP, a continuación se explican dos de ellos: el algoritmo del vecino más próximo y el algoritmo del árbol de expansión mínimo.
El más intuitivo algoritmo greedy para el TSP es basado sobre la heurística del vecino más próximo: iniciando de una ciudad cualquiera, continúa a la más cercana ciudad no visitada y continúa hasta que todas las ciudades hayan sido visitadas, en este punto retorna a la primera ciudad. Hay frecuentemente un alto precio que pagar para realizar selecciones greedy en el inicio del proceso. Un simple ejemplo para ilustrar el caso es dado en la figura 2.8, donde se inicia en la ciudad A, esta heurística greddy construye un tour A – B – C – D – A, con el costo total de 2+3+23+5=33, pero los costos del tour A – C– B – D – A es sólo 4+3+7+5=19.

Figura 2.8: un ejemplo TSP con cuatro ciudades. Note que los costos para cada enlace no corresponden a la distancia entre las ciudades dibujadas.

Un árbol de expansión mínimo ([11] y [12]) es un juego de n – 1 enlaces (donde nuevamente n es el número de ciudades) que conecta todas las ciudades así que la suma de todos los enlaces usados es minimizada. En el grafo se puede crear una ruta por el tratamiento de los enlaces en el árbol de expansión como un enlace bidireccional. Entonces se inicia con una ciudad que está solamente conectada a otra ciudad (esto es conocido como una ciudad hoja) y se continúa al siguiente enlace de ciudades no visitadas. Si hay un enlace no utilizado se retorna al enlace previo. Se continúa haciendo esto hasta que se retorna a la ciudad de inicio. Esto permite tener un límite superior para la ruta del viajante. Se puede notar, sin embargo, que se visitarán algunas ciudades más de una vez. Se puede arreglar esto si cuando se necesita visitar de retorno a una ciudad que ya ha sido visitada, en cambio se va a la próximo ciudad no visitada: cuando todas las ciudades han sido visitadas se va directamente de retorno a la ciudad de inicio.


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