Algunos problemas de rutas por arcos

2014

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…