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.

Esta modalidad de problemas puede solucionarse como un modelo de transbordo normal, sin embargo la principal sugerencia es la de establecer una oferta en el nodo fuente igual a una unidad (1) y establecer una demanda en el arco destino igual a una unidad (1).

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

El caso

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».

X12 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 2

X13 = Cantidad de unidades enviadas desde el nodo 1, hacia el nodo 3

X23 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 3

X24 = Cantidad de unidades enviadas desde el nodo 2, hacia el nodo 4

X32 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 2

X34 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 4

X35 = Cantidad de unidades enviadas desde el nodo 3, hacia el nodo 5

X46 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 6

X47 = Cantidad de unidades enviadas desde el nodo 4, hacia el nodo 7

X54 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 4

X56 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 6

X57 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 7

X58 = Cantidad de unidades enviadas desde el nodo 5, hacia el nodo 8

X67 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 7

X69 = Cantidad de unidades enviadas desde el nodo 6, hacia el nodo 9

X76 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 6

X78 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 8

X79 = Cantidad de unidades enviadas desde el nodo 7, hacia el nodo 9

X87 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 7

X89 = Cantidad de unidades enviadas desde el nodo 8, hacia el nodo 9

Restricciones

Restricciones de Oferta y Demanda

Hay que recordar que el objetivo de este modelo es la consecución de un plan de ruta que nos permita encontrar al minero lo más pronto posible al recorrer la distancia mínima posible, por ende la clave para plantear el modelo como si fuese de transbordo es establecer una demanda y oferta igual a la unidad (1).

X12 + X13 = 1

X69 + X79 + X89 = 1

Restricciones de Balance

X12 + X32 – X23 – X24 = 0

X13 + X23 – X32 – X34 – X35 = 0

X24 + X34 + X54 – X46 – X47 = 0

X35 – X54 – X56 – X57 – X58 = 0

X46 + X56 + X57 – X67 – X69 = 0

X67 + X47 + X57 + X87 – X76 – X78 – X79 = 0

X78 + X58 – X89 = 0

En palabras sencillas: «Todo lo que entra a cada nodo es igual a lo que sale de él»

Función objetivo

ZMIN = 4X12 + 2X13 + 2X23 + 7X24 + 4X32 + 9X34 + 6X35 + 1X46 + 5X47 + 2X54 + 4X56 + 3X57+ 2X58 + 1X67 + 5X69 + 4X76 + 3X78 + 5X79 + 2X87 + 7X89

Ingresando los datos en WinQSB

Solución obtenida mediante WinQSB

La ruta más corta para rescatar al minero  tiene como distancia total 1600 metros (dado que las distancias estaban dadas en cientos de metros) y es tal como se muestra en la siguiente gráfica:

Sin embargo, WinQSB cuenta con una metodología mucho más sencilla de resolución de algoritmos de ruta más corta, metodología que explicaremos más adelante, de todas formas hemos encontrado cómo, aplicando debidamente la razón y un algoritmo conocido como el de transbordo, podemos solucionar problemas distintos en teoría.


Solución del algoritmo de la ruta más corta mediante WinQSB

El módulo del WinQSB que permite la resolución del algoritmo de la ruta más corta

 es el Network Modeling, el cual utiliza una interfaz muy sencilla en forma de matriz en la cual hay que ingresar el valor de los ramales (dependiendo del contexto este valor puede representar distancias, tiempo, costos etc.) correspondiente a cada relación de un nodo con otro.

Paso a paso

Primero se debe ingresar al módulo Network Modeling del paquete WinQSB, una vez nos encontremos en este aparecerá el menú que se muestra en la siguiente gráfica, menú en el cual tendremos que seleccionar la opción Shortest Path Problem (Problema de la ruta más corta).

Además en este menú emergente debemos de ingresar la cantidad de nodos que conforman la red del problema y tenemos la posibilidad de asignarle un nombre al mismo, en nuestro caso la cantidad de nodos de la red es igual a 9; clic en OK y aparecerá la siguiente ventana.

En esta ventana se debe ingresar la magnitud de cada ramal correspondiente a cada relación entre los nodos, tal como veremos a continuación.

Damos clic en Solve and Analize y tendremos un menú emergente en el cual tendremos que seleccionar el nodo fuente y el nodo destino, tal como se muestra en la siguiente gráfica.

Una vez efectuada la selección tendremos la opción de ver el tabulado final y la opción de ver un paso a paso gráfico; para el tabulado final click en SOLVE y para el paso a paso clic en SOLVE AND DISPLAY STEPS.

Podemos cotejar la solución que obtuvimos al plantear este problema como un modelo de transbordo con esta solución. La eficiencia se encuentra determinada en escoger la herramienta adecuada para resolver el problema planteado.


Le recomendamos revisar: Problema de la ruta más corta en Google OR-ToolsDescubre esta poderosa herramienta de modelamiento y solución de problemas de optimización.

Bryan Salazar López

Ingeniero Industrial y Magíster en Logística Integral especializado en productividad y modelamiento de procesos bajo dimensiones de sostenibilidad, industria 4.0, transformación digital y modelos de optimización. Docente universitario de pregrado y posgrado con experiencia en la enseñanza de estos temas. Fundador de Ingenieriaindustrialonline.com, un sitio en donde se recogen las aportaciones de investigaciones, artículos y referencias relevantes para la industria.

Entradas recientes

El sentido común y la Teoría de Restricciones (TOC)

En una pequeña comunidad agrícola en Michoacán, México, un niño llamado José Hernández soñaba con…

hace % días

La restricción nos blinda contra las malas noticias

Sábado por la mañana, Robert acaba de acompañar a su mujer a su clase de…

hace % días