El problema de la ruta más corta

PROBLEMA DE LA RUTA MÁS CORTA

El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino. El problema se resuelve por el “algoritmo de etiquetado”.

Se trata de encontrar la ruta de menor distancia, o costo ,a entre el punto de partida o nodo inicial y el destino o nodo terminal.

DEFINICIÓN DEL PROBLEMA

-Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.

-Arcos bi-direccionales conectan los nodos i y j con distancias mayores que cero, dij

-Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.

Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.

Pasos a seguir:

Primer paso: Elaborar un cuadro con todos los nodosy los ramales que salen de él.

Segundo paso: Partiendo del origen, debemos encontrar el nodo más cercano a él.

Tercer paso: Anular todos los ramales que entren al nodo más cercano elegido.

Cuarto paso: Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino.

PROBLEMA DE LA RUTA MÁS CORTA

¿Cuál es el camino más corto desde la origen (s de “source”) hasta el destino (t) ?

Supuestos:

Existe un camino de la fuente a todos los demás nodos

Todos los largos de los arcos son no negativos

• ¿Cuál es el camino más corto del nodo 1 al 6 ?

PROBLEMA DE LA RUTA MÁS CORTA

• En general la formulación con LP de este problema, desde una origen s a un destino t está dada por:

PROBLEMA DE LA RUTA MÁS CORTA

• Otra formulación, para determinar la ruta más corta a n nodos es enviar “un” paquete a desde s a cada n-1 nodos.

EJEMPLO 1:

Consideremos el siguiente diagrama donde los números asignados a cada uno de los arcos representan la distancia en kilómetros de un nodo a otro. Se desea encontrar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.

El tamaño reducido de la red anterior permite encontrar el camino más corto simplemente enumerando las distintas alternativas que comenzando en el nodo 1 permita llegar al nodo 8. De esta forma las rutas posibles son:

• Ruta 1-2-5-7-8: 4+8+17+9=38[km]

• Ruta 1-3-4-7-8: 3+12+20+9=44[km]

• Ruta 1-3-4-6-8: 3+12+2+22=39[km]

• Ruta 1-3-4-8: 3+12+15=30[km]

• Ruta 1-3-6-8: 3+4+22=29[km]

La ruta o camino más corto es 1-3-6-8 con una distancia total de 29[km].

MODELO DE FLUJO MAXIMO

En algunas redes circula por los arcos un flujo (envío o circulación de unidades homogéneas de algún producto: automóviles en una red de carreteras, litros de petróleo en un oleoducto, bits por un cable de fibra óptica) desde el origen o fuente al destino, también denominado sumidero o vertedero. Los arcos tienen una capacidad máxima de flujo, y se trata de enviar desde la fuente al sumidero la mayor cantidad posible de flujo, de tal manera que:

El flujo es siempre positivo y con unidades enteras.

El flujo a través de un arco es menor o igual que la capacidad.

El flujo que entra en un nodo es igual al que sale de él.

En el caso de que el origen o el destino no existan en el problema, se añaden ficticiamente utilizando arcos unidireccionales de capacidad infinita, como en grafo mostrado a continuación:

Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad proporciona el flujo máximo en la red.

USOS DEL ALGORITMO DE FLUJO

...