000059153 001__ 59153
000059153 005__ 20170127103259.0
000059153 037__ $$aTAZ-TFG-2016-2081
000059153 041__ $$aspa
000059153 1001_ $$aNaya Forcano, Abel
000059153 24200 $$aTabu Search Algorithms. An Application to the Vehicle Routing Problem.
000059153 24500 $$aAlgoritmos de Búsqueda Tabú. Aplicación en un problema de rutas.
000059153 260__ $$aZaragoza$$bUniversidad de Zaragoza$$c2016
000059153 506__ $$aby-nc-sa$$bCreative Commons$$c3.0$$uhttp://creativecommons.org/licenses/by-nc-sa/3.0/
000059153 520__ $$aEn 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.
000059153 521__ $$aGraduado en Matemáticas
000059153 540__ $$aDerechos regulados por licencia Creative Commons
000059153 700__ $$aCalvete Fernández, Herminia Inmaculada$$edir.
000059153 700__ $$aFrancés Román, Ángel Ramón$$edir.
000059153 7102_ $$aUniversidad de Zaragoza$$bMétodos Estadísticos$$cEstadística e Investigación Operativa
000059153 8560_ $$f544125@celes.unizar.es
000059153 8564_ $$s331164$$uhttps://zaguan.unizar.es/record/59153/files/TAZ-TFG-2016-2081_ANE.pdf$$yAnexos (spa)
000059153 8564_ $$s434896$$uhttps://zaguan.unizar.es/record/59153/files/TAZ-TFG-2016-2081.pdf$$yMemoria (spa)
000059153 909CO $$ooai:zaguan.unizar.es:59153$$pdriver$$ptrabajos-fin-grado
000059153 950__ $$a
000059153 951__ $$adeposita:2017-01-26
000059153 980__ $$aTAZ$$bTFG$$cCIEN