PDF de programación - problema del camino Mínimo

http://optimos2.diinf.usach.cl/swc/

Bienvenidos al Sitio Web de Conocimiento sobre el Problema del Camíno Mínimo

En este sitio de de difusión de conocimiento científico y tecnológico el visitante se informa y
puede resolver instancias reales del "Problema del Camino Mínimo" (PCM), pues se pone a
disposición una potente calculadora científica como aplicación web.
El público objetivo considera académicos e investigadores en Optimización, estudiantes
universitarios y de Enseñanza Media (secundaria). También está orientado a las pequeñas y
medianas empresas, principalmente de Chile, en las que se puedan utilizar aplicaciones del
PCM. Además este material es una interesante fuente para investigación periodística
científica.
El Problema del Camino Mínimo, conocido también como "Shortest Path Problem" (SPP), es
uno de los clásicos de la investigación de operaciones y por décadas es material de trabajo
sobre modelos de "optimización de redes", que es un tipo especial de modelo de
programación lineal, pero que provee un lenguaje más intuitivo que hablar de ecuaciones,
funciones objetivo y restricciones.
La importancia del Problema del Camino Mínimo radica en la amplitud del espectro de
problemas que se puede abordar a través de los modelos que lo solucionan y porque lo
vemos muy frecuentemente en procesos de transporte y comunicaciones, así como también
en circuitos integrados para computadores, sistemas mecánicos e hidráulicos.

Teoría - Presentación del Problema (Parte I)

El Problema del Camino Mínimo (PCM) consiste en encontrar la ruta más corta en términos
de tiempo, dinero, distancia, etc. (cualquier índice de conveniencia), entre un punto y otro
dentro de una red. Ésta puede ser una red computacional, el tramado de calles, el esquema
de un proyecto, etc. Un problema típico de redes es encontrar alguna ruta desde la ciudad A
(el origen) hasta la ciudad B (el destino), donde se sabe que existen trayectorias alternativas
en diferentes puntos intermedios. El costo del recorrido va a depender de la ruta escogida, es
decir, se busca minimizar la suma de los tramos que conducen de A hasta B. Una red puede
ser representada conceptualmente a través de un grafo, que es una herramienta matemática
que permite un modelamiento y analogía directa. Un grafo se define como un conjunto de
nodos (puntos, vértices) y arcos (líneas, aristas), en que los nodos pueden representar
terminales computacionales, uniones de tuberías, etc. y los arcos pueden representar cables
de red, cañerías, etc. a cada arco se asocia un costo que puede representar el largo del
cable o la capacidad de la cañería. En la Ilustración 1 vemos la analogía de un grafo con
una red de caminos.

Teoría - Presentación del Problema (Parte II)

Para una red de pocos nodos, o no muy densa, se puede encontrar solución probando todas
las alternativas, es decir, usando "fuerza bruta", pero esto no es muy práctico. En los casos
reales el número de rutas es demasiado grande para permitir un completo análisis de todas
ellas. Es posible imaginar lo complejo que sería estimar la ruta óptima entre un par de puntos
de una ciudad como Santiago de Chile o New York al hacer la analogía con la ilustración 2.

Teoría - Trascendencia del Problema

Los problemas de Camino Mínimo están en la columna vertebral de la optimización del flujo
en redes, y motivan el estudio de si a implementadores de código y investigadores, por varias
razones según sugieren Ahuja, Magnantin y Orlin [1].

• Aparecen frecuentemente en la práctica en una amplia variedad de aplicaciones en

que se desea enviar cosas entre dos puestos tan rápida, barata o confiablemente
como sea posible.

• Son fáciles de resolver con eficiencia.
• Siendo los modelos de red más simples logran capturar muchos de los más

sobresalientes ingredientes centrales de los flujos en redes y una referencia y sirven
como una base para estudiar modelos más complejos.

• Aparecen frecuentemente como subproblemas al resolver muchos problemas

combinatorios y de optimización de redes.

• El estudio de problemas de caminos mínimos es un punto de partida para introducir
muchas ideas clave sobre flujo en redes, como las estructuras de datos que suelen
usarse, entre las que hallamos por ejemplo a los grafos.

El mundo es cada vez más rápido, se aprecia lo instantáneo, se quiere el óptimo. Cualquier
solución a un problema de optimización es valioso per se.

Generalmente los problemas prácticos que requieren del SPP aparecen en las industrias de
telecomunicaciones y transporte cuando se quiere enviar un mensaje o vehículo entre dos
emplazamientos geográficos, buscando reducir tiempo o dinero invertido, pero son muchas
las aplicaciones reales como por ejemplo.

• En empresas de transporte y telecomunicaciones.
• Desarrollo de circuitos integrados para computadores.
• Sistemas mecánicos e hidráulicos.
• La administración de proyectos.
• El planeamiento de reposición de inventarios.
• Secuenciación de ADN.
• Aproximación de funciones matemáticas.
• Distribución de costos de inspección entre etapas de líneas de producción.
• Asignación horarios de trabajo a operadores telefónicos y similares.
• El problema del sistema de inecuaciones de diferencias (System of Difference

constraints).

• El clásico problema de la mochila que consiste en decidir qué cosas llevar en un viaje
cuando hay capacidad de carga limitada y se requiere la más larga supervivencia
posible.

• La planificación del tráfico urbano, etc.

Tomando el ejemplo del tráfico urbano, en la práctica, los modelos que los urbanizadores
usan para calcular patrones de flujo de tráfico son problemas de optimización no lineal
compleja o modelos de equilibrio complejo que ellos construyen sobre el supuesto de que los
usuarios del sistema se comportarán viajando a través de las rutas más cortas entre sus
salidas y destinos, con respecto a la congestión de tráfico en un momento dado. Así es como
la mayoría de las implementaciones para encontrar patrones de tráfico urbano resuelven una

gran cantidad de problemas de camino mínimo como subproblemas, en efecto, hay una
instancia de PCM a resolver para cada par de origen y destino posible en la red, este sería
un problema combinatorio.

Teoría - Definición Formal del Problema del Camino Mínimo

Sea un grafo G(N, A) en el cual a cada arco (i, j) se le asigna un valor numérico dij, llamado
longitud o costo. La longitud Lij, de un camino Pij, es la suma de las longitudes de todos los
arcos que lo componen como se ilustra en la Relación 1:
El problema del camino mínimo consiste en determinar el camino de menor longitud entre un
par de nodos. Sea Kij el conjunto de caminos existentes entre el par de nodos i y j, entonces
el costo del camino mínimo L* entre estos nodos es como es aprecia en la Relación 2:

En otras palabras se busca minimizar la suma de los tramos que conducen de un punto
(nodo) a otro y que juntos conforman una ruta o camino, la distancia propiamente dicha se
llama costo mínimo (L*) y el itinerario se llama camino mínimo (aquel Pij que satisface L*).

Teoría - Algoritmos Solución

En la literatura sobre algoritmos de flujo en redes se halla comúnmente una clasificación de
las creaciones algorítmicas para resolver el Problema del Camino Mínimo que separa el
universo de soluciones en dos grandes familias. Comparten que son de tipo iterativo y
asignan etiquetas de distancias tentativas para los nodos encada paso, pero la
implementación varía en como cada uno de los tipos algoritmos actualizan las etiqueta de
distancia en cada paso y como convergen hacia los valores de las distancias de la ruta más
corta.
1. Label Setting:

• Tienen como algoritmo básico al de Dijkstra, teniendo entre sus variantes a los

algoritmos "heap", "reverse", bidireccional, "radix heap", etc. Otro algoritmo particular
en esta familia es el Ford-Moore-Bellman.

• Designa una etiqueta como permanente (óptima) en cada iteración.
• Resuelve problemas acíclicos y con grafos con arcos con largos no negativos.

2. Label Correcting:

• Tiene algoritmos como el Label-Correcting genérico, el modificado, el "todos con

todos" y el Floyd-Warshall.

• Considera todas las etiquetas como temporales hasta el paso final.
• Es más general y resuelve todo tipo de problemas.

Soluciones Heurísticas
El Problema del Camino Mínimo ha sido ampliamente estudiado en su versión deterministica,
pero los avances en el campo de la optimización estocástica han motivado a revisitar los
problemas de redes clásicos con relajadas consideraciones sobre el determinismo de varios
parámetros. Muchas de las investigaciones sobre el SPP a-priori estocástico han enfrentado
variaciones dinámicas del problema. Un algoritmo heurístico eficiente es de autoría de Fu &
Rilett (1998) y uno NP óptimo es presentado en Hall (1986) y en Miller-Hooks & Mahmassani
(1999).