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.

Ruta más Corta.

Líneas Fairway Van

  • Determine la ruta mas corta entre Seattle y El Paso para la siguiente red de carreteras.
  • Solución- Analogía de un problema de programación lineal.

- Variables de Decisión

  • Solución- Analogía de un problema de programación lineal.

- Variables de Decisión

 

EJEMPLO 2.

Ruta más Corta.

  • Solución:


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: