Rutas más cortas

ÍNDICE:

Algoritmo de la ruta más corta

Ya el nombre de este tipo de algoritmo es bastante sugestivo. El algoritmo de la ruta más corta consiste, si es necesario decirlo, en una modalidad de problemas de redes, en la cual se debe determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino, sin importar el número de nodos que existan entre estos.

Vale la pena considerar, que en la práctica, es muy frecuente la utilización del algoritmo resultante con variaciones que consisten en la minimización de tiempos, no necesariamente de distancias.

Algoritmo de la ruta más corta – Ejemplo

Un minero ha quedado atrapado en una mina, la entrada a la mina se encuentra ubicada en el nodo 1, se conoce de antemano que el minero permanece atrapado en el nodo 9, para llegar a dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta de acceso al nodo 9 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente gráfica dadas en cientos de metros. Formule un modelo de transbordo y resuelva mediante cualquier paquete de herramientas de investigación operativa que permita establecer la ruta más corta para poder así auxiliar al minero.

Variables de decisión

El nombre de las variables en este caso poco importa, dado que de ser escogida para la solución básica eso significa simplemente que será empleada como ruta para ir a rescatar al minero, sin embargo nada tiene de malo el que se le pueda asociar con el envío de unidades desde la entrada de la mina hacia el minero, por ende puede sugerirse este como nombre de las variables. «Cantidad de unidades enviadas desde el nodo i hacia el nodo j».

X₁₂ = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2

X₁₃ = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3

X₂₃ = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3

X₂₄ = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4

X₃₂ = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2

Page updated

Report abuse