Nuevos resultados con una formulación para el Problema de Rutas por Arcos con Capacidades

J. M. Belenguer, E. Benavent, Á. Corberán, I. Plana, C. Prins, G. Reinelt, J. M. Sanchis

En este trabajo analizamos una formulación entera para el Problema de Rutas por Arcos (CARP) definido en un grafo no dirigido, la cual usa variables dirigidas. Para esta formulación, se ha implementado un algoritmo de branch-and-cut para resolver óptimamente el CARP. Se han incluido todas las familias conocidas de desigualdades válidas para este problema y para el Problema del Cartero Rural, el cual es un caso particular del CARP. Para cada una de ellas, se han implementado los correspondientes algoritmos de separación. Además, también proponemos y separamos nuevas clases de desigualdades válidas. Finalmente, presentamos resultados computaciones usando conjuntos de instancias de la literatura.

Palabras clave: rutas por arcos branch-and-cut programación entera

A. A. Juan Perez, J. Panadero, C. Bayliss, L. Martins, A. Freixes, D. Raba

A. M. Florio, R. F. Hartl, S. Minner, J. J. Salazar González

F. Perea Rojas-Marcos