Introducción de dependencia horaria en los costes y generalización de los tiempos de espera en el problema del agente viajero con ventanas de tiempo

Abstract

El principal objetivo de esta tesis es introducir la dependencia horaria de los costes y restricciones temporales (ventanas de tiempo) en el conocido Problema del Agente Viajero asimétrico (PAV asimétrico) obtenido el Problema del Agente Viajero con Dependencia Horaria de los Costes (PAVDHC). Este problema básicamente consiste en: "Sea G un grafo dirigido completo donde cada vértice tiene asociada una ventana de tiempo y tanto el coste como el tiempo de recorrer cada arco dependen del momento en que empieza a ser recorrido. El problema consiste en encontrar una ruta óptima para un vehículo que abandone un vértice determinado, llamado depósito dentro de su ventana temporal, visite todos los vértices exactamente una vez dentro de su ventana de tiempo y regrese al vértice depósito antes de que se agote su ventana temporal. De tal forma que teniendo en cuenta la dependencia horaria de los costes, la ruta obtenida sea aquella cuyo coste sea el menor de todas las rutas posibles. Y en vistas a minimizar el coste total de la ruta el problema permite esperar, con coste cero, hasta el mismo momento en que un vértice activa su ventana temporal. En cuyo caso el vehículo deberá abandonar el vértice en el primer instante de tiempo". Seguidamente, se muestran los resultados teóricos que nos permitirán transformar el PAVDHC en un PAV asimétrico en un tiempo pseudo-plinomial y con ello, la posibilidad de resolver el problema de una forma óptima. Prueba de esto, es la experiencia computacional llevada a cabo con un algoritmo de resolución exacta para el PAV asimétrico transforamdo de PAVDHC. También se propondrá una generalización del PAVDHC en la que se permite esperar hasta cualquier instante de la ventana de tiempo de cualquier vértice. A este problema le llamaremos el Problema del Agente Viajero con Dependencia Horaria de los Costes y Tiempos de Espera (PAVDHCTE). Por otra parte, se ofrece un estudio detallado de la reso