Resumen:

El Problema de Ruteo de Arcos Capacitados No Dirigidos con Beneficios (UCARPP – Undirected Capacitated Arc Routing Problem with Profits) es un problema de optimización combinatoria que consiste en encontrar un conjunto de rutas para una flota homogénea de vehículos que puedan satisfacer las demandas ubicadas en los ejes de un grafo. Los ejes  tienen asociadas una demanda y una ganancia que se obtiene si se satisface esa demanda. Cada eje tiene asociado también un tiempo de viaje, y puede ser transitado para atender un cliente en él. Los vehículos tienen una capacidad limitada. Sólo un vehículo puede recoger la demanda de un eje y cobrar la ganancia y se deben cumplir restricciones de duración máxima de las rutas y de capacidad de cada vehículo. El objetivo es maximizar la ganancia total. En este problema no se requiere recorrer todos los ejes con demanda o sea atender a todos los clientes.

UCARPP es un problema de optimización combinatoria que pertenece a la clase NP-Hard. En la literatura se han propuesto algoritmos exactos y heurísticas. Los primeros, obtienen soluciones óptimas sobre instancias de datos de tamaño reducido. Los segundos, en general, alcanzan soluciones cercanas a las óptimas y a bajo costo computacional. El objetivo de este trabajo fue desarrollar una heurística, basada en la metaheurística GRASP, que obtenga resultados competitivos y robustos.