PROGRAMACIÓN DE RUTAS
Programación de rutas
DISEÑO DE RUTAS PARA LOS
VEHÍCULOS
El tiempo durante el cual los artículos
están en tránsito se refleja en el número
de envíos que pueden hacerse con un
vehículo en un periodo dado, así como en
los costos totales de transportación para
todos los envíos.
Reducir los costos de transportación y
mejorar el servicio al cliente
encontrando los mejores caminos que
OBJETIVO debería seguir un vehículo en una red
de carreteras, líneas ferroviarias, líneas de
embarque o rutas de navegación aérea
que minimicen el tiempo o la distancia.
Programación de rutas
Diseño de rutas
Aunque hay muchas variaciones
dentro de los problemas de diseño de
rutas, podemos reducirlas a unos
cuantos tipos básicos.
Está el problema de:
• Cómo hallar un camino a través de
una red donde el punto de origen
es diferente del punto de destino.
• Hay un problema parecido cuando
existen múltiples puntos de origen
y de destino.
• Además, el problema de diseñar
las rutas cuando los puntos de
origen y destino son los mismos.
Programación de rutas
Diseño de rutas
Puntos de origen y destino separados y
sencillos
Método de la ruta más corta
Encuentre la ruta más corta de la siguiente red. Los números representan las
distancias correspondientes reales entre los nodos.
Programación de rutas
Método de la ruta más corta
Debemos partir del origen (O) y debemos llegar al Destino (T) y lo debemos hacer
por el camino o ruta más corta. Es decir tenemos que optimizar, minimizando costos
de envío del nodo Origen al Nodo destino
Vea la red tenemos tiene 11 nodos: Al salir del Nodo O se puede llegar a los Nodos A,B
y C, pero fíjese que se puede hacer a distintos costos 4,3 y 6 respectivamente. Lo cual
mostramos con cuadrados rojos sobre los nodos alcanzados o conocidos. OA=4,
OB=3,OC=6
Programación de rutas
Método de la ruta más corta
Ahora vamos a llegar al Nodo D; puede ver que
los nodos conocidos más cercanos son A y C, por
lo tanto se puede llegar a D desde A con 4+3=7;
pero se puede llegar a D dese C con 6+2=8, como
nos interesa el camino más corto elegimos AD
para un costo de 7. Ahora vamos a llegar a E;
puede ver que los nodos conocidos más
cercanos son B y C por tanto se puede llegar a E
desde B con 3+6= 9; pero se puede llegar a E
desde C con 6+5=11 como nos interesa el
camino más corto elegimos BE con un costo de 9
Ahora vamos a llegar a F; puede verse que los
nodos conocidos más cercanos son C,D y E, por
tanto se puede llegar a F desde C con 6 + 2= 8;
pero se puede llegar a F desde D con 7+2=9; pero
también se puede llegar a F desde E con 9+1=10;
puede verse que el más corto de los tres es 8 por
lo que elegimos CF.
Programación de rutas
Método de la ruta más corta
Ahora podemos alcanzar G desde los nodos
conocidos más cercanos D y F. por tanto se
puede llegar a G desde D con 7+4=11; pero se
puede llegar a G desde F con 8+2=10; puede
verse que es menos costoso llegar desde F por
lo que elegimos FD.
Ahora podemos alcanzar H desde los nodos
conocidos más cercanos E,F y G. Por tanto se
puede llegar H desde E con 9+2= 11; pero se
puede llegar a H desde F con 8+5=13; pero se
puede llegar a H desde G 10+2=12; puede
verse que el menos costoso es de EH con 11.
Ahora podemos alcanzar I desde los nodos
conocidos más cercanos E y H. Por lo tanto se
puede llegar a I desde E con 9 + 5=14; pero
puedo llegar I desde H con 11+3=14; vemos
que los costos son iguales desde E o desde H,
por lo que hay dos opciones posibles. HI y EI
Programación de rutas
Método de la ruta más corta
Ahora podemos alcanzar el nodo destino T desde los nodos conocidos más cercanos G,H e I. Por
tanto puedo alcanzar T desde G con 10+7=17; pero puedo alcanzar T desde H con 11+8=29 o puede
alcanzar T desde I con 14+4=18, puede verse que de los tres el menos costoso es 17 desde GT
Resultando la ruta óptima: OC-CF-FG-GT o lo que es lo mismo O-C-F-G-T = 17
Programación de rutas
Programación de rutas
Diseño de rutas
Puntos múltiples de origen y
destino
Programación lineal - Método de transporte
Cuando haya puntos múltiples de origen que
puedan servir a múltiples puntos de destino, OFERTA DEMANDA
hay un problema de asignación de los
destinos a esos orígenes, así como también
para hallar las mejores rutas entre ellos. Este
problema ocurre, normalmente, cuando hay
más de un vendedor, planta o almacén para
servir a más de un cliente el mismo
producto.
Es aún más complicado cuando los puntos
de origen están limitados por la cantidad de
demanda total del cliente que puede
suministrarse desde cada ubicación.
Programación de rutas
Diseño de rutas
Puntos múltiples de origen y
destino
Programación lineal - Método de transporte
El primer paso para la resolución de un problema de programación lineal
consiste en la identificación de los elementos básicos de un modelo
matemático, estos son:
Función Objetivo:
Variables:
Restricciones
Caso 1 – Oferta=Demanda
Programación de rutas
Diseño de rutas
Puntos múltiples de origen y
destino
Programación lineal - Método de transporte
Caso 2 – Oferta > Demanda
Caso 3 – Oferta < Demanda
