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.

Palabras clave: Rural Postman Problem, General Routing Problem, poliedro, branch and cut

Programado

GT20 Transporte
7 de noviembre de 2023  16:50
HC2: Sala Canónigos 2


Otros trabajos en la misma sesión


Política de cookies

Usamos cookies solamente para poder idenfiticarte y autenticarte dentro del sitio web. Son necesarias para el correcto funcionamiento del mismo y por tanto no pueden ser desactivadas. Si continúas navegando estás dando tu consentimiento para su aceptación, así como la de nuestra Política de Privacidad.

Adicionalmente, utilizamos Google Analytics para analizar el tráfico del sitio web. Ellos almacenan cookies también, y puedes aceptarlas o rechazarlas en los botones de más abajo.

Aquí puedes ver más detalles de nuestra Política de Cookies y nuestra Política de Privacidad.