Experimentos con diferentes formulaciones del Problema de Rutas por Arcos con Capacidades

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

Presentamos dos formulaciones enteras diferentes del Problema de Rutas por Arcos con Capacidades (Capacitated Arc Routing Problem, CARP) definido en un grafo no dirigido. Una formulación usa variables dirigidas mientras que la otra usa variables no dirigidas. Para cada formulación hemos implementado un código de branch-and-cut para resolver exactamente el CARP. Intentamos incorporar todas las familias de restricciones válidas conocidas para este problema y el problema de Cartero Rural, incluyendo en el código los correspondientes algoritmos de separación para cada una de ellas. Finalmente presentamos algunos resultados computaciones preliminares

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

J. M. Daza Escorcia, J. M. Belenguer, E. Benavent

F. Parreño, R. Álvarez-Valdés, M. T. Alonso