50 Años de Arc Routing

Abstract

Hace poco más de 50 años, un matemático chino, Meigu Guan, planteó el problema de encontrar un recorrido de las aristas de un grafo no dirigido que fuera el más corto posible. Guan buscaba minimizar la longitud de un camino cerrado que pasara por cada arista del grafo al menos una vez y, así, encontrar una ruta de longitud mínima para un cartero que debe recorrer cada calle de la zona que tiene asignada para repartir el correo. El artículo de Guan, sobre lo que posteriormente se conoció como el Problema del Cartero Chino, fue el primero de una larga serie de contribuciones en el área de las Rutas por Arcos (Arc Routing). Básicamente, los problemas de rutas por arcos consisten en determinar un recorrido de coste mínimo de todos o algunos arcos y/o aristas de un grafo, posiblemente sujeto a algunas condiciones adicionales. Estos problemas definen un área apasionante porque, por una parte, la mayoría de ellos son problemas que plantean un desafío desde el punto de vista de su estudio y resolución y, por otro lado, porque aparecen en muchas situaciones prácticas de la vida real como la recogida de basuras, la limpieza de las calles y el mantenimiento de carreteras o vías de tren y, puesto que el dinero involucrado en estas operaciones representa millones de euros, existe un considerable potencial para el ahorro. Esta charla es sobre el recorrido de los arcos (y aristas) de un grafo, los problemas de rutas por arcos, su historia y resolución, y sus aplicaciones a problemas de la vida real.