Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/11531/25764
Registro completo de metadatos
Campo DC Valor Lengua/Idioma
dc.contributor.authorSerrano Marfil, Blancaes-ES
dc.contributor.otherUniversidad Pontificia Comillas,es_ES
dc.date.accessioned2018-02-13T12:00:24Z-
dc.date.availablees_ES
dc.date.issued2018es_ES
dc.identifier.urihttp://hdl.handle.net/11531/25764-
dc.description- Investigación sobre los distintos algoritmos diseñados para resolver el "problema del camino más corto": Dijkstra, Bellman-Ford, Search A *, Floyd-Warshall, Johnson, etc. - Analizar los pros y contras de cada uno de los algoritmos y determinar la mejor solución para calcular rutas de transporte entre las ciudades teniendo en cuenta que los pesos de los enlaces pueden cambiar en tiempo real y también otras restricciones. - Definir la función del algoritmo en pseudocódigo y escribir la fórmula en código PHP. - Implementar un controlador en PHP para alimentar al algoritmo con la base de datos y llevar a cabo test de rendimiento con datos de transporte reales. - Basándose en los datos obtenidos, proponer mejoras en el algoritmo de cálculo de rutas y optimizar la fórmula. - Implementar filtros para reducir el número de resultados generados por el algoritmo de acuerdo a un conjunto especifico de parámetros, tales como medio de transporte, horarios de viaje, numero de pasos, etc. - Representar las rutas calculadas por el algoritmo sobre mapas gráficos e implementar una vista de interfaz con Google Maps.es_ES
dc.description.abstractBaolau es una empresa de multi-transporte que opera en la zona del Mekong. Su misión es tanto proporcionar las rutas que comunican diferentes ciudades y regiones como gestionar la reserva de las mismas. Para aquellas conexiones que requieren más de un medio de transporte, se estaba empleando hasta ahora el algoritmo de Dijkstra. No obstante, debido a la expansión de la empresa a nuevos países, el incremento de nodos y rutas ha supuesto un reto para dicho algoritmo en cuanto al tiempo de ejecución y recursos empleados. Por tanto, el objetivo de este proyecto consiste en determinar cuál es el mejor algoritmo que pueda sustituir a Dijkstra en esta circunstancias. Para ello se ha llevado a cabo una investigación sobre las diferentes posibilidades y se ha acordado que sea el Iterative Enumeration Algorithm (IEA) el sucesor. Este algoritmo no solo es capaz de proporcionar más de un resultado con una sola ejecución, sino que además es más rápido. Por otra parte, se ha modificado la consulta a la base de datos de rutas con el fin de optimizar al máximo el proceso de búsqueda. El algoritmo se ha implementado en el lenguaje de programación PHP e integrado en el sistema de la empresa.es-ES
dc.description.abstractBaolau is a multi-transport company that operates in the Mekong area. Its goal is not only to provide the routes that connect different cities and regions, but also to manage their reservations and payment. Dijkstra was the algorithm in use for connections in need of more than one step. However, due to the company’s expansion to new countries, the increasing number of nodes and routes had become a challenge for the algorithm. The execution time was too long and too many resources were employed. Therefore, the main objective of this project is to determine which is the best algorithm to substitute Dijkstra in these circumstances. A thorough research on the different possibilities has been carried out for this purpose and the Iterative Enumeration Algorithm (IEA) has been the one chosen as successor. This algorithm can obtain more than one solution with just one execution, operating even faster than Dijkstra. On the other hand, the query to the route database has also been modified in order to wholly optimize the route search process. The algorithm has been implemented in PHP and integrated into the company’s system.en-GB
dc.format.mimetypeapplication/pdfes_ES
dc.language.isoen-GBes_ES
dc.subject.otherMIT (H67)es_ES
dc.titleOptimización de algoritmos de cálculo de rutas en tiempo reales_ES
dc.typeinfo:eu-repo/semantics/masterThesises_ES
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses_ES
dc.keywordsIEA, Dijkstra, rutas múltiples, algoritmo.es-ES
dc.keywordsIEA, Dijkstra, multiple-route, algorithm.en-GB
Aparece en las colecciones: H67-Trabajos Fin de Máster
H67-Trabajos Fin de Máster

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
TFM-SerranoMarfilBlanca.pdfTFGM5,32 MBAdobe PDFVista previa
Visualizar/Abrir
BlancaSerrano_AnexoI.pdfANXI103,67 kBAdobe PDFVista previa
Visualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.