RUTEO DE VEHÍCULOS
• IMPORTANCIA: el costo de transportación
constituye de 1 a 2 tercios del costo
logístico total.
T E N D E N C IA
R E Q U IE R E E N V ÍO S
 V ariab ilid ad de la
D em an d a
 S erv icio al C lien te
 M ín im o In v en tario
en P ro d u ció n y
D istrib ució n
 P eq u eñ o s
 M ás rápid o
 M ás frecu en tes
 M ás a tiem p o
 A lta C o m p eten cia
1
RUTEO DE VEHÍCULOS
El tiempo que los bienes se encuentran en
tránsito determina el número de envíos que
un vehículo puede realizar en un período de
tiempo y el costo de transportación total
para todos los envíos
BENEFICIOS
• Reducir el costo de transporte es de interés
de la empresa (micro) y del país (macro)
• Mejor utilización de recursos y de personal
• Mejora el ambiente
• Menor gasto energético
• Reduce problemas de tránsito
OBJETIVO
EL OBJETIVO EN EL PROBLEMA DE RUTEO
DE VEHÍCULOS ES LA MINIMIZACIÓN DE
TIEMPO, DINERO Y DISTANCIA DADOS
CIERTOS PARÁMETROS RELEVANTES
Minimizar la distancia recorrida en:
• Entrega de órdenes semanales o diarias a clientes
dispersos en una zona geográfica
• Entregas a partir de un Centro de Distribución
• Uso de un solo vehículo
RESTRICCIONES
• CAPACIDAD DE LOS VEHÍCULOS
• LÍMITE DEL TIEMPO TOTAL QUE UN
VEHÍCULO OCUPA EN LA RUTA
• ASIGNACIÓN DE UN CIERTO
NÚMERO DE VEHÍCULOS A CIERTOS
CLIENTES
• VENTANAS DE TIEMPO
CLASIFICACIÓN DE
PROBLEMAS
• RUTEO DE UN ORIGEN A UN DESTINO
• RUTEO DE MÚLTIPLES ORÍGENES Y
DESTINOS
• RUTEO CON VARIOS PUNTOS Y EL
MISMO ORIGEN Y DESTINO (ROUNDTRIP)
• RUTEO Y PROGRAMACIÓN
UN ORIGEN A UN DESTINO
• PROBLEMA DEL CAMINO MÁS
CORTO.
• El camino mas corto de un origen a
diferentes destinos
• ALGORITMO: RUTA MÁS CORTA
(DIJKSTRA’S)
• EJEMPLO: DE PLANTA A AGENCIA(s)
EJEMPLO
Un camión debe ser enviado de Guadalajara
a Mérida. Se tienen diferentes trayectos
posibles pasando por ciudades intermedias.
El objetivo es minimizar la distancia
recorrida. Se conoce:
Las ciudades intermedias posibles
• La distancia entre cada ciudad posible
ORIGEN Y DESTINOS
MÚLTIPLES
• PROBLEMA DE FLUJO EN REDES, DE
TRANSPORTE, DE ASIGNACIÓN
• ALGORITMOS: FLUJO EN REDES,
PROGRAMACIÓN LINEAL ENTERA
Y/O BINARIA.
• EJEMPLO: ENTREGA DE PLANTAS A
AGENCIAS
EJEMPLO
• Una empresa tiene tres plantas desde las
cuales debe abastecer del mismo producto a
tres clientes .Se conoce la demanda de cada
cliente y la oferta de cada planta.
• Oferta: P1=400 ton, P2=700, P3=500
• Demanda: C1=600 ton, C2=500, C3=300
• Costo transportación:desde P1=4, 7, 6;
desde P2=5, 5, 5; desde P3=9, 5, 8 resp.
EJEMPLO
• LOS COSTOS DE TRANSPORTACIÓN
SON EN DÓLARES POR TONELADA
• SOLUCIÓN: 400 TON DE P1 A C1
200 TON DE P2 A C1
200 TON DE P2 A C2
300 TON DE P2 A C3
300 TON DE P3 A C2
COSTO=$6,600
ROUND-TRIP
• PROBLEMA DEL AGENTE VIAJERO
• UN CAMINO HAMILTONIANO
• PROBLEMA DIFÍCIL SI EL NÚMERO
DE PUNTOS A TOCAR ES GRANDE
• SE APLICAN HEURÍSTICAS:
– encontrar un camino inicial con el método del
vecino mas cercano
– mejorar el camino eliminando cruces
EJEMPLO
C
31
26 34
34 17
B
D
48
23
A
67
34
47
W
SOLUCIÓN: W ---D----C----B----A
RUTEO Y PROGRAMACIÓN
• RUTEO CON RESTRICCIONES
– En cada parada hay un volumen a cargar y/o
descargar
– Múltiples vehículos con capacidades distintas
– Tiempo total permitido limitado a horas
laborables
– Ventanas de tiempo para entrega en cada punto
– Carga en una ruta solo después de descarga
– Tiempo de descanso limitado en tiempo y
horario
ALGUNOS PRINCIPIOS
• Cargar vehículos con el volumen
correspondiente a los sitios mas cercanos
• Separar los sitios en cluster independientes
y programar cada cluster por separado
• Comenzar la ruta en el punto mas alejado
del origen al cluster
• Evitar cruces en la ruta
• La ruta mas eficiente es la que realiza el
vehículo de mayor carga
ALGUNOS
PRINCIPIOS
• La carga y la descarga debe mezclarse en
lugar de dejar la carga para el final
• Los puntos aislados de los cluster que
requieren poco volumen deben alcanzarse
con rutas alternativas en vehículos más
pequeños
• Evitar ventanas de tiempo muy restringidas
PROBLEMA DEL AGENTE
VIAJERO
• Sea G=[N,A,C] una red donde N es el
conjunto de nodos, A son los arcos y C=(cij)
es la matriz de costos (o distancia) de mover
un vehículo desde el nodo i al nodo j. El
problema del Agente Viajero consiste en
encontrar un ciclo Hamiltoniano en la red,
esto es, un ciclo que pasa por todos los
nodos exactamente una vez.
PROBLEMA DEL AGENTE
VIAJERO (PL entera)
(INEFICIENTE PARA PROBLEMAS GRANDES)
1 si el circuito pasa por el arco (i,j)
xij= { 0 en caso contrario
n= número de nodos
min  cij xij
s.a Cada ciudad j debe ser visitada una sola vez xij=1 para j=1,…,n
ij
Cada ciudad i debe dejarse una sola vez
xij=1 para i=1,…,n
ji
No debe haber ciclos en ningún subconjunto S de ciudades que incluya la
ciudad origen
[.] indica la cardinalidad del conjunto
.
xij [S]-1
i,jS
PROBLEMA DEL AGENTE
VIAJERO
• Las restricciones sobre no formación de ciclos son
del orden de 2n, pero pocas (n) son activas en el
óptimo lo que facilita un proceso iterativo. Ejemplo:
para 2000 ciudades se ha encontrado el óptimo con
esta formulación (varias horas de computadora)
• Una forma alternativa: ujui+1-(1-xij)n, j=2,..,n; ji
requiere del orden de n-1 restricciones. Pero es poco
eficiente para problemas grandes.
uj= el número secuencial de la ciudad j en el camino
Secuenciación de trabajos como
PAV
• El problema de secuenciar n trabajos en una
máquina puede plantearse como un
problema de agente viajero con n+1
ciudades; las ciudades i=1,…,n
corresponden a los trabajos i y la ciudad 0
es el inicio del trayecto. La distancia entre
las ciudades j y k es el tiempo de arranque
para j,k1. La distancia entre la ciudad 0 y k
es el tiempo de preparación para el primer
trabajo (k).
Secuenciación de trabajos como
PAV
• Minimizar el tiempo total de completar
todos los trabajos (makespan) es
equivalente a encontrar el mínimo ciclo en
la red
• Para estos problemas existen heurísticas
llamadas reglas de despacho o de
secuenciación, por ejemplo secuenciar
primero el trabajo con menor tiempo de
arranque. Esta regla es equivalente a la
heurística del vecino más cercano
PROBLEMA DEL AGENTE
VIAJERO
• En la práctica puede ser importante obtener una
buena solución en lugar del óptimo (una solución
en pocos segundos o minutos en lugar de una
mejor solución en horas)
• Puede usarse Branch and Bound para resolver el
problema. Se resuelve el problema relajado (sin la
condición de que no haya ciclos) que es un
problema de asignación.
PROBLEMA DEL AGENTE
VIAJERO
• Una solución factible para el problema puede
una solución óptima para el problema
asignación pero que contenga subciclos.
subciclo es un ciclo que no contenga todos
nodos de la red. En la red :
ser
de
Un
los
2
4
1
5
3
la solución x15=x21=x34=x43=x52=1 tiene dos
subciclos
PROBLEMA DEL AGENTE
VIAJERO
• Si es posible eliminar todas las soluciones
factibles del problema de asignación que
contengan subciclos y se resuelve este
problema de asignación, se obtendrá la
solución óptima del problema del agente
viajero. No es fácil hacerlo. Se puede hacer
con B and B ramificando de manera de
eliminar los subciclos. Por ejemplo en el
caso anterior ramificar con x34=0 o c34=M
PROBLEMA DEL AGENTE
VIAJERO
• Cuando no se puede encontrar la solución óptima en un
tiempo razonable usamos una Heurística:
• Una Heurística es un método que mejora la solución
obtenida pero no encuentra necesariamente el óptimo. En
problemas prácticos (por ej. secuenciación de operaciones
en máquinas controladas por computadoras) las heurísticas
pueden encontrar soluciones con un costo no mayor al 2%
del costo del óptimo.
• La eficiencia de una heurística se puede medir por:
– desempeño garantizado
– análisis probabilístico
– análisis empírico
PROBLEMA DEL AGENTE
VIAJERO
• Desempeño garantizado: es una cota del peor de los casos que
garantiza que tan lejos de la solución óptima podemos encontrarnos
• Análisis probabilístico: se supone que la localización de las ciudades
sigue una distribución de probabilidad conocida. Por ejemplo que las
ciudades son v.a. uniformemente distribuídas en un cuadrado unitario;
para cada heurística se calcula:
Longitud esperada del camino encontrado por la heurística
Longitud esperada del camino óptimo
Cuanto más cerca de 1 esté el cociente mejor es la heurística
• Análisis empírico: la solución obtenida por la heurística se compara
con la solución óptima de un número de problemas con solución
conocida
PROBLEMA DEL AGENTE
VIAJERO
Un proceso de solución típico para este problema sigue los siguientes
pasos: (hay varios algoritmos para cada paso)
• Crear un subciclo inicial
– Convex Hull
– Sweep (barrido)
– Vecino más cercano
• Insertar nodos restantes
– El más barato
– El más cercano
– El más lejano
• Mejorar el circuito
– Algoritmos de intercambio: 2-opt, 3-opt, etc
PROBLEMA DEL AGENTE
VIAJERO
Las heurísticas pueden consistir en:
• Construir un subciclo inicial y/o insertar
puntos restantes si es necesario
• Mejorar un ciclo existente
• Una combinación de los dos anteriores.
Procedimientos Compuestos
REGLAS MIOPES Y
BUSQUEDA LOCAL
Las heurísticas pueden también clasificarse en:
• REGLAS MIOPES: la solución se construye de manera
progresiva. En cada iteración se tiene una solución parcial
y se extiende esta solución seleccionando una de las
posibles opciones. Solo considera la mejor opción en el
paso siguiente sin tomar en cuenta lo ocurrido
antes.Ejemplo: la heurística del vecino más cercano
• BUSQUEDA LOCAL: busca una mejor solución en un
entorno de la solución actual. Ejemplo. 2-opt, 3-opt.
Recocido Simulado (Simulated Annealing), Búsqueda
Tabú (Tabu Search), Algoritmos Genéticos
Subciclo inicial: Convex Hull
• La envoltura convexa (Convex Hull) es el
convexo más pequeño que contiene a todos
los puntos
8
21
10
64
42 9
91
3
7
1
26
34
48
5
2
50
6
18
4
ALGORITMO INCREMENTAL
• Agrega puntos de uno en uno y actualiza la
envolvente.
• Si el nuevo punto está en el interior no hace
nada, en caso contrario se eliminan todos
los arcos que ese punto puede ver
• Agregar dos arcos que conecten el nuevo
punto con el resto de la envolvente
• Repetir el proceso hasta que no queden
puntos fuera
A
Gift Wrapping
• Encontrar el punto A (con la menor
coordenada en Y) como punto inicial
• Encontrar el punto B tal que todos los
puntos estén a la izquierda del arco AB (por
escaneo de todos los puntos)
• Encontrar C tal que todos los puntos estén a
la izquierda del arco BC
• Repetir el procedimiento
C
B
A
Reglas de Decisión
Los algoritmos anteriores requieren determinar si un punto
está a la izquierda de un arco o si un punto puede “ver” un
arco.
Las pruebas son iguales y se pueden implementar
calculando el área de un triángulo. El área del triángulo
PoP1P2 donde Po=(xo,yo), P1=(x1,y1), P2=(x2,y2) es
xo x1 x2 Si el área es distinta de cero P2 está a la
izquierda de PoP1 (GW); si el área es
1/2 yo y1 y2
distinta de cero y PoP1 es un arco de la
1 1 1
envoltura P2 puede ver a PoP1
Area positiva o negativa indica que nos
movemos en el sentido contrario al reloj
VECINO MÁS CERCANO
• Paso 1: Comenzar con cualquier nodo como
nodo inicial
• Paso 2: Encontrar el nodo no visitado más
cercano al último nodo visitado y agregarlo
al camino.
• Paso 3: Repetir el Paso 2 hasta que todos los
nodos de la red estén contenidos en el
camino. Unir el primer nodo con el último
visitado.
Desempeño Garantizado y
Número de Iteraciones
longitud
del circuito
longitud
con la heurística
del circuito
óptimo

1
2
log 2 ( n )  
El método es de orden O(n2), es decir el
número de iteraciones requeridas no es
mayor a n2
1
2
MÉTODOS PARA INSERTAR
PUNTOS LIBRES
Un método de inserción toma un subciclo
en la iteración k y determina cuál de los
restantes n-k nodos debe ser insertado
(paso de selección) en el circuito y entre
que nodos (paso de inserción).
• El más cercano
• El más barato
• El más alejado
EL MÁS CERCANO
• Paso 1: comenzar con un subgrafo consistiendo solo del
nodo i
• Paso 2: encontrar el nodo r tal que cir es mínimo y formar
el subciclo i-r-i.
• Paso 3: (Selección) a partir de un subciclo, encontrar el
nodo r que no está en el subciclo y que esté más cerca de
cualquier nodo j del subciclo (min crj).
• Paso 4: (Inserción) encontrar el arco (i,j) que minimiza
cir+crj-cij. Insertar r entre i y j
• Paso 5: Si todos los nodos han sido agregados parar, sino
regresar al Paso 3.
Desempeño Garantizado y
Número de Iteraciones
longitud
del camino con la heurística
longitud
 2
del camino óptimo
Número de iteraciones no mayor a n2.
EL MÁS BARATO
• Paso 1: comenzar con una subgráfica que contiene
solo el nodo i
• Paso 2: encontrar el nodo r tal que cir es mínimo y
formar el sub-ciclo i-r-i
• Paso 3: encontrar el arco(i,j) en el sub-ciclo que no
contenga a r tal que cir+crj-cij sea mínimo.
Insertar el nodo r entre i y j
• Tiene el mismo desempeño que el anterior y es del
orden
O ( n log ( n ))
2
2
EL MÁS LEJANO
• Paso 1: comenzar con un subgrafo que contenga solo el
nodo i
• Paso 2: encontrar el nodo r tal que cir se máximo y formar
el subciclo i-r-i.
• Paso 3: (Selección) dado un subciclo, encontrar el nodo r
que no esté en el subciclo y lo más alejado de cualquier
nodo en el subciclo (max crj).
• Paso 4:(Inserción) Encontrar el arco (i,j) en el subciclo que
minimice cir+crj-cij. Insertar r entre i y j
• Paso 5: si todos los nodos están en el ciclo parar, sino
repetir el paso 3.
Desempeño Garantizado y
Número de Iteraciones
lo n gitu d d el ciclo co n h u eristica
 2 ln ( n )  0 .1 6
lo n gitu d d el ciclo o p tim o
No más de n2 iteraciones
Método de ahorros de Clark and
Wrigth
• Paso 1: seleccionar cualquier nodo como el nodo central y
notarlo como nodo 1.
• Paso 2: Calcular “ahorros” sij=c1i+c1j-cij para i,j=2,3,....,n
• Paso 3: ordenar los ahorros del mayor al menor
• Paso 4: comenzar por el primero de la lista y moverse
hacia abajo formando subciclos más grandes ligando nodos
i y j apropiados
• Paso 5: repetir hasta que se tenga el ciclo.
Desempeño Garantizado y
Número de Iteraciones
• No se conoce “el peor de los casos”. Para
una versión modificada donde se selecciona
el mejor ahorro para el último nodo
agregado, el desempeño es tal que la razón
está acotada por una función lineal de
log2 (n). Es del orden O(n2 log2 (n))
Un ejemplo
• La localización de los puntos es la
siguiente:
#
X
Y
1
0
0
2
100
600
3
400
400
4
500
700
5
900
400
6
800
900
USAR
DISTANCIA
EUCLIDEANA
Descargar

No Slide Title