Algunos problemas de rutas por arcos

Resumen

En esta tesis se estudian tres problemas de rutas por arcos muy importantes tanto a nivel práctico como teórico. Se tratan del General de Rutas por Arcos en un grafo dirigido (Directed General Routing Problem, DGRP), su caso particular, el problema de la Grúa (Stacker Crane Problem, SCP) y el problema del Cartero Rural Generalizado en un grafo dirigido (Generalized Directed Rural Postman Problem, GDRPP). El primer problema estudiado es problema de la Grúa el cual se define en un grafo mixto G=(V,E,A), donde cada arista o arco, (i,j), tiene un coste asociado cij > 0, y tiene como objetivo hallar una ruta de coste mínimo que recorra al menos una vez cada arco del grafo. El problema General de Rutas por Arcos en un grafo dirigido se define en un grafo dirigido G=(V,A) con costes no negativos asociados a los arcos donde, dados un subconjunto de arcos requeridos A_R y un subconjunto de vértices requeridos V_R, se trata de encontrar una ruta de mínimo coste que recorra todos los arcos requeridos y visite todos los vértices requeridos. Por último, el problema del Cartero Rural Generalizado en un grafo dirigido se define en un grafo dirigido G=(V,A) con costes no negativos asociados a los arcos en el que, dados unos conjuntos de arcos H_1,...,H_n, el objetivo es encontrar una ruta de coste mínimo que recorra al menos un arco de cada conjunto H_i. El estudio y resolución de estos problemas ha sido abordado en esta tesis desde el punto de vista de la Combinatoria Poliédrica, uno de los enfoques más útiles para la resolución de muchos problemas NP-difíciles de optimización combinatoria. Se presenta dentro de ella, un heurístico, basado en una búsqueda local iterada, para la resolución aproximada del SCP, un algoritmo de ramificación y corte para el DGRP y otro para el GDRPP. Resolviendo instancias del DGRP y del SCP que varían entre 100 y 3000 arcos requeridos y 500 y 5000 vértices. Así como instancias del GDRPP, donde los tamaños van desde 1000 a 1500 arcos, de 500 a 800 vértices y de 500 a 15000 clientes. Los resultados obtenidos en esta tesis doctoral han mejorado, a veces de forma sustancial, los presentados por otros autores para estos o similares problemas. .