El problema del cartero rural en un grafo mixto

Abstract

La memoria plantea el estudio del poliedro de soluciones del Problema del Cartero Rural definido sobre un grafo mixto, Este problema generaliza al problema del Cartero Chino sobre un grafo mixto, así como al problema del Cartero Rural sobre un grafo no dirigido. El estudio del poliedro de sus soluciones comprende: su dimensión y una descripción parcial pero importante de sus facetas. La memoria se completa con el desarrollo de un heurístico, basado en Tabú Search, para la obtención de cotas superiores y con un esquema de planos de corte en el que se incorporan los resultados teóricos obtenidos anteriormente. Todo ello supone un esquema algorítmico completo que permite la resolución óptima, o casi óptima, de los problemas, como queda reflejado en el estudio computacional que cierra el trabajo.