Taller 9: Búsqueda de Direcciones en Bogotá y representaciones en un grafo

Objetivos

  • Analizar y comprender la estructura de un grafo dirigido, con costos asociados a cada uno de los arcos.
  • Entender la importancia, necesidad de uso y aplicación de un grafo en aplicaciones críticas, como la búsqueda geográfica.
  • Modelar y representar un problema a través de la abstracción e implementación del mismo, usando un grafo.

Descripción general

¿Considera que Bogotá es una ciudad óptima y adecuada para conducir? ¿Cree usted, que al conducir, se dirige a través de la ruta más corta entre su punto de origen y su destino? Conforme a la información presentada en el Global Driver Satisfaction Index, publicado por Waze en el mes de Septiembre de 2015, es posible evidenciar que el índice de satisfaction con respecto al tráfico en la ciudad de Bogotá, se encuentra entre los peores en una escala global. Esto implica que toda persona (Temeraria) que desee conducir en esta área metropolitana, debería tener en cuenta ciertos factores importantes y útiles al momento de realizar su desplazamiento a lo largo de las excelentes vías de la capital Colombiana.

De acuerdo a diversas investigaciones, estudios y análisis de movilidad realizados por parte de diversos grupos de investigación, entidades públicas y privadas, se ha afirmado y evidenciado la existencia de una correlación y dependencia directa entre la distancia de un trayecto de viaje y el tiempo que implica tal desplazamiento.[1](#myfootnote1) Es decir, si se reduce la distancia de recorrido entre un punto de origen y un punto de destino, el tiempo de recorrido asociado al mismo, será reducido a su vez. Conforme a esta premisa, es fundamental resaltar la importancia de la búsqueda óptima y pertinente de una ruta de desplazamiento a lo largo de los 136956 segmentos de vía existentes en Bogotá.

Si bien, reducir el tiempo de desplazamiento no solo se encuentra sujeto a la distancia del trayecto planeado (e.g., Estado de las vías, número de vehículos circulando en un día y hora específica, entre otros.), es importante considerar que la distancia es un característica que permanece (En muchos casos) estática e inamovible durante un tiempo considerable (En el orden de años o décadas), mientras que otros factores pueden variar de forma drástica durante un corto tiempo.

1: Rietveld, Piet et al. On the relationship between travel time and travel distance of commuters - The Annals of Regional Science. Vol 33. Issue 3. Disponible en http://dx.doi.org/10.1007/s001680050105

Abstracción del problema

El sistema de nomenclatura y asignación implementado en Bogotá se basa en el uso de una rejilla Cartesiana, en el cual, las calles que se encuentran al sur de la Calle 0, se encuentran denotadas con el sufijo Sur, en lugar del signo negtivo, habitual en la representación cartesiana del espacio \(\mathbb{R}^2\). De igual forma, toda carrera que se encuentre al oriente de la Carrera número 0, se denota a través del sufijo Este. Debido a que cada intersección entre dos vías (e.g., Calles y Carreras), se encuentra descrita a través del uso una coordenada geográfica (i.e., WGS84), es posible representar cada nodo que conforma cada segmento que pertenece a la malla vial de Bogotá como un grafo dirigido, en el cual, cada segmento de vía se encuentra descrito como la unión de dos nodos (Un par de coordenadas geográficas), cuya distancia se encuentra descrita en metros.

Conforme a esta abstracción, se propone la construcción de un sistema de búsqueda y resolución de rutas óptimas entre dos direcciones existentes en la ciudad de Bogotá a partir de la implementación y uso de un grafo dirigido con pesos en cada arco. Si bien, cada nodo del sistema es representado a través de la definición de una coordenada geográfica, es necesario que todo usuario del sistema pueda introducir una dirección sujeta a la nomenclatura estándar definida por la oficina de Catastro. Esto implica que cuando un usuario introduzca una dirección, el sistema debería localizar el identificador del nodo al interior del sistema, así como su información correspondiente (e.g., Vías a las cuales pertenece).

Con el fin de establecer una equivalencia entre una dirección descrita en lenguaje natural y un nodo existente en el grafo, es necesario comprender la naturaleza y la representación del grafo en cuestión. Debido a que una vía (e.g., Calle 167), se encuentra conformada por un conjunto de nodos que comparten el mismo nombre, y considerando que todo nodo que describe una intersección entre dos o más vías pertenece al conjunto de nodos que conforma cada una de las vías a las cuales pertenece, es posible encontrar un nodo que represente una intersección, si este pertenece a la intersección entre los conjuntos de las vías descritas en la dirección. Por ejemplo, si se desea encontrar el nodo que representa la dirección 'CLL 13 # KR 14', es necesario hallar el nodo que pertenece a la intersección entre el conjunto de nodos que conforman la Calle 13 y el conjunto de nodos que pertenecen a la Carrera 14. Cada vía se encontraría dispuesta como un diccionario que establece una equivalencia entre el nombre de una vía, y el conjunto de nodos que pertenecen a esta.

Para este fin, se ha recopilado y procesado un conjunto de datos[1](#myfootnote2) que contiene la ubicación geográfica, así como la información de nombramiento de cada vía en la ciudad. El conjunto de datos se compone de tres archivos de descripción y un archivo de información global de nombramiento y nomenclatura en el sistema. A continuación se procede a presentar el encabezado de cada archivo que conforma el conjunto de datos.

Archivos de descripción del grafo

nodes.csv  - Archivo de descripción de nodos, por cada coordenada geográfica, un número identificador único del nodo en el sistema es asignado.

Encabezado:
num,lat,long  #Número de identificación, latitud y longitud

names.csv  - Archivo de descripción de vías, por cada identificador de un nodo en el grafo, un nombre de vía estandarizado es asignado.

Encabezado:
num,name  #Número de identificación, nombre de vía al cual pertenece el nodo

edges.csv  - Archivo de descripción de segmentos, cada segmento se encuentra compuesto por el número de identificación del nodo de origen,
el número de identificación del nodo final, además de la distancia en metros entre ambos nodos.

Encabezado:
from,to,dist  #Número de identificación del nodo origen, Número de identificación del nodo final, Distancia entre ambos nodos

Archivo de descripción de nomenclatura estandarizada del sistema

Abreviatura Nombre
AC Avenida Calle
CL Calle
TV Transversal
DG Diagonal
AK Avenida Carrera
KR Carrera

2: El conjunto original de datos fue obtenido y recuperado como parte del Proyecto Mapa de Referencia para Bogotá Distrito Capital, desarrollado y publicado en el Dominio Público por parte de la oficina de Infraestructura de Datos Espaciales para el Distrito Capital.

Instrucciones de desarrollo

Nota: Antes de iniciar, lea la sección 0. Envío de talleres: Términos y Condiciones, en esta sección se encuentran enumeradas las reglas y recomendaciones de desarrollo y envío de proyectos establecidas a lo largo del curso.

  1. Por favor, descargue el esqueleto del ejercicio
  2. En primer lugar, al interior del directorio estructuras podrá hallar cada una de las clases que describen un nodo (MapNode.java) y un arco (MapEdge.java) en el grafo. Realice una inspección de su funcionamiento y comprenda los elementos que describe cada uno de los componentes.
  3. En segundo lugar, lea detenidamente las instrucciones dispuestas al interior del archivo de descripción del grafo del mapa vial de Bogotá, MapGraph.java, posteriormente, proceda a implementar las funcionalidades solicitadas.
  4. A continuación, dirigirse a la carpeta mundo y proceder a completar e implementar las funcionalidades restantes al interior de la clase de descripción general del sistema de búsqueda de direcciones en Bogotá, BogotaMap.java. Nota: No olvide omitir el encabezado de cada archivo de descripción de los elementos del grafo, durante el proceso de carga de los mismos.
  5. Finalmente, dirigirse al archivo BogotaRoutingCLI y completar las instrucciones dispuestas. Nota: Recuerde que toda Avenida Calle (Carrera) es una Calle (Carrera) y viceversa. Considere este hecho durante el ingreso de una dirección por parte de un usuario.
  6. Verificar el funcionamiento completo de la aplicación. En caso de que algún inconveniente sea detectado, por favor realizar las correcciones pertintentes y adecuadas.

Reto (Opcional)

  • Consultar, comprender e implementar el uso del sistema de numeración de direcciones en Bogotá, a partir de la aproximación de la misma a la intersección más cercana. e.g., CLL 45 # KR 14 - 96 → CLL 45 # KR 15 ; KR 7 # CLL 72 - 11 → KR 7 # CLL 72 . Nota: El número de las calles incrementa de Sur a Norte, mientras que el número de las carreras incrementa de Oriente a Occidente.

Preguntas

  1. ¿Por qué es fundamental realizar la implementación del grafo de descripción del mapa de Bogotá a través del uso de listas de adyacencia y diccionarios de descripción de información?
  2. A partir del conjunto de nodos que conforma una vía, proponer un procedimiento que permita establecer el inicio y el fin de la vía. Se define como inicio a aquel nodo que no es referenciado como sucesor de otro nodo que pertenece a una vía. Un nodo final, se define como el nodo que pertenece a una vía, pero que no cuenta con nodos sucesores que pertenezcan a la misma vía. Nota: No es necesario realizar una implementación concreta, puede expresarlo a través de pseudocódigo.
  3. Describa y proponga una solución al problema de existencia de un camino entre dos nodos. i.e., Dadas dos direcciones, decidir si existe un camino entre ambos nodos. Nota: No es necesario realizar una implementación concreta, puede expresarlo a través de pseudocódigo o lenguaje natural.

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Verifique que su aplicación cumple con las condiciones descritas en Envío talleres.
  2. Conteste las preguntas en el archivo README.txt.
  3. Realice pruebas unitarias para el funcionamiento de la aplicación. Estas deben encontrarse en el paquete taller.test. Como como mínimo sus pruebas deberían validar los siguientes casos:
    • Dada una dirección, determinar y retornar la información del nodo que describe la intersección más cercana.
  4. Extienda la funcionalidad de la aplicación al añadir una opción adicional que permita conocer el número de intersecciones existentes en la malla vial Bogotana.
  5. Cargue el taller a su repositorio en Bitbucket. No olvide crear el archivo calificacion.txt