Planeación de rutas

Prototipo de Sistema de Administración y Planificación Automática de Rutas
Óptimas para Expresos Escolares de Instituciones Educativas
1

2

Cueva, E. , Vaca C.
1-2

Facultad de Ingeniería en Electricidad y Computación
Escuela Superior Politécnica del Litoral - ESPOL,
Campus Gustavo Galindo, Km. 30.5 Vía Perimetral.
Apartado 09-01-5863. Guayaquil, Ecuador
1ecueva@fiec.espol.edu.ec
2

cvaca@fiec.espol.edu.ec

Resumen
El presente proyectodescribe la implementación de un prototipo de aplicación web para la administración y
planificación de rutas óptimas para expresos escolares de instituciones educativas. Una aplicación de este tipo
permite disminuir sustancialmente el tiempo requerido para la planificación de rutas escolares, a la vez que
permite visualizar lasrutas generadas.
En el prototipo se generan rutas de menor distancia sin considerar el sentido de las calles. Debido a que no se
cuenta con información geocodificada de toda la ciudad de Guayaquil se utiliza para la implementación un área
geográfica determinada, para nuestro caso el centro de la ciudad.
En la generación de rutas de menor distancia se utiliza una implementación del algoritmo deTSP, este
algoritmo utiliza métodos Greedy con la heurística del vecino próximo.
Para dibujar la ruta se utiliza la implementación del algoritmo A-star, la cual permite definir que intersecciones
debe visitar para ir de un punto a otro de acuerdo con el orden de visita dado por el algoritmo TSP.
Palabras Claves: Problema del Viajante, Dijkstra, A-star,API’s de Google Maps.

Abstract
Thisproject describes the implementation of a web application prototype for the management and planning of
optimal routes to express school educational institutions. One application of this type can substantially reduce the
time required for route school planning and at the same time it will allow us to visualize the generated routes.
Using the prototype shorter distance paths are generated withoutconsidering the direction of the streets.
Because there is no geocoded data for the city of Guayaquil, a predefined geographical area was used, this is the
center of the city.
TSP algorithm implementation is used for the generation of shorter distance routes, this algorithm uses greedy
methods applying the heuristic of close neighbor.
To draw the generated routes is used A-Start algorithmimplementation, that allows you to define which
intersections should visit to get from one point to another in accordance with the visitation order given by TSP.
Keywords: Traveling Salesman Problem, Dijkstra, A-star, API’s Google Maps.

1.Introducción
En la actualidad se ha popularizado el uso de
aplicaciones web para la ubicación de direcciones
domiciliarias, gigantes de la computación comoGoogle y Yahoo proveen API’s para manejo de mapas
de forma gratuita. Estas API’s pueden ser utilizadas
para mostrar rutas a seguir para ir de un punto a otro,
una funcionalidad muy útil para cierto tipo de

aplicaciones que requieren dibujar rutas por ejemplo:
rutas escolares, rutas de entrega de comida, rutas
entrega de correo, etc.
Existe, sin embargo, una limitación a los API’smencionados anteriormente: la información de
generación de rutas no está disponible para muchos
sectores geográficos en nuestro país. En este
documento se presenta un prototipo que permite
utilizar los mapas provistos por Google en conjunto
con una base de datos de direcciones geocodificadas

para generar rutas escolares en el sector céntrico de la
ciudad de Guayaquil, ese prototipo puedeconstituir
una base para explotar el gran potencial de estas
aplicaciones.
Para un sistema de generación y manejo de rutas de
expreso escolar, la visualización de las rutas es una
parte importante de este tipo de aplicación, pero
también es fundamental el uso de algoritmos que
permitan obtener rutas optimizadas. En el desarrollo
del prototipo se utiliza una implementación del
algoritmo TSP que...