Algoritmo de colonia de hormigas para el problema de ruteo de vehículos con
dependencia temporalSantiago Balseiro
Irene LoiseauJuan Ramonet
Hoja de Ruta
Introducción al Problema
Algoritmos
Interfaz Gráfica
Análisis del Caso Real
Introducción al Problema
VRP
Académico
Económico
Interés
Problema de Ruteo de Vehículos (VRP):“Consiste en el servicio en un período de tiempo preestablecido de un conjunto de clientes mediante una flota de vehículos localizados en un depósito”
VRP
• Grafo completo – G = (V, A)
• Clientes– di demanda
• Vehículos– C capacidad
• Arcos– cij costo
TDVRPTW
• Problema de Ruteo de Vehículos con Ventanas de Tiempo y Dependencia Temporal
• Ventanas de Tiempo: [ai, bi]
• Tiempos de Servicio: si
• Objetivo jerárquico– minimizar 1ero: cantidad de vehículos empleados
2do: tiempo (o distancia)
TDVRPTW• Dependencia temporal
– ¿Es lo mismo ir al Centro por la mañana que por la tarde?
– Modelo• Dividimos el horizonte de tiempo en periodos.• Fijamos para cada arco una velocidad por periodo.
Formulación
• Variables de decisión– xij
m será 1 si algún vehículo recorre el arco (i,j) en el intervalo de tiempo m
– ti tiempo de partida del vehículo del nodo i– wi carga total entregada por el vehículo al llegar al nodo i.
(1)
( )1m
ijm Mi j
x j N− ∈∈Δ
= ∀ ∈∑ ∑
( )1m
ij Om Mi j
x j D− ∈∈Δ
≤ ∀ ∈∑ ∑
(2)
(2')
( )min
o E
mij i
i D m M i Dj i
B x t+∈ ∈ ∈∈Δ
⋅ +∑ ∑ ∑ ∑ Funcional Jerárquico
Un vehículo debe llegar a cada cliente
sujeto a:
Formulación
( ) ( )1 , ,mi m ijt T B x i j A m M− ≤ − ∀ ∈ ∈
( )1 , ,mi m ijt T x i j A m M−≥ ∀ ∈ ∈
i i i i ia s t b s i V+ ≤ ≤ + ∀ ∈
( )1 ,mi i j ij
m Mw d w B x i j A
∈
⎛ ⎞+ − ≤ − ∀ ∈⎜ ⎟⎝ ⎠
∑
( )i Ek iw C i D≤ ∀ ∈
(4)
(5)
(6)
(7)
(8)
(9)
( ) ( )1 , ,m mi j ij j ijt s c t B x i j A m M+ + − ≤ − ∀ ∈ ∈
Selección del período según el instante de partida del cliente
Restricciones de las ventanas de tiempo
Cálculo de la carga de los vehículos
Restricciones de capacidad
( )1m
ijm Mj i
x i N+ ∈∈Δ
= ∀ ∈∑ ∑
( )1m
ij Em Mj i
x i D+ ∈∈Δ
≤ ∀ ∈∑ ∑
(3)
(3')
Un vehículo debe partir de cada cliente
Cálculo de los tiempos parciales
Algoritmos
Algoritmos
• Solución Exacta? NP-Hard• Heurísticas
– Constructivas– Búsqueda Local
• Metaheurísticas– Tabu Search– Algoritmos Genéticos– Simulated Annealing– Colonia de Hormigas– etc.
Colonia de Hormigas
Ant Colony System• Hormigas agentes computacionales
Paso 1 Paso 4 Paso 8 Fin iteración
Hor
mig
a 1
Hor
mig
a 2
• k hormigas en paralelo k nuevas soluciones por iteración
Ant Colony System
¿Cómo escogen al próximo cliente?
si
0 en otro caso
ij iji
il ilij l Ni
j Np
α β
α β
τ ητ η
∈
⎧ ⋅∈⎪⎪ ⋅= ⎨
⎪⎪⎩
∑
• Vecinos que cumplen restricciones– Capacidad– Horarios de Entrega
• Cada arco (i, j) tiene asociado:– τij feromona– ηij visibilidad
• Calculan las probabilidades pij para cada destino j:
Ant Colony System
Ant Colony System
• Actualización global– Depositar feromona según la mejor solución
• Actualización local– La feromona se evapora cada vez que una
hormiga recorre un arco
( ) 01ij ijτ ξ τ ξ τ← − ⋅ + ⋅
( ) ( )1 , bsij ij bs i j
Cρτ ρ τ
Ψ← − ⋅ + ∀ ∈Ψ
Ant Colony System
ETA
PA
CO
NS
TRU
CTI
VA
Localizar hormigas en depósito
p = 1..Cantidad de Clientes
PA
SO
m = 1...Cantidad de Hormigas
HO
RM
IGA
Calcular probabilidades
Escoger próximo cliente y trasladarse
Evaporación local
ITE
RA
CIÓ
N
ETA
PA
AC
TUA
LIZA
CIÓ
N
k = 1..Cantidad de Iteraciones
Pos-inserción
Búsqueda Local
Comparar solución
Actualización Global
m = 1...Cantidad de Hormigas
HO
RM
IGA
Multiple Ant Colony System
Objetivo jerárquicominimizar: 1ero: cantidad de vehículos empleados
2do: tiempo (o distancia)
Heurísticas de Mejora• Vecindarios se exploran exhaustivamente• Buscar mejoras en el funcional• Clasificación
– de una ruta– de dos rutas o multiruta
Relocate1
Exchange1
Heurísticas de Mejora
Or-opt
4-opt*
2-opt
Heurísticas de Mejora
2-opt*
CROSS Exchange
Exchange2
Relocate2
Heurísticas de Mejora¿Porqué tantos operadores?
– ¿Son redundantes? Si!
Estrategia: aplicar primeros los de vecindario reducido y luego aquellos de vecindario extendido
01
23
01
23
Heurísticas de Inserción• Las hormigas generan soluciones con clientes sin
servir.
• 1era solución: Inserción directa
Si falla, no se pueden acomodar más clientes?
NO!
Heurísticas de Inserción
• 2da solución: Búsqueda Local + Inserción– Mismos operadores que heurística de mejora– Distinto objetivo
Si falla, no se pueden acomodar más clientes?
NO!
1
2
a
b
1
2
a
b
Heurísticas de Inserción
• Métrica MDL (minimun delay)– Cuantificar cuán difícil es insertar un cliente.– 3 causas que impiden servir un cliente
• Capacidad• Ventanas de tiempo del cliente• Ventanas de tiempo de un cliente posterior
– Evaluar numéricamente la penalidad por violar las restricciones
Heurísticas de Inserción
• 3ra solución: Búsqueda Local + Inserción + MDL
Resultados
• Instancias de Solomon, 1984– 56 problemas
• Comparación con mejores métodos a nivel mundial
0.0%1119.43.31119.23.3RC20.0%1384.411.51384.211.5RC10.1%952.52.7951.72.7R20.1%1210.611.91209.911.9R10.0%589.93.0589.93.0C20.0%828.410.0828.410.0C1
DistanciaVehículosDistanciaVehículosGap
MACS-TDVRPTWMejor ResultadoGrupo
– En 44 problemas encuentra la mejor solución– Diferencia promedio de 0.03%
Interfaz Gráfica
Interfaz Gráfica• Visualización 3D • Información de las
soluciones • Edición interactiva • Configuración del
algoritmo • Integración a un módulo
GIS
• Visualización 3D • Información de las
soluciones • Edición interactiva • Configuración del
algoritmo • Integración a un módulo
GIS
Análisis del Caso Real
Presentación
• Aplicaciones
Presentación
• Importadora y distribuidora e de productos alimenticios
• Ubicada en Kendall al sur de Miami, Florida
Alimentos Australes
Presentación
• Proyecto– Relocalización del
depósito
• Etapas– Recolección de datos– Validación– Elección de las
alternativas– Evaluación KENDALLKENDALL
Ubicación de los clientes
Recolección de Datos
• Clientes– Geocodificación– Horarios de Entrega
• Productos– Volúmenes– Pesos
• Vehículos– Consumos– Capacidades
• Distancias y Tiempos (GIS)
Validación
• Finalizada la recolección de datos ¿Se puede utilizar la solución? No!
ValidaciónMacro
Micro
Chófer Raul Ramirez
Fecha Apr/25/2007
Salida 7:25
Llegada 15:10
Orden Hora Llegada
Hora Salida
4 13:01 14:10
3 11:35 12:53
1 8:15 10:00
2 10:20 11:08
CLIENTE
BAY SUPERMARKET
FOOD GIANT # 3
LA MIA SUPERMARKET NW
PRICE CHOICE #5
Validación Micro
Estudio
Ejemplo de formulario entregado a los chóferes
Validación Micro
• Tiempos de Servicio
0
5
10
15
20
25
30
35
40
< 10 min 10 min -20 min
20 min -30 min
30 min -40 min
40 min -50 min
50 min -60 min
> 60 min
Validación Micro
• Ajuste de los Tiempos de Viaje– Tiempos GIS vs Tiempo Reales– 330 viajes medidos de 58000 viajes posibles!
• Tres efectos– Zona– Tránsito– Distancia
( ) ( ), , , ,GISij ij d ij i j t s i jt t f d x x f t x x= ⋅ ⋅
r r r r
Factor Distancia +
Zona
Factor Tránsito
Validación Micro
• Factor Distancia + Factor Zona
0
2
4
6
8
10
12
14
16
18
20
0 2 4 6 8 10 12 14
Distancia [km]
Fact
or
Factor de corrección en función de la distancia para el centro de Miami
Validación Micro
• Factor Tránsito• Periodos
– Mañana (9:00 AM)– Mediodía – Tarde (15:00 PM)
a
cb
d
N
S
EO
Eje Dolphin
Eje I-95
Validación Macro
Gastos Devengados
Ordenes de Pedido
Software de Ruteo
RutasKilómetros
Horas
Gastos Simulados
3691Tiempo [horas]
68626Distancia [km]
448Rutas
14 $/horaSalario0.247 $/kmCombustible0.022 $/kmGomas0.073 $/kmMantenimiento
Alternativas
RequisitosHIALEAH
$0.69 / ft2mes
DORAL$0.77 / ft2mes
MIRAMAR$0.79 / ft2mes
KENDALL$0.65 / ft2mes
Evaluación
Procedimiento
Ordenes de Pedido
Software de Ruteo
RutasKilómetros
Horas
Gastos Simulados
Alternativas
Evaluación
Miramar
Doral
Hialeah
Kendall
0 20,000 40,000 60,000 80,000Distancia [km]
Miramar
Doral
Hialeah
Kendall
0 1,000 2,000 3,000 4,000 5,000Tiempo [hs]
Miramar
Doral
Hialeah
Kendall
0 100 200 300 400 500Rutas
Evaluación
ActualKendall
Alquiler Depósito 63,360$ 66,240$ 5% 73,920$ 17% 75,840$ 20%Costos Transporte Combustible 16,506$ 12,528$ -24% 13,158$ -20% 12,016$ -27%
Mantenimiento 5,463$ 4,147$ -24% 4,355$ -20% 3,977$ -27%Gomas 1,626$ 1,234$ -24% 1,297$ -20% 1,184$ -27%
Salario Chóferes 60,699$ 54,827$ -10% 55,211$ -9% 54,858$ -10%
Total 147,655$ 138,977$ -6% 147,941$ 0% 147,876$ 0%
Alternativa AHialeah
Alternativa BDoral
Alternativa CMiramar
Gomas1%
Mantenimiento4%
Combustible11%
Transporte16%
Alquiler Depósito
43%
Salario Chóferes
41%
Conclusiones
• Conclusiones– Posible reducción del 6% en los costos
anuales
– Más próximos a los clientes
– Reducir tiempo en calle
– Mejorar calidad del servicio
– Estadísticas Detalladas
Fin