“

Modelo de la
ruta más
corta
”
 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 origen con un nodo destino, sin importar el número
de nodos que existan entre estos.

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, de menor costo o de menor
tiempo.
 Aplicaciones del
modelo

Transporte Horarios de operadores

telefónicos

Planeación de inventarios Planeación de

producción
Telecomunicaciones Redes
eléctricas

Transbordo

Planeación de tráfico
urbano Diseño de rutas de vehículos
 “
Planteamiento
del problema
”
La situación que enfrenta Gorman Construction. Gorman tiene varios sitios de construcción
localizados en un área que abarca tres condados de Estados Unidos. Debido a los múltiples
viajes diarios para transportar personal, equipo y suministros desde la oficina de Gorman a los
sitios de construcción, los costos asociados con las actividades de transporte son significativos.
Como algunos de los caminos son carreteras y otros son calles citadinas, las rutas de distancia
más corta entre la oficina y el sitio de construcción no necesariamente proporcionan la ruta
más rápida o de tiempo más corto. Aquí se muestra la red de carreteras de Gorman con el
tiempo de traslado en lugar de la distancia, la ruta más corta desde la oficina de Gorman al
sitio de construcción del nodo 6, el objetivo es minimizar el tiempo de traslado en lugar de la
distancia.
 30 MIN 4
2 40MIN

13 MIN
20 MIN

10 MIN
1 30 MIN
8
6

15 MIN 7 MIN
3
25MIN
12 MIN
5 7
20 MIN
 “

Solución
”
 Modelo de programación
lineal
1) Definición de las variables en función de la trayectoria de los
nodos.
VARIABLES

X12, X13, X23,

X24, X26, X32,
X35, X42, X45,
X46, X53, X54,
X56
 Modelo de programación
lineal
1) Definición de las variables en función de la trayectoria de los
nodos.
VARIABLES

X12, X13, X24,

X35, X45, X46,
X48, X54, X57,
X64, X67, X68,
X78
 X24

30 MIN 4 X48

X12
2 40MIN

X46 13 MIN
20 MIN X45
X68
X64
10 MIN
1 30 MIN
8
6
X54

15 MIN 7 MIN

X13 3 X67
25MIN
12 MIN
5 7 X78
20 MIN
X57
X35
 2) Determinación de la función objetivo..

MIN=40*X12+36*X13+6*X23+12*X24+25*X26+6*X32+15*X35+
12*X42+8*X45+11*X46+15*X53+8*X54+23*X56;

Debido a que lo que se

trata de encontrar es el
TIEMPO MÁS CORTO,
la función objetivo deberá
estar dirigida a
MINIMIZAR.
 2) Determinación de la función objetivo..
MIN=20*X12+15*X13+30*X24+20*X35+10*X45+13*X46+40*X48
+10*X54+12*X57+13*X64+7*67+30*X68+25*X78;

Debido a que lo que se

trata de encontrar es el
TIEMPO MÁS CORTO,
la función objetivo deberá
estar dirigida a
MINIMIZAR.
 3) Construcción de restricciones del modelo a partir de la ecuación.

Flujo de salida del nodo = Flujo de regreso al

nodo Se efectúa la
igualación a 0
para los nodos 2,
1
ODOS
X12+X13=1 X12+X13=1 3, 4 y 5

2 X23+X24+X26=X12+X32+X42 X23+X24+X26-X12-X32-X42=0

3 X32+X35=X13+X23+X53 X32+X35-X13-X23-X53=0

4 X42+X45+X46=X24+X54 X42+X45+X46-X24-X54=0

5 X53+X54+X56=X35+X45 X53+X54+X56-X35-X45=0

6 X26+X46+X56=1 X26+X46+X56=1
 3) Construcción de restricciones del modelo a partir de la ecuación.
Flujo de salida del nodo = Flujo de regreso al nodo

1 X12+X13=1 X12+X13=1 Se efectúa la

igualación = 0
2 X24=X12 X24-X12 para los nodos 2,
ODOS
3 X35=x13 X35-x13
3, 4,5, 6 y 7.

4 X45+X46+X48=X24+X54+X64 X45+X46+X48-X24-X54-X64=0

5 X54+X57=X35+X45+X75 X54+X57-X35-X45-X75=0
6 X64+X67+X68=X46+X76 X64+X67+X68-X46-X76=0

7 X75+X76+X78=X57+X67 X75+X76+X78-X57-X67=0

8 X48+X68+X78=1 X48+X68+X78=1
Restricción
X12+X13=1
X12+X13=1; Nodo 1
de origen.

X23+X24+X26-X12-X32-X42=0; Nodo 2
Restriccione X32+X35-X13-X23-X53=0; Nodo 3
s de X42+X45+X46-X24-X54=0; Nodo 4
transbordo. X53+X54+X56-X35-X45=0; Nodo 5

Restricción Nodo 6
X26+X46+X56=1;
de destino.
 Restricción
X12+X13=1; Nodo 1
de origen.

X24-X12=0; Nodo 2
Restricciones X35-x13=0; Nodo 3
X45+X46+X48-X24-X54-X64=0; Nodo 4
de transbordo.
X54+X57-X35-X45-X75=0; Nodo 5
X64+X67+X68-X46-X76=0; Nodo 6
X75+X76+X78-X57-X67=0; Nodo 7
Restricción
X48+X68+X78=1; Nodo 8
de destino.
 4) Modelo completo.

MIN=40*X12+36*X13+6*X23+12*X24+25*X26+6*X32+15*X35
+12*X42+8*X45+11*X46+15*X53+8*X54+23*X56;
!S.A.;
X12+X13=1;
X23+X24+X26-X12-X32-X42=0;
X32+X35-X13-X23-X53=0;
X42+X45+X46-X24-X54=0;
X53+X54+X56-X35-X45=0;
X26+X46+X56=1;
 4) Modelo completo.

MIN=20*X12+15*X13+30*X24+20*X35+10*X45+13*X46+40*X
48+10*X54+12*X57+13*X64+7*67+30*X68+25*X78;
!S.A.;
X12+X13=1;
X24-X12=0;
X35-x13=0;
X45+X46+X48-X24-X54-X64=0;
X54+X57-X35-X45-X75=0;
X64+X67+X68-X46-X76=0;
X75+X76+X78-X57-X67=0;
X48+X68+X78=1;
 “
Resultados
obtenidos
”
 Valor 63.00
objetivo.
X12 1 X42 0
X13 0 X45 0
Valor de las X23 0 X46 1
variables X24 1 X53 0
X26 0 X54 0
X32 0 X56 0
X35 0
 “
Interpretació
n de
resultados y
”
 Con los resultados obtenidos, se obtiene la siguiente interpretación:

Tiempo
mínimo de la 63.00 minutos
ruta
seleccionada
Debido a que las variables representan la
X12 1
Variables con unión de un nodo con otro, aquellas que
X24 1
valor mayor a presentan valor de 1, son las que indican la
X46 1
0 ruta a seguir..

Por lo tanto, el tiempo mínimo que se puede producir es de 63 minutos,

siguiendo la ruta que va del nodo 1 (nodo de origen) al nodo 2,
posteriormente al nodo 4 y finalizando, como lo indica el
planteamiento del problema, en el nodo 6 (nodo de destino).
 “
Diseño de
ruteo
obtenido
”
Nodo 1 – Nodo 2= 40
Nodo 2 – Nodo 4= 12
Nodo 4 – Nodo 6= 1 1

TOTAL = 63
 Nodo 1 – Nodo 2= 40
Nodo 2 – Nodo 4= 12
Nodo 4 – Nodo 6= 1 1

TOTAL = 63
30 MIN 4
2 40MIN

20 MIN 13 MIN

10 MIN
1 30 MIN
8
6

15 MIN 7 MIN
3 25MIN
12 MIN
20 MIN 5 7
¡Gracias
!