Algoritmos de bùsqueda de rutas con puntos intermedios y navegación indoor
View/ Open
Date
2023-11-30Author
Ruiz de Alegria Iñiguez de Heredia, Francisco
Metadata
Show full item recordAbstract
En este trabajo se aborda el problema de la búsqueda de rutas entre dos puntos,
con la posibilidad de definir puntos de paso intermedios. El problema de búsqueda
de rutas es uno de los grandes retos informáticos y matemáticos, ya que se trata
de un problema con una complejidad NP-Completo. Los planos sobre los que se
buscarán las rutas se transformarán en grafos, por lo que se ha realizado un estudio
sobre la teoría de grafos y se han identificado los elementos que resultan útiles para
que los algoritmos de búsqueda sean más eficientes. Para la búsqueda de rutas con
puntos intermedios se han estudiado en profundidad tres algoritmos: (1) El algoritmo
de Dijkstra que ofrece una solución óptima a base de examinar todas las posibles
soluciones. (2) El algoritmo Ant Colony Optimization (ACO), que es una solución
totalmente heurística y que permite obtener soluciones adecuadas en un tiempo de
cómputo razonable. (3) En último lugar se implementará el algoritmo de ramificación
y acotamiento, Branch and Bound, el cual a través de una función heurística devuelve
una ruta óptima. La solución propuesta se ha implementado e integrado en dos
aplicaciones reales, por un lado una aplicación web y por otro una aplicación móvil.