OPTIMIZACION DE REDES RUTA MÁS CORTA
El problema de la ruta más corta determina la distancia menor entre un punto de origen y un punto de
destino.
Un problema de la ruta más corta involucra una red conexa con un costo no negativo asociado a cada
rama. A un nodo se le denomina fuente y a otro se le denomina destino. El objetivo es determinar una
ruta que una a la fuente con el origen, de manera que la suma de los costos asociados con las ramas
en la ruta sea la mínima.
El algoritmo de Dijkstra es útil para determinar la ruta más corta entre el nodo del punto de origen y
cada uno de los nodos de la red. Por otra parte, el algoritmo de Floyd es más general porque permite
determinar la ruta más corta entre cualquier par de nodos de la red.
Es necesario especificar el nodo inicial y nodo terminal, es un caso particular del problema de
arborescencia. La longitud de una ruta o camino es la suma de las longitudes de los arcos que la
forman, la que es mínima se le llama ruta más corta.
Se le puede asociar la red:
R= [X, A, d]
X: Conjunto de nodos
A: Conjunto de arcos dirigidos
d: Distancias / Costos
Entre este tipo de problemas, se puede encontrar una sub clasificación de problemas específicos:
Mochila
Reemplazo
Planeación de Producción
Ruta más Segura
Los algoritmos que dan solución a éste problema son Algoritmo de Dijkstra, Algoritmo de Dijkstra
Generalizado o a través de utilizar los métodos desarrollados para el Modelo de Programación Lineal.
Problema de la Ruta Más Corta (RMC)
Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A
cada ligadura (arco no dirigido) se asocia una distancia no negativa, el objetivo es encontrar la
ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.
La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera
sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más
cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino
(Hillier, 2010).
▸Determine la ruta más corta en millas, para el ejemplo de Seervada Park.
▸PASO 1. Iniciar desde el nodo de origen e ir avanzando hacia el nodo final (recursividad de
avance).
▸PASO 2. Colocar entre corchetes en el lado izquierdo el valor que tiene la rama y en el lado
derecho la letra o número correspondiente al nodo predecesor.
▸PASO 3. Seleccionar el corchete con el valor menor y continuar hacia adelante a partir de este.
▸NOTA 1: Cuando se selecciona un nuevo nodo con el valor menor, se debe ir contemplando la
suma acumulativa de las ramas anteriores correspondientes.
Solución del ejemplo Prototípico por Algoritmo de Dijkstra
▸Se selecciona el nodo A puesto que tiene la distancia más corta de los 3 (tres) nodos que salen
del origen.
▸Continuando a partir del nodo A, se busca a que nodos se conecta y se suma el valor de la
rama anterior más el valor de la rama actual y se elige el menor, en este caso es el nodo B.
▸Se descarta el nodo B, puesto que no mejora la distancia del nodo origen al nodo C, al contrario
aumenta, y se selecciona el nodo E.
▸Se selecciona el nodo D, sin embargo, hay dos opciones que llevan al nodo D con el mismo
valor, por lo cual se consideran dos alternativas.
▸Finalmente se llega al nodo final con un valor de 13 millas que representa la distancia más
corta, siendo la ruta más corta las mostradas en rojo y azul.
Conclusión
▸La distancia más corta desde la entrada del parque hasta el mirador es de 13 millas, las dos
rutas óptimas (trayectorias) son las siguientes:
▸O-A-B-E-D-T
▸O-A-B-D-T
▸Esta ruta permite reducir costos de transportación de los vehículos que llevan a los visitantes,
por ejemplo costos de gasolina.
