I. Plana Andani, Á. Corberán Salvador, J. M. Sanchis Llopis, P. Segura Martínez
El Problema del Cartero Rural (Rural Postman Problem, RPP) es uno de los problemas más conocidos en el área de problemas de rutas por arcos. Dado un grafo no dirigido con un coste asociado al recorrido de cada arista, y un subconjunto de aristas requeridas, el objetivo del RPP es encontrar un recorrido cerrado con coste total mínimo que pase por todas las aristas requeridas al menos una vez. El Problema General de Rutas (General Routing Problem, GRP) es una generalización del RPP en la cual tenemos, además, un subconjunto de vértices requeridos que deben ser visitados por la solución. En este trabajo proponemos una nueva formulación para el GRP y el RPP y presentamos varias familias de desigualdades que inducen facetas del poliedro de soluciones, las cuales empleamos para diseñar un algoritmo de ramificación y corte (branch and cut). Finalmente, realizamos extensas pruebas computacionales y comparamos los resultados con otros métodos exactos previamente publicados.
Keywords: Rural Postman Problem, General Routing Problem, poliedro, branch and cut
Scheduled
GT20 Transportation
November 7, 2023 4:50 PM
HC2: Canónigos Room 2