Descripción del título
Introducción de dependencia...
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) obteniendo el Problema del Agente Viajero con Dependencia Horaria de los Costes (PA VDHC). 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-polinomial 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 transformado 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 resolución aproximada del PAVDHC mediante tres procedimiento
Recurso Electrónico
recurso_electronico Rebiun18983316 https://catalogo.rebiun.org/rebiun/record/Rebiun18983316 050119s2004 sp q d u spa d 8468861499 UPVA 990001986760203706 B-UPV Albiach Vicent, José 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 Recurso electrónico-CD-ROM] [tesis doctoral presentada por] José Albiach Vicent ; [dirigida por David Soler Fernández] Valencia Editorial UPV 2004 Valencia Valencia Editorial UPV 1 disco (CD-Rom) 12 cm 1 disco (CD-Rom) Tesis doctoral / Universidad Politécnica de Valencia Ref.: 2004.5197 Tesis Univ. Politécnica de Valencia 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) obteniendo el Problema del Agente Viajero con Dependencia Horaria de los Costes (PA VDHC). 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-polinomial 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 transformado 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 resolución aproximada del PAVDHC mediante tres procedimiento p_5197-1-1 Estudio de tiempos- Costes- Tesis doctorales Soler Fernández, David Universidad Politécnica de Valencia. Departamento de Matemática Aplicada