El problema general de rutas con viento(windy general routing problem, wgrp)

Resumen

En esta tesis, hemos estudiado el Problema General de Rutas con Viento (WGRP), Dicho problema consiste en, dado un grafo G=(V,E), con un conjunto de vértices V, un conjunto de aristas E y dos costes c(i,j), c(j,i) asociados a cada arista, uno por sentido de recorrido, y dados un subconjunto de vértices requeridos VR perteneciente a V y un subconjunto de aristas requeridas ER incluido en E, hallar un tour de coste mínimo que recorra al menos una vez todas las aristas requeridas y visite todos los vértices requeridos. Este problema tiene un doble interés, ya que modeliza situaciones reales, de las cuales presentamos detalladamente un ejemplo en esta memoria, y, al mismo tiempo, generaliza a la mayoría de Problemas de Rutas por Arcos con un solo vehículo conocidos.Hemos estudiado el poliedro asociado al espacio de soluciones del problema, describiendo las siguientes familias de esigualdades y demostrando que definen faceta del poliedro: desigualdades triviales, desigualdades de obligatoriedad, esigualdades de conectividad, desigualdades de cortes R-impares, desigualdades K-C y K-C02, desigualdades Path-Bridge y Path-Bridge02 y desigualdades Honeycomb y Honeycomb02.También hemos introducido un teorema de ``lifting'' que afirma que todas las desigualdades de configuración que inducen faceta para el WGRP en el grafo de configuración también inducen faceta del WGRP en el grafo original. Sin embargo, hemos visto que no todas las desigualdades que inducen faceta del poliedro del WGRP son desigualdades de configuración, por lo que hemos introducido el concepto de desigualdad de configuración débil. También hemos presentado una nueva familia de desigualdades válidas que inducen facetas para el WGRP, llamadas Zigzag, y que se engloban dentro de esta nueva categoría de desigualdades. Hemos estudiado la aplicación de estas nuevas desigualdades en otros problemas que son casos particulares del WGRP, así como bajo qué condiciones so