Algoritmos de Búsqueda Tabú. Aplicación en un problema de rutas.

Naya Forcano, Abel
Calvete Fernández, Herminia Inmaculada (dir.) ; Francés Román, Ángel Ramón (dir.)

Universidad de Zaragoza, CIEN, 2016
Departamento de Métodos Estadísticos, Área de Estadística e Investigación Operativa

Graduado en Matemáticas

Resumen: En su forma genérica, los problemas de rutas de vehículos consisten en hallar una ruta o rutas para una flota de vehículos para dar servicio a un conjunto de clientes minimizando, generalmente, el coste del transporte. Sus principales características son: la red de transporte, los arcos y nodos que los vehículos pueden recorrer, la flota de vehículos, las características de los vehículos utilizados en el proceso, así como las restricciones que puedan imponerse. Estas restricciones pueden afectar a la distancia recorrida o la carga máxima que pueden transportar los vehículos; al lugar en donde entregar la mercancía si cada cliente tiene varios posibles; el origen, o los orígenes si se permite que haya varios; el servicio, si se permite que la carga se pueda dividir o si existen horarios que cumplir; y las rutas solución, por ejemplo si éstas no deben superar una longitud máxima o si se permite que un vehículo realice varias de ellas. Este tipo de problemas de rutas de vehículos tiene multitud de variantes y modificaciones, desde las más sencillas hasta algunas que hoy en día siguen siendo materia de investigación. El coste computacional para resolver este tipo de problemas es elevado y, aunque existen métodos y algoritmos exactos, para problemas con un elevado número de nodos el tiempo de cálculo suele ser excesivo. Es por esto que los algoritmos metaheurísticos, que exploran el espacio de soluciones mediante algún método de búsqueda, se han utilizado para resolver este tipo de problemas, a menudo con resultados altamente satisfactorios. Uno de estos procedimientos metaheurísticos son los llamados algoritmos de búsqueda tabú. Estos algoritmos tratan de guiar un proceso de búsqueda local mediante la utilización de estructuras de memoria, que almacenan determinados acontecimientos ocurridos a lo largo del proceso. La búsqueda local se basa en el concepto de vecinos de una solución, y va recorriendo el espacio de soluciones partiendo de una solución inicial y sustituyéndola por uno de sus vecinos iterativamente. Las estructuras de búsqueda tabú, en su forma mas básica, penalizan determinados vecinos para evitar que el proceso se estanque en un mínimo local. El objetivo de este trabajo es estudiar el problema de rutas de vehículos y los algoritmos de búsqueda tabú, así como implementar un algoritmo de este tipo para resolver un problema clásico de rutas de vehículos. Esta memoria consta de tres capítulos. En el primer capítulo, se formula el problema clásico de rutas de vehículos y se presentan algunas variantes así como distintos tipos de algoritmos que se han propuesto en la literatura para su resolución. En el segundo capítulo, se presentan los conceptos fundamentales de los algoritmos de búsqueda tabú, así como algunas características más avanzadas. Por último, en el tercer capítulo, se detalla la implementación realizada del algoritmo, así como los resultados obtenidos tras ejecutarlo.

Tipo de Trabajo Académico: Trabajo Fin de Grado