Nuevas técnicas metaheurísticasaplicación al transporte escolar

Resumen

Este trabajo surge como consecuencia de diversas conversaciones mantenidas con los responsables del transporte escolar en la Provincia de Burgos, La complicada y el elevado grado de dispersión en la población son los dos problemas fundamentales que en la provincia de Burgos, agravan la dificil tarea de la elaboración de rutas. El problema a resolver debe satisfacer un doble objetivo: el economico, que consiste en la minimizacion del coste de transporte y el social, que trata de minimizar la permanencia de los escolares en los autobuses. Se trabaja con métodos aproximados de resolución denominados Metaheuristicos. Los tres grupos de metahuristicos que se estudian son los siguientes:Metaheuristicos basados en Busqueda por Entornos, metaheuristcos Evolutivos o Basados en Población y otros Metaheuristicos, que engloba estrategias como Colonia de Hormigas. Tradicionalmente, antes de la aparición de los metaheuristicos, la busqueda por Entornos abarcaba tan solo la Busqueda Local. Busqueda Local es una estrategia descendente, que escoge sempre una solución mejor que la actual. Dada su importacia en muchos de los metahuristicos utilizados se dedica el capitulo 2 a su estudio y se hacen pruebas con tres tipos diferentes de entornos. Se realizan pruebas con la estrategia de Mayor Descenso y con la de Primer Descenso. Para reducir el tiempo de computación empleado para la busqueda de soluciones en los vecindarios se ha adaptado a problemas de rutas la estrategia denominada Busqueda local Rapida. En el capítulo 3 se diseña un algoritmo para el VRPTW utilizando GRASP y concentracion Heuristica cuyo fin es comprobar la utilidad del uso de la filosofia de concentracion heuristica. Posteriormente se desarrolla un algoritmo de Busqueda Tabu que utiliza vecindarios descritos en el capitulo dos, y un conjunto de concentracion en la fase de intensificacion. En su base básica se implementa la estrategia denominada Oscilacion Estrategica, pa