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



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

Alcance del Proyecto


El desarrollo del prototipo contempla la implementación de una herramienta con acceso vía web que implementa cada una de las características detalladas en la descripción del prototipo.

Debido al costo para obtener la información geocodificada de todas las intersecciones de calles de la ciudad de Guayaquil se determinó que para darle viabilidad al proyecto propuesto se trabajaría con un área que abarque calles céntricas de la ciudad. Se eligió el sector céntrico debido a que es el sector de la ciudad de Guayaquil que tiene datos geográficos bien definidos en Google Maps, los cuales son importantes para la generación y visualización de las rutas generadas.
El prototipo que se diseñará e implementará incluirá:


  • Aplicativo web para la generación automática y óptima de rutas de transporte escolar, que permitirá también la administración y mantenimiento de tareas propias de este tipo de servicio.

  • Un repositorio de intersecciones de calles que cubrirá la siguiente área geográfica, delimitada por las calles: Malecón Simón Bolívar y Colón - Av. Quito y Colón, al sur; Malecón Simón Bolívar y General Vernaza - Julián Coronel y Av. Quito, al norte.

  • La generación de rutas considerará el criterio de menor distancia, sin considerar el sentido de las calles, puesto que estos datos no se tienen disponibles en formato digital.

  • Las rutas generadas serán visualizadas usando funciones del API’s Google Maps.

  • La capacidad de las unidades de transporte serán consideradas como de valor fijo para la generación de las rutas.

Todas las decisiones que se tomaron para definir el alcance fueron necesarias realizarlas, porque sino no hubiera sido factible desarrollar el prototipo.

CAPÍTULO 2


  1. FUNDAMENTOS TEÓRICOS



Introducción

En este capítulo se plantea los fundamentos teóricos en los cuales se basa el diseño e implementación del prototipo de rutas óptimas. Se definen conceptos que son utilizados en el desarrollo de este tipo de aplicativos orientados a generación de rutas y mapas de rutas escolares. Para el caso de geocodificación de direcciones domiciliarias y rutas mínimas se consideran dos alternativas, de las cuales se ha escogido la más óptima en costo, tiempo de implementación y tiempo de respuesta del aplicativo.








    1. Sistemas de Planeación de Rutas


En toda institución cuya ubicación geográfica es relativamente apartada de los lugares donde se concentra la mayor cantidad de población, se vuelve imprescindible en un momento dado contar con unidades de transporte para dar servicio a empleados o a clientes.


Una institución educativa de secundaria es un claro ejemplo en el cual, se vuelve imprescindible manejar información geográfica de los estudiantes y profesores para distribuir a los mismos en las diferentes rutas de transporte escolar planeadas.
El trabajo de distribuir a personal, clientes, estudiantes en una serie de rutas se vuelve complicado cuando el número de los mismos aumenta y no se tiene un sistema que automatice el proceso de diseño de rutas. Así pues una distribución manual puede llevar a resultados poco eficientes con rutas extremadamente largas y poco equilibradas.
Existen múltiples implementaciones de sistemas de planeación de rutas construidos alrededor del mundo, a continuación detallamos algunos sistemas que han sido desarrollados:


  • Software de planificación de ruteo de buses escolares, desarrollado por la compañía Versa Trans [1]. Este software provee los siguientes servicios: generación de mapas, mantenimiento de datos del estudiante, ruteo y planificación; y manejo de herramientas de reportes.



  • Prototipo de Ruteo y planificación de bus escolar usando GIS (Sistema de Información geográfica), desarrollado como parte de una tesis de maestría para el colegio Sujatha de la ciudad de Hyderabad, India.

Este prototipo permite la administración de transportación escolar a través del diseño de rutas escolares cortas y rápidas y también permite ubicar paradas de bus, lo cual ayuda a seleccionar las paradas para recoger a los estudiantes y personal de acuerdo a su concentración en las diferentes áreas [2].


  • Manejador de operaciones de transportación (TOM), desarrollado por Gecko Microsolutions, Inc. Este sistema presta los siguientes servicios: ruteo usando GIS (Sistema de Información geográfica), visualización de mapas, manejo de conductas de estudiantes en el bus, manejo de otras actividades de transportación de los alumnos [3].

En la mayoría de los paquetes de software para planificación de rutas escolares se puede encontrar la implementación de algoritmos relacionados a la generación de rutas, por ejemplo, encontrar el camino más corto entre dos puntos, generar una ruta para recorrer varios puntos de forma eficiente, etc. En las siguientes secciones se analizarán algunos de estos conceptos.

      1. Problema del Camino más Corto


Los seres humanos por naturaleza minimizan esfuerzo, sobre todo cuando se trata de moverse. Cuando tienen la oportunidad, siempre tratarán de elegir el camino más corto para ir de un lugar a otro. Este comportamiento puede ser fácilmente observado en los peatones. Cuando sea posible, un peatón camina atravesando un césped, en zigzag por los coches en un estacionamiento, o cruza una calle lateral entre las intersecciones si la ruta seleccionada permite llegar más rápido a un destino.

El transporte, como una actividad económica, reproduce este proceso de minimización, en particular tratando de reducir al mínimo la distancia entre localidades. Estrategias para obtener rutas con tiempos más cortos y costos más bajos son constantemente analizadas por individuos y empresas. Para un individuo, a menudo es sólo una cuestión de conveniencia, pero para una sociedad es de importancia estratégica como un costo monetario directo. En tales circunstancias, no es sorprendente que numerosos métodos hayan sido desarrollados para hacer frente a la compleja cuestión de selección de rutas. Uno de esos clásicos es el problema del vendedor viajero, cuando el camino más corto tiene que ser seleccionado de un conjunto de numerosas combinaciones de posibles trayectorias.
El problema del camino más corto se lo puede clasificar en: el camino más corto desde un origen a un destino y el camino más corto desde un origen a muchos destinos. Para el prototipo propuesto en este documento se analizará e implementará una solución que use el camino más corto desde un origen a muchos destinos.
Los sistemas que implementan soluciones para encontrar el camino más corto entre un origen y varios destinos requieren la aplicación de conceptos que se definen en la siguiente lista de términos:


    • Grafo: es un conjunto, no vacío, de objetos llamados nodos (vértices) y una selección de pares de nodos, llamados enlaces (aristas) que pueden ser direccionados o no, los grafos direccionados son llamados dígrafos. Típicamente, un grafo se representa mediante una serie de nodos conectados por enlaces [4].




    • Vértices o nodos: En teoría de grafos, un nodo es la unidad fundamental de la que están formados los grafos [4]. Como ejemplos de nodos se nombran los siguientes: intersecciones de calles, poblaciones, ciudades, empalmes eléctricos, fases principales de un proyecto [5].




    • Enlaces o aristas: son las uniones entre los nodos. Los enlaces denotan relaciones entre los nodos (vecindad, herencia, orden, etc.) [4]. Como ejemplos de enlaces se nombran los siguientes: segmentos de calles, carreteras secundarias, tiempo de desplazamiento en aviones, componentes de circuito, tareas de un proyecto.




    • Costos: número específico atribuido a cada enlace de un grafo, también llamado valuación o ponderación. Como ejemplos de costos se nombran los siguientes: número de habitantes, % de cierta población por zona, % de uso de electricidad por zona, longitud de una carretera. En la figura 2.1 se muestra un grafo con costos asignados a sus enlaces [5].

Figura 2.1: Grafo con costos



  • Grafos ponderados: un grafo o dígrafo ponderado es un grafo o dígrafo con costos asignados a sus enlaces. Un interés en los grafos es motivado por numerosas aplicaciones de la vida real, como por ejemplo, encontrar la ruta más corta entre dos puntos en una red de transporte o comunicación o el problema del vendedor viajante [5].




  • Ruta: una ruta del nodo A al nodo B del grafo G puede ser definida como una secuencia de nodos adyacentes (conectados por enlaces) que empieza con A y termina con B. Si todos los enlaces de una ruta son distintos, se dice que la ruta es simple [5].




  • Longitud de una ruta: es el número total de nodos en una secuencia de nodos que definen la ruta -1, el cual es el número de enlaces en la ruta. Por ejemplo, a, c, b, f es una ruta simple de longitud 3 de a a f como se muestra en el grafo de la figura 2.2, mientras a, c, e, c, b, f es una ruta (no simple) de longitud 5 de a a f [5].


Figura 2.2: Grafo no direccionado




  • Ruta dirigida: es una secuencia de nodos en el cual todos los pares de nodos consecutivos están conectados por enlaces dirigidos del nodo origen al nodo destino. Por ejemplo, a, c, e, f es un ruta dirigida de a a f en el grafo de la figura 2.3 [5].


Figura 2.3: Grafo dirigido




  • Grafo conectado: si para todos los pares de nodos u,v hay una ruta de u a v. Por ejemplo el grafo de la figura 2.2 es conectado, mientras el grafo de la figura 2.4 no es conectado porque no hay ruta, por ejemplo, de a a f.




Figura 2.4: Grafo no conectado

  • Ciclos: es una simple ruta de longitud positiva que inicia y termina en el mismo nodo. Po ejemplo, f, h, i, g, f es un ciclo en el grafo de la figura 2.4. Un grafo que no tiene ciclos se dice ser a cíclico [5].




  • Búsqueda exhaustiva: Muchos problemas importantes requieren encontrar un elemento con una propiedad especial en un dominio que crece exponencialmente. Típicamente, tales problemas surgen en situaciones que implican explícitamente o implícitamente modelos combinatoriales que usan permutaciones o combinaciones de elementos de un conjunto dado. Muchos de tales problemas son problemas de optimización que requieren encontrar un elemento que maximice o minimice alguna deseada característica tales como una longitud de ruta o costo asignado.

La búsqueda exhaustiva es simplemente un enfoque de fuerza-bruta de los problemas combinatoriales. Lo cual sugiere generar todos los elementos del dominio del problema, seleccionando aquellos que satisfacen las restricciones del problema, y entonces encontrando un elemento deseado (por ejemplo, el que optimice algunas funciones objetivo). Note que aunque la idea de búsqueda exhaustiva es bastante sencilla, su implementación típicamente requiere mucho tiempo para ser ejecutada.




  • Circuito Hamiltoniano: es un ciclo que pasa a través de todos los nodos del grafo exactamente una vez.

En teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos nodos, de tal manera que la suma de los costos de sus enlaces sea mínima; siendo los enlaces el segmento que une los nodos y el costo de cada enlace es el número que representa tal enlace. Un ejemplo podría ser encontrar la forma más rápida de llegar de un lugar a otro, en este caso, los nodos representan los lugares y los enlaces representan los segmentos de la carretera y se ponderan por el tiempo necesario para realizar el viaje de un punto a otro [6].


En un sistema de transporte de rutas, las direcciones domiciliarias constituyen los nodos del grafo y las calles ubicadas entre una dirección y la siguiente más cercana constituyen los enlaces. Para generar información geográfica que pueda ser representada en un mapa es necesario como primer paso traducir las direcciones domiciliarias a un par latitud, longitud. Este proceso se conoce como Geocodificación de direcciones y se explica en la siguiente sección.







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