Optimización de algoritmos de cálculo de rutas en tiempo real

Abstract

Baolau 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.

Baolau 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.