Source: http://www.slideshare.net/vyepesp/tesis-optimizacin-vrptw-presentation
Timestamp: 2016-06-28 08:11:17+00:00

Document:
YEPES, V. (2002). Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW. Tesis Doctoral. Escuela Técnica Superior de Ingenieros de Caminos, Canales y Puertos. Universidad Politécnica de Valencia. 352 pp.	El propósito de la tesis consiste en la presentación de un modelo económico de distribución de mercancías que generalice los problemas de rutas sometidos a restricciones temporales de servicio “vehicle routing problem with time windows” (VRPTW) y de un conjunto de técnicas heurísticas y metaheurísticas capaces de resolverlo eficientemente. El trabajo sistematiza el conjunto de métodos de optimización heurística y establece el estado de la técnica en relación con los procedimientos empleados en la resolución del problema VRPTW y sus extensiones. Tras constatar ciertas discrepancias entre los modelos teóricos y los casos reales, la tesis define una función objetivo que mide la rentabilidad económica de las operaciones, y flexibiliza los horarios de entrega con penalizaciones que reflejen la insatisfacción de los clientes. Asimismo se contempla la posibilidad de contar con flotas heterogéneas de vehículos con costes fijos y variables diferenciados, así como capacidad de carga, velocidad y jornadas laborales distintas, y con la posibilidad del uso múltiple. Se incorpora la asimetría en la duración de los viajes, con tiempos de aproximación y de alejamiento que modulen el nivel de congestión por tráfico y otras dificultades de acceso. También es posible el ajuste de diferentes costes horarios en función de las horas extraordinarias y penalizaciones por ruptura en la llegada al depósito.	La tesis presenta una novedosa heurística de construcción secuencial de rutas basada en criterios económicos (HESECOR) capaz de resolver el modelo propuesto y que, en el caso del problema VRPTW básico, ha llegado en algunos casos a alcanzar la mejor solución publicada. También se han presentado un conjunto de metaheurísticas basadas en la búsqueda secuencial por entornos. Del análisis del comportamiento de dichas técnicas a los problemas básicos y generalizados presentados, se aportan conclusiones de interés práctico, tanto para la optimización heurística de los problemas combinatorios, como para la toma de decisiones en las empresas dedicadas al transporte.
Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW
económica aplicada a las redes
de transporte del tipo VRPTW
Dr. Josep R. Medina Folgado
>ValenciaSeptiembre2002
E.T.S. de Ingenieros de Caminos, Canales y Puertos >ValenciaSeptiembre2002
Optimización heurística aplicada a las redes de transporte del tiporedes
Optimización heurística económica económica aplicada a las VRPTW
Los problemas de optimización combinatoria 2
Modelos de distribución física y transporte 3
El problema de las rutas de vehículos con restricciones en el
horario de servicio: VRPTW 4
Definición del modelo de problema de rutas 5
Propuestas de estrategias de búsqueda secuencial por
entornos para la resolución del modelo VRPTW 6
Resumen y conclusiones 5
Globalización Incremento de las
de los mercados expectativas de los clientes
El problema de las Exigencia de productos
y servicios de calidad
inversión Mejora de servicio
por entornos
Resolución de problemas de transporte
conclusiones >ValenciaSeptiembre2002
Distribución física tiempo
Previsión de Ubicación fábricas
la demanda Servicios de y almacenes
reparación transporte
Tratamiento Recuperación y
por entornos mercancías tratamiento de
devueltas desperdicios
Gran variación de costes en las empresas
Costes logísticos: 4-32%. Ballou (1991)
Costes de transporte: 1/3-2/3 de los costes
logísticos. Ballou (1991)
76,5% del transporte de mercancías en
vehículos. Halse (1992)
Objetivos, contribución y estructura de la tesis
Los operadores del transporte
deben tomar decisiones
Procedimientos robustos, flexibles
y rápidos que proporcionen soluciones
Complejidad problemas
Modelo de distribución con restricciones
horarias y objetivo económico.
Ventanas temporales de flexibilidad
Incorporación de congestión, asimetrías,
jornadas laborables variables y
Taxonomía de estrategias para la
Heurística económica de construcción de
soluciones factibles (HESECOR).
Operadores específicos para resolver el
VRPTW y generalizaciones.
Conceptos de márgenes de viaje, esperas
ineludibles y ventanas temporales efectivas.
Nuevas metaheurísticas: perturbación de
la velocidad, exploración convergente,
búsqueda local adaptativa y otras.
escasos solución? Producción
Presupuesto descanso
Tiempo Otros
Optimización Incertidumbre
Realidad Modelo Validación
Predicción Decisión
Algoritmia y complejidad computacional
Complejidad problema de decisión
Polinómica Exponencial
en tiempo polinomial
P⊆NP
Técnicas de resolución de problemas de O.C.
“contiene los dos elementos que hacen atractivo un
problema a los matemáticos: planteamiento sencillo y
dificultad de resolución” (Garfinkel, 1985)
25 nodos en 5 siglos
20 nodos en 50 m
20 billones en 1 seg
Algoritmos específicos
“tailored algorithms” (Telfar, 1994)
Flexibilidad en el manejo de las
características propias del problema
Éxito regla 80/20 (Ho, 1994)
Métodos generales (Osman et al., 1996)
Emulan estrategias eficientes
en la Naturaleza e inteligencia artificial
Guían procedimientos específicos
(Goonatilake et al., 1995)
Inteligencia genéticos
Lógica borrosa biológica
local guiada estadística
local iterada Cristalización
descubren, se
adaptan, son
flexibles, explican
Algoritmos Genéticos (“GA”)
situaciones ... - transportes, redes de gas y electricidad
- procesos industriales, circuitos
- evaluación de créditos e inversiones
Redes Neuronales (“NN”)
- análisis de datos: diques, lluvias, transportes
- navegación, robótica, tráfico
- riesgo de inversiones, robo tarjetas
Cristalización Simulada (“SA”)
- análisis de ondas, optimización de NN
- transportes, diseño de circuitos integrados
- procesado de imagen, plantas de fabricación
Sistemas Borrosos (“FS”)
- enfoque automático de cámaras
- control de electrodomésticos, tráfico
Evaluación de las heurísticas y las metaheurísticas
Barr et al. (1995)
> Modelos de distribución
Características de los problemas de asignación y
Características de los problemas de rutas
optimización Número flota (4)
horarias (7)
la demanda (6)
280 años Localización de
la demanda (3)
búsqueda Precedencias (3) ruta (5)
vehículos (3) Velocidad
resolución del Función
Capacited VRP
VRP with Length Constraint
distribución DVRP
transporte VRPVRT
FSMVRP
El problema de las VRP with Variable Access Time
Vehicle Fleet Mix with
VFMVRC
vehículos con Stochastic VRP
restricciones Variable Unit Running Cost
en el horario VRP with Stochastic Travel
de servicio: Times
VRP with Deliveries and
VRPDB
modelo de VRP with Stochastic Demands
problema de Backhauls and Customers
Propuestas de Vehicles
Multi Compartment VRP
búsqueda VRP with Split Delivery
por entornos VRP with Time Windows
resolución del VRP with Soft Time Windows
VRPTW VRP with Time Deadlines
El problema VRPTW
Ruta empieza y acaba en base
Capacidad en vehículos
Pullen y Webb (1967)
Literatura temprana:
Knight y Hofer (1968)
Madsen (1976)
Proyecto GreenTrip:
40 años/investigador 1996-98
El problema VRPTW: aplicaciones reales
Los problemas de Distribución de piezas de repuesto
transporte Reparto de medicamentos a farmacias
Recogida de basuras, limpieza de calles, reparto de correo
secuencial Programación de actividades
Rutas de aviones espías, logística militar
Modelo matemático del problema VRPTW
∑∑ ∑ c x
Los problemas de ij ijk
=1 ∀i ∈ C
∑q ∑ x ≤ Q
∀k ∈ V
∑ x = 1 ∀k ∈V
∑x −∑x =0 ∀h ∈ C , ∀k ∈ V
modelo de ihk hjk
∑x =1 ∀k ∈ V
i , n +1, k
x (b + tij − b jk ) ≤ 0
∀i, j ∈ N , ∀k ∈ V
ei ≤ bik ≤ ui ∀i ∈ N , ∀k ∈ V
xijk ∈ {0,1} ∀i , j ∈ N , ∀k ∈ V
Larsen (1999)
Algoritmos de aproximación y heurísticas
Backer y Schaffer (1986)
van Ladeghem (1988)
Ioannou et al. (2001)
Povtin y Rousseau (1993)
Antes y Derigs(1995)
VRPTW Kontoravdis y Bard (1995)
Russell (1977); Savelsbergh (1986,1990,1992); Solomon et al.
(1988); Baker y Schaffer (1986); van Landeghem (1988); Thompson
y Psaraftis (1993); Potvin y Rousseau (1995)
Kontoravdis y Bard (1995); Antes y Derigs (1995); Russell (1995);
modelo Prosser y Shaw (1996); Cordone y Wolfler-Calvo (1997); Shaw
(1997, 1998); Caseau y Laburthe (1999); Bräysy (2001)
Heurística secuencial de Solomon (1987)
Cliente más alejado al depósito
Criterio de inicio de ruta
Cierre del inicio de servicio más temprano
Criterio de inserción de cliente
c 1 [i (u ), u , j (u )] = min c 1 (i p −1 , u , i p )
4 .2 )
p =1 ,..., m
c1 (i, u, j ) = α1c11 (i, u, j ) + α 2 c12 (i, u, j )
α1 + α 2 = 1, α1 ≥ 0, α 2 ≥ 0
c11 (i, u , j ) = d iu + d uj − Gd ij
c12 b ju − b j
c 2 [i (u *), u*, j (u *)] = max c 2 [i (u ), u , j (u )]
(Paso 2
4 .6 )
c2 (i, j , u ) = λ ⋅ d 0u − c1 (i, j , u )
λ=2; G=1; α1=1; α2=0
de T en T’
¿Criterio
de parada ? SI
NO SI Óptimo
¿Es T’ mejor Reemplazar
que T ? T por T’
Taxonomía de los operadores de cambio
Movimientos dentro de una ruta
1-swap*
1-relocate IOPT
Movimientos entre dos rutas
2-relocate 2-swap
transporte 2-opt**
Or-opt GENIUS
Reductor rutas
Intercambio vehículos
Movimientos entre tres rutas
Sustitución vehículos
para la 3-swap 3-relocate 3-opt* Cíclicas
Metaheurísticas VRPTW
Blanton et al. (1993)
Thangiah et al. (1994)
Thangiah (1995)
Carlton (1995)
Potvin et al. (1996)
De Backer et al. (1997)
Badeau et al. (1997)
Berger et al. (1998)
Chiang et al. (1996)
Bräysy (1999)
Tan et al. (2000)
Chiang et al. (1997)
Berger et al. (2001)
Schulze et al. (1999)
Bent et al. (2001)
Taillard et al. (1997)
Brandao (1999)
Cordeau et al. (2000)
Homberger et al. (1999)
GRASP Bräysy et al. (2000)
Kontoravdis et al. (1995)
Rochat et al. (1995)
Potvin et al. (1999)
Gambardella et al. (1999)
Schrimpf et al. (2000)
Búsqueda en entornos amplios
Kilby et al. (1999)
Shaw (1997, 1998)
De Backer et al (2000)
Ibaraki et al. (2001)
Rousseau et al. (2000)
Bräysy (2001a, 2001b)
Problemas de Solomon (1987)
TW ↓ TW ↑
Aleatorio R1 R2
Agrupado C1 C2
Mixto RC 1 RC 2
R1-R2 C1
56 problemas
Vehículos iguales
TW 25%,50%,75%,100%
C2 RC 1 - RC 2
Comportamiento de las estrategias de optimización
Solomon (1987) and
Potvin et al. (1993)
distribución 445
al.(1993)
rutas de Antes et al. (1995)
vehículos con 430
Cordone et al. (1998)
en el horario 425 Russell (1995)
Caseau et al. (1999)
VRPTW 420
Definición del 415
Bräysy (2001a)
problema de 410
secuencial Tiempo en minutos
Efectividad de distintos procedimientos heurísticos. Bräysy y Gendreau (2001)
optimización Garcia et al. (1994)
Kontoravdis et al.
430 (1995)
Potvin et al. (1996) Kilby et al. Brandão (1999)
425 Schulze et al. (1999)
Russell (1995) Bräysy (1999b)
vehículos con Gambardella et al.
420 Bräysy et al. (2000)
de servicio: Gehring et al. (1999) Taillard et al. (1997)
modelo de 410 Homberger et Homberger et
problema de Bräysy (2001b)
al.(1999) al. (1999)
rutas Bräysy (2001c)
Efectividad de distintos procedimientos. Bräysy y Gendreau (2001)
NTR D Referencia Estrategia
Bräysy (2001c) Búsq. en entornos ampliados
405 57710
405 57952 Algoritmos genéticos
406 57876 Algoritmos evolutivos
Gehring et al. (2001)
406 57641 Algoritmos genéticos
de servicio: Gambardella et al. (1999)
407 57525 Colonias de hormigas
407 57556 Búsqueda tabú
categóricamente que una familia de
metaheurísticas resuelve mejor que
otra un problema del tipo VRPTW .
Referencia Problema Nº Rutas NTR
Lau et al. (2001) R103 13 1175,67 462
Taillard et al. (1997) RC108 10 1139,82 417
Rochat et al. (1995) R105 14 1377,11 427
Rochat et al. (1995) R106 12 1252,03 427
Rousseau et al. (2000) R202 3 1191,70 412
Shaw (1997) R104 9 1007,31 -
Shaw (1997) R107 10 1104,66 -
Shaw (1997) RC107 11 1230,48 -
Shaw (1998) RC103 11 1261,67 -
Ibaraki et al. (2001) RC208 3 828,14 -
Un resultado excelente en la
optimización de un problema VRPTW
no implica que la estrategia sea
adecuada en casos semejantes.
¡Demasiadas justificaciones para acreditar
la eficacia de un procedimiento!
¿Se ha reducido el
¿Se ha mejorado
una marca vigente?
un conjunto de problemas?
¿Es mejor que otro ¿Se ha reducido el
procedimiento considerado número de rutas del
bueno? conjunto de problemas?
¿Se ha reducido
¿Es mejor que otro
resolución del banco de problemas
más moderno?
En procedimientos No se han publicado a
aleatorios no se han veces tiempos de
publicado a veces cálculo, y en otras
número de ensayos ni ocasiones no se conoce
estadísticos como la el hardware ni software.
dispersión y el valor
En ocasiones se han A veces se ha
definido metaheurísticas cambiado la función
como procedimientos objetivo adaptándola a
que extraen el mejor cada caso en distintas
resultados de varios fases del cálculo. Éstas
procedimientos. no han sido homogéneas
> Definición del modelo de
Ámbito de los problemas de distribución y transporte
Las ventanas temporales
Determinación del inicio del servicio y de los
márgenes de viaje
Acercamiento a los problemas reales
– Flota heterogénea: vehículos con diferente
antigüedad, capacidad de carga, costes fijos y de
operación, jornadas laborales...
– Función objetivo basada en criterios
económicos reales: tarifas y costes
– Presencia de horarios de servicio a los clientes
y de apertura del almacén
– Flexibilización en el horario de entrega o
recogida siempre que se penalicen
convenientemente las insatisfacciones del cliente
– Posibilidad de que los vehículos reinicien
nuevas rutas si no se sobrepasa la jornada
Ámbito de los problemas del modelo
AVRP Asymmetric VRP VRPVADT VRP with
CVRP Capacited VRP
VRPLC VRP with Length
VRPM VRP with
Multiple Use of
FSMVRP Fleet Size and Vehicles
Mix VRP VRPSDV VRP with Split
VFMVRC Vehicle Fleet Mix
VRPTW VRP with Time
VRPSTW VRP with Soft
VRPHE VRP with
Heterogeneous VRPTD VRP with Time
Fleet Deadlines
CTW (t ) = ∑ClTW (t )
C1TW (t ) = p e + c e ⋅ e sj − t
t < e sj
rutas de ,j j j
 eh − t 
C2, j (t ) = p j ⋅ hj s
en el horario e  e sj ≤ t < e h
e −e  j
j 
VRPTW j
C3, j (t ) = 0
e sj ≤ t ≤ u sj
rutas ku
 t − uh 
C4, j (t ) = p j ⋅ s j h 
u h < t ≤ u sj
u −u  j
j j
C5, j (t ) = rju + c u ⋅ t − u sj t > u sj
Modelo de penalización económica para franjas horarias flexibles
Inicio del servicio y asimetrías en los viajes
t (t ) = li (t ) + + a j (t )
bk (t ) = max esj , bik (t ) + si + tij (t ) ≤ u sj
e sj > b k (t )
e sj − bk (t )
w (t ) = 
e sj ≤ b k (t )
Definición del j
Inserción sucesiva de clientes
Inicio del servicio y márgenes de viaje
Inicio más temprano posible
b k,early (i ) (t ) = max e sj , eis + si + tij (t ) ≤ u sj
optimización k
Inicio más tardío posible
bk,last(i ) (t ) = min u sj , uis + si + tij (t ) ≥ e sj
El problema de las j
Ventana temporal efectiva
H ik, j max (t ) = b k,last (i ) (t ) − b k,early (i ) (t )
Margen del viaje
H ik, j (t ) = b k,last (i ) (t ) − b k (t )
Espera ineludible Distancia ficticia
[ ] d ij ,min (t ) = wij ,min (t ) ⋅ vk
wij ,min (t ) = max 0, e sj − b k,last (i ) (t )
Reducción del margen efectivo de los viajes
  N 5 TW
B = ∑  F j + q j Rq j + d 0 j Rd j + q j d 0 j Rqd j − ∑ V j , k Cv j ,k  − ∑∑ Cl , j (t j ) −
optimización N
j =1   j =0 l =1
− ∑ Chk (Tk ) + ∑ (Cr , k + Cdu k ⋅ d r ,k ) − ∑∑ Cl , j (t j )
k =1   j =0 l =1
I = ∑ (F j + q j Rq j + d 0 j Rd j + q j d 0 j Rqd j )
C = Ch + Cd + Ctw + Cv
Ch = ∑ Chk (Tk )
Chlk ⋅ t 0 ≤ t ≤ Hlk
Chk (t ) = Chlk ⋅ Hlk + Chek ⋅ t Hlk < t ≤ Hek
Chl ⋅ Hl + Che ⋅ He + Chp ⋅ t t > Hek
k k k k k
Cd = ∑ Cd k
Coste por distancia
Cd k = ∑ Cr ,k + Cduk ⋅ d r ,k
modelo de r =1
Ctw = ∑∑ ClTW (t j )
Penalizaciones TW
j = 0 l =1
para la VJ
Cv = ∑∑ v j ,k ⋅ Cv j ,k
> Propuestas de estrategias
de búsqueda secuencial por
Comportamiento de distintas estrategias en la
resolución del VRPTW con objetivo económico
Resolución de problemas de rutas VRPTW
HESECOR
Heurística de
secuencial de rutas
Mejora los criterios de Solomon (1987)
Generaliza problemas más complejos
Adopción de variables espacio-temporales
Criterios de rentabilidad económica
Amplios conjuntos de soluciones
Proximidad económica como criterio de inicio
La variable espacio-temporal
representa un criterio de cercanía entre
nodos mejor que su separación física.
Esperas por franjas horarias
Dificultades de aproximación
Potvin et al. (1996), Kilby et al. (1997),
por Lau et al. (2001) continúan
despreciando la componente temporal

References: resolución 
 resolución 

Resolución 
 resolución 

resolución 

resolución 

resolución 

resolución 

Resolución