Diseño óptimo de la red

El diseño óptimo de redes viales es un problema de optimización combinatoria . Representa de forma abstracta el problema al que se enfrentan los estados y municipios al planificar su red de carreteras. Dado un conjunto de ubicaciones que se conectarán mediante carreteras, el objetivo es lograr una corta distancia entre cada par de puntos. Más específicamente, se busca minimizar la suma de las distancias más cortas, calculada sobre todos los pares de puntos. Para cada par de ubicaciones, existe un valor que representa el costo de construir una carretera directa entre ellas. Se debe decidir qué carreteras construir con un presupuesto fijo.

La entrada al problema de diseño óptimo de la red es un grafo ponderado G = (V,E), donde el peso de cada arista (u,v) en el grafo representa el costo de construir una carretera de u a v; y un presupuesto B.

Una red factible es un subconjunto S de E, tal que la suma de w(u,v) para todos los (u,v) en S es como máximo B, y hay un camino entre cada par de nodos u y v (es decir, S contiene un árbol de expansión de G).

Para cada red factible S , el costo total de S es la suma, sobre todos los pares (u,v) en E, de la longitud del camino más corto de u a v, que utiliza únicamente aristas en S. El objetivo es encontrar una red factible con un costo total mínimo.

Johnson, Lenstra y Kan demuestran que el problema es NP-difícil , incluso para el caso simple en el que todos los pesos de las aristas son iguales y el presupuesto restringe la elección a árboles de expansión. ^{[ 1 ]}

Dionne y Florian estudiaron algoritmos de ramificación y acotación , y demostraron que funcionan en un tiempo razonable con entradas de tamaño medio, pero no con entradas grandes. Por lo tanto, presentaron algoritmos de aproximación heurística . ^{[ 2 ]}

Anshelevic, Dasgupta, Tardos y Wexler estudian un juego de diseño de redes, donde cada agente tiene un conjunto de terminales y desea construir una red en la que sus terminales estén conectadas, pero pagando lo menos posible. Estudian el problema computacional de verificar si existe un equilibrio de Nash . Para algunos casos especiales, proporcionan un algoritmo de tiempo polinomial que encuentra un equilibrio de Nash (1+ε) -aproximado. ^{[ 3 ]}

Boffey y Hinxman presentan un método heurístico y demuestran que produce resultados de alta calidad. También estudian métodos de solución basados ​​en ramificación y acotación, y evalúan los efectos de realizar diversas aproximaciones al calcular cotas inferiores. Además, generalizan el problema a redes con un coste de construcción de enlaces no proporcional a la longitud y con demandas de viaje que no son todas iguales. ^{[ 4 ]}

• Planificación y diseño de redes
• Árbol de expansión de coste de enrutamiento mínimo : un problema similar en el que el conjunto seleccionado debe ser un árbol de expansión.