El método de la ruta más corta es un método de programación lineal, que permite buscar la solución a un problema de optimización que resulte de una combinatoria y de diferentes aplicaciones, el objetivo de este método esta en encontrar rutas cortas o de menor costo, según sea el caso, que va desde un nodo especifico hasta cada uno de los demás nodos de la red.
En este sentido un nodo es una representación gráfica en forma de circulo, este nodo es muy importante ya que denota los orígenes y destinos del problema que se realice, asimismo una red representa un conjunto de puntos y líneas que conectan pares de puntos, estos puntos son los que llamaremos nodos y las líneas serían las aristas.
Un ejemplo simple para aplicar a este tipo de problemas sería el viaje de una persona desde un estado a ciudad el cual pudiese tener varias alternativas, según el interés de la persona, bien sea para ir más rápido o llegar de manera económica según sus recursos, para el primer caso se minimizaría la distancia y para el segundo caso el costo.
En cualquier caso el objetivo consistiría en encontrar la ruta más eficiente a un menor costo, y por lo tanto tendríamos que los estados estarán representados como los nodos y las carreteras como los arcos.
IMPORTANCIA
Este método es muy importante ya que por medio de este modelo se pueden resolver de manera rápida, ya que pueden formularse como modelos de redes obteniendo soluciones enteras sin necesidad de restricciones, aunque en algunos casos pudieran tenerlas. Asimismo se puede decir que no importa que tan grande sea el problema se puede resolver por pequeños algoritmos.
El problema de la ruta más corta es fundamental en muchas áreas, como son: Investigación de operaciones, ciencia de la computación e ingeniería.
Algunas de las razones son:
- La amplia variedad de aplicaciones prácticas como es el envío de algún material entre dos puntos específicos de la forma más eficiente, económica o rápida.
- Existen métodos de solución eficientes, los cuales al ser aplicados a una red con características específicas, proveen una solución exacta a un tiempo y costo razonables.
- Se puede utilizar como inicio en el estudio de modelos complejos de redes, esto es, cuando no se conoce la estructura de la red se pueden aplicar algoritmos para conocer algunas características de la red (presencia de ciclos negativos).
- Se utiliza frecuentemente como sub-problemas (subrutinas) en la solución de problemas combinatorios y redes, así en el caso de problemas para los cuales no existe un algoritmo de solución exacto, la aplicación de algoritmos de ruta más corta, resultan auxiliares para encontrar una buena solución.
APLICACIONES
En cuanto a sus aplicaciones este modelo tiene muchas aplicaciones en la vida práctica, dentro de las que podemos mencionar:
- Transporte,
- Horarios de operadores telefónicos,
- Planeación de tráfico urbano,
- Trasbordo,
- En las redes eléctricas,
- Diseño de rutas de vehículos,
- Telecomunicaciones,
- Planeación de inventarios,
- Planeación de producción, entre otros...
EL PROBLEMA
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"
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.
