Nuevas facetas para el problema general de rutas en un grafo mixto

Résumé

Los problemas de rutas tiene su origen en el conocido problema de los puentes de konigsberg planteado por Euler, Consisten, basicamente en encontrar rutas de longitud minima en un grafo cumpliendo una serie de condiciones. Algunas aplicaciones conocidas son el reparto de correo, recogida de basuras, mantenimiento de redes de todo tipo, etc. Casi todos estos problemas son NP-duros, por lo que el estudio de la estructura facial de su poliedro de soluciones es de fundamental importancia para el diseño de algoritmos exactos de resolucion basados en la formulacion decada Problema de Rutas como un Problema de Programacion Lineal. El Problema general de Rutas sobra un grafo mixto, MGRP, consiste en, dado un grafo mixto, encontrar un tour de longitud minima que pase, al menos una vez, por un subconjunto dado de aristas"requeridas", por un subconjunto dado de arcos "requeridos" y por un subconjunto dado de vertices "requeridos". Asi, el MGRP incluye, como casos particulares, a una gran parte de los problemas de rutas clasicos y puede considerarse como el problema de rutas con un solo vehiculo mas general. Estudios poliedricos conocidos de este problema describen varias familias de desigualdades que inducen faceta del poliedro de soluciones asociado. Este problema fue estudiado por Romero (1997) y por Corberan, romero y Sanchis (1998). En estos trabajos, se definio un poliedro de soluciones asociado, y se encontraron varias familias de desigualdades que inducen faceta del poliedro de soluciones asociado. En esta tesis presentamos una nueva familia de desigualdades que inducen faceta del poliedro de soluciones asociado al MGRP, las desigualdades Honeycomb. Esta es una familia muy amplia de desigualdades que fueron introducidas por Corberan y Sanchis(1998) para el GRP no dirigido. Hemos presentado dos versionesde estas desigualdades, las desigualdades Honeycomb"estandar", es decir, con los mismos coeficientes que en el caso no dirigido, y las des