Optimización de Rutas
de Distribución
Ing. Carlos L. Quintero Araújo, M.Sc.
Agenda
•
•
•
•
•
•
Introducción al caso
Problema teórico correspondiente: VRPTW
Métodos de solución disponibles
Supuestos utilizados
Algoritmo de solución
Resultados
2
Para Comenzar…
Examinadlo Todo; Retened lo bueno
1ª Tesalonicenses 5:21
3
Introducción al caso
• Operador logístico
• Distribución de productos congelados
• 535 puntos a atender en Bogotá y alrededores:
– Demanda conocida a las 5:00 p.m.
– Inicio de rutas: 4:30 a.m.
• No se visitan todos los puntos cada día
• Zonas prohibidas de circulación
• Flota de vehículos contratada
4
Problema Teórico Correspondiente:
VRPTW
• Vehicle Routing Problem
–
–
–
–
–
–
–
–
Flota de vehículos de capacidad W, limitada o no
Demandas q(i) para cada nodo i
No se tienen costos de ejecución de la tarea
Ruta: sucesión de clientes distintos entre 2 copias del
depósito
Entrega o colecta pero no ambas
NP-Difícil: TSP si la demanda total ≤ W
Métodos exactos: n=50
Instancias clásicas: Christofides
5
Problema Teórico Correspondiente:
VRPTW
• Vehicle Routing Problem
with Time Windows
– Cada cliente i tiene una
ventana de tiempo [ei,li] en
la cual debe ser atendido.
– Llegar antes del inicio de la
ventana implica un tiempo
de espera adicional.
– Llegar después de la
ventana genera soluciones
no factibles, salvo el caso
con ventanas suaves
(penalización).
Gráfica tomada de http://upload.wikimedia.org/
6
Problema Teórico Correspondiente:
VRPTW

min
C ij X
ij
( i,j) E
s.a

X
0 j

X
i0

X
ij
 1;  i  V\{ 0 }

X
ij
 1;  j  V\{ 0 }
X
ij
 m
j V
 m
iV
j V
iV

 1 ,  S  V\{ 0 }
i S,j V\S

qi  W
k
k
,  k  1 ,..,m
i S
ei  p i  li ,  i  V
p i  t ij  p j ,  ( i , j )  E
X
ij
 { 0 ,1 }
7
Métodos de solución disponibles
• Exactos: no es pertinente utilizarlos
– Branch & Bound
• Aproximados: sacrifican calidad de la solución por
tiempo de respuesta
– Heurísticas
– Metaheurísticas
8
Supuestos utilizados
• Distancias Manhattan. Levantamiento sobre
planos. Factor de ajuste: 1,44
• Sólo rutas para puntos en Bogotá
• Tiempos de servicio conocidos
• Velocidad diferencial por franja horaria: Vo=15km/h
• 2 zonas para movimiento de vehículos
9
Algoritmo de solución
• Función Objetivo: minimizar el tiempo de espera
• Solución Inicial:
– Construcción de cada ruta con VMC hasta completar
capacidad del camión.
• Metaheurística Búsqueda Tabú:
– Vecindarios 2-OPT intra e inter rutas
– Test de capacidad inter rutas
– Criterios de detención:
• # máximo de iteraciones: 1000
• # máximo de iteraciones sin mejora: 500
10
Algoritmo de solución
11
Resultados
• Código en C – Interfaz con excel
• Tiempo de solución: 5 seg
• Hoja de ruta para cada vehículo con estimados de
tiempo.
• Solución factible con el menor tiempo de espera
global.
12
¿Preguntas?
Descargar

SISTEMAS DE CONTROL Y PROGRAMACION DE …