Resolución del problema de enrutamiento del autobús escolar

Abstract

[ES] La finalidad de este trabajo es obtener una solución exacta y eficiente del problema de enrutamiento de un autobús escolar. Lo que se pretende es realizar una aplicación con la que poder planificar las rutas óptimas para transportar estudiantes desde el colegio a sus casas y viceversa. Se trata de un problema derivado del problema de enrutamiento de vehículos y se diferencia de estos en añadir variables extra que proporcionan mayor dificultad en la obtención de la solución. Para obtener la solución exacta desarrollaremos un algoritmo de back-tracking que sea capaz de expandir de forma recursiva todos los nodos de las posibles soluciones. Debido a que estamos ante un problema de tipo NP-Completo, obtener una solución exacta tendrá un coste temporal y computacional elevado. Para reducir el tiempo de computo lo máximo posible utilizaremos técnicas de programación paralela mediante OpenMP que nos permitirán aprovechar toda la capacidad de computo de la máquina.

[EN] The purpose of the work is to obtain an exact and efficient solution to the problem of routing a school bus. What is intended is to make an application with the planned power of the optimal routes to transport students from school to their homes and vice versa. This is a problem derived from the problem of routing vehicles and differs from these in adding extra variables that require more difficulty in obtaining the solution. To obtain the exact solution, we will develop a recoil algorithm that is capable of recursively expanding all the nodes of the possible solutions. Because we are facing an NP-Complete problem, obtain an exact solution that will have a high temporal and computational cost. To reduce the computing time as much as possible, we use parallel programming techniques using OpenMP that allows us to reduce the entire computing capacity of the machine.