Algoritmo de colonia de hormigas para el problema de...
Transcript of Algoritmo de colonia de hormigas para el problema de...
![Page 1: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/1.jpg)
Algoritmo de colonia de hormigas para el problema de ruteo de vehículos con
dependencia temporalSantiago Balseiro
Irene LoiseauJuan Ramonet
![Page 2: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/2.jpg)
Hoja de Ruta
Introducción al Problema
Algoritmos
Interfaz Gráfica
Análisis del Caso Real
![Page 3: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/3.jpg)
Introducción al Problema
![Page 4: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/4.jpg)
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”
![Page 5: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/5.jpg)
VRP
• Grafo completo – G = (V, A)
• Clientes– di demanda
• Vehículos– C capacidad
• Arcos– cij costo
![Page 6: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/6.jpg)
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)
![Page 7: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/7.jpg)
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.
![Page 8: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/8.jpg)
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:
![Page 9: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/9.jpg)
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
![Page 10: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/10.jpg)
Algoritmos
![Page 11: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/11.jpg)
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.
![Page 12: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/12.jpg)
Colonia de Hormigas
![Page 13: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/13.jpg)
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
![Page 14: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/14.jpg)
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:
![Page 15: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/15.jpg)
Ant Colony System
![Page 16: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/16.jpg)
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ρτ ρ τ
Ψ← − ⋅ + ∀ ∈Ψ
![Page 17: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/17.jpg)
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
![Page 18: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/18.jpg)
Multiple Ant Colony System
Objetivo jerárquicominimizar: 1ero: cantidad de vehículos empleados
2do: tiempo (o distancia)
![Page 19: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/19.jpg)
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
![Page 20: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/20.jpg)
Heurísticas de Mejora
Or-opt
4-opt*
2-opt
![Page 21: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/21.jpg)
Heurísticas de Mejora
2-opt*
CROSS Exchange
Exchange2
Relocate2
![Page 22: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/22.jpg)
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
![Page 23: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/23.jpg)
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!
![Page 24: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/24.jpg)
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
![Page 25: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/25.jpg)
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
![Page 26: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/26.jpg)
Heurísticas de Inserción
• 3ra solución: Búsqueda Local + Inserción + MDL
![Page 27: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/27.jpg)
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%
![Page 28: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/28.jpg)
Interfaz Gráfica
![Page 29: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/29.jpg)
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
![Page 30: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/30.jpg)
Análisis del Caso Real
![Page 31: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/31.jpg)
Presentación
• Aplicaciones
![Page 32: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/32.jpg)
Presentación
• Importadora y distribuidora e de productos alimenticios
• Ubicada en Kendall al sur de Miami, Florida
Alimentos Australes
![Page 33: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/33.jpg)
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
![Page 34: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/34.jpg)
Recolección de Datos
• Clientes– Geocodificación– Horarios de Entrega
• Productos– Volúmenes– Pesos
• Vehículos– Consumos– Capacidades
• Distancias y Tiempos (GIS)
![Page 35: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/35.jpg)
Validación
• Finalizada la recolección de datos ¿Se puede utilizar la solución? No!
ValidaciónMacro
Micro
![Page 36: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/36.jpg)
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
![Page 37: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/37.jpg)
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
![Page 38: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/38.jpg)
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
![Page 39: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/39.jpg)
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
![Page 40: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/40.jpg)
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
![Page 41: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/41.jpg)
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
![Page 42: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/42.jpg)
Alternativas
RequisitosHIALEAH
$0.69 / ft2mes
DORAL$0.77 / ft2mes
MIRAMAR$0.79 / ft2mes
KENDALL$0.65 / ft2mes
![Page 43: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/43.jpg)
Evaluación
Procedimiento
Ordenes de Pedido
Software de Ruteo
RutasKilómetros
Horas
Gastos Simulados
Alternativas
![Page 44: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/44.jpg)
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
![Page 45: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/45.jpg)
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%
![Page 46: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/46.jpg)
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
![Page 47: Algoritmo de colonia de hormigas para el problema de …materias.fi.uba.ar/7114/Docs/TesisBalseiro.pdf · Algoritmo de colonia de hormigas para el problema de ruteo de vehículos](https://reader031.fdocumento.com/reader031/viewer/2022012921/5bb6936b09d3f2f06e8c00df/html5/thumbnails/47.jpg)
Fin