Algoritmos de bùsqueda de rutas con puntos intermedios y navegación indoor

Abstract

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.