VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización de

rutas con flotas heterogéneas VRPHESTW

J.R. Medina1 y V. Yepes2

1Dept. Ingeniería e Infraestructuras de los Transportes2Dept. Ingeniería de la Construcción y Proyectos de Ingeniería Civil

Universidad Politécnica de Valencia

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Problemas básicos de distribución

Traveling Salesman Problem

TSP

Traveling Salesman Problem

TSP

Multiple Traveling Salesman Problem

m-TSP

Multiple Traveling Salesman Problem

m-TSP

Vehicle Routing Problem

VRP

Vehicle Routing Problem

VRP

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Vehicle Routing Problem with Time Windows

Una visita por clienteRuta empieza y acaba en baseFlota homogéneaCapacidad en vehículosHorarios de entrega

Una visita por clienteRuta empieza y acaba en baseFlota homogéneaCapacidad en vehículosHorarios de entrega

ÁREA ECONÓMICA APLICACIÓNMaterias primas Combustible, gas natural, hormigónSector público Recogida de basuras, correo, etcSalud Reparto de medicamentos a farmaciasTransporte de alimentos Grandes superficies y comerciosDefensa Rutas de aviones espía, logística militar

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Complejidad computacional del VRPTW

VRP → NP-hard(Lenstra y Rinnooy Kan, 1981)

VRP → NP-hard(Lenstra y Rinnooy Kan, 1981)

VRPTW → NP-hardVRPTW → NP-hard

Solución viableTSPTW →

NP-completo(Savelsberg, 1985)

Solución viableTSPTW →

NP-completo(Savelsberg, 1985)

Con rutas fijasVRPTW →

NP-completo

Con rutas fijasVRPTW →

NP-completo

Poco probable

llegar a solución

óptima en

tiempo polinomial

Poco probable

llegar a solución

óptima en

tiempo polinomial

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

AVRP Asymmetric VRP

CVRP Capacited VRP

VRPLC VRP with Length Constraint

PVRP Period VRP

FRP Fixed Routes Problem

FSMVRP Fleet Size and Mix VRP

VFMVRC Vehicle Fleet Mix withVariable Unit Running Cost

VRPHE VRP with Heterogeneous Fleet

VRPB VRP with Backhauls

VRPDB VRP with Deliveries and Backhauls

PDP Pickup and Delivery Problem

MCVRP Multi Compartment VRP

min-maxVRP Min-max VRP

VRPPC VRP with Precedence Constraints

MDVRP Multiple Depot VRP

VRPSF VRP with Satellite Facilities

OVRP Open VRP

LVR Location VRP

DVRP Dynamic VRP

VRPVRT VRP with Variable Travel Times

VRPVADT VRP with Variable Access Time

SVRP Stochastic VRP

VRPST VRP with Stochastic TravelTimes

VRPSD VRP with Stochastic Demands

VRPSDC VRP with Stochastic Demands and Customers

VRPM VRP with Multiple Use of Vehicles

VRPSDV VRP with Split Delivery

VRPTW VRP with Time Windows

VRPSTW VRP with Soft Time Windows

VRPTD VRP with Time Deadlines

Modelos que se acercan a los problemas reales

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Universo de problemas reales de transporte

Universo de problemas reales de transporte

Universo de distintos

escenarios posibles para un

problema concreto

Universo de distintos

escenarios posibles para un

problema concreto

Universo de heurísticas y

metaheurísticasposibles

Universo de heurísticas y

metaheurísticasposibles

Espacio de soluciones factibles

Espacio de soluciones factibles

Mejor solución posible para un

tiempo de cálculo

Mejor solución posible para un

tiempo de cálculo

Un universo de problemas y de técnicas

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Acercamiento a los problemas reales VRPHESTW

– 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

VRP with heterogeneous fleet of vehicles and soft time windows

Ventanas de tiempo flexibles

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Acercamiento a los problemas reales VRPHESTW

VRP with heterogeneous fleet of vehicles and soft time windows–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

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

• Idea básica: en vez de buscar en el espacio de las soluciones (s), buscar en el espacio de los óptimos locales (s*).

ILS

S

S*

La búsqueda local iterada

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

La búsqueda local iterada

1. Construir una solución inicial s0

2. Aplicar un algoritmo de búsqueda que proporcione un óptimo local s*

3. Mientras no se encuentre un criterio de parada:

a. Perturbar la solución s* para transformarla en s’

b. Emplear el algoritmo de búsqueda para obtener s*’

c. Si s*’ supera el criterio de aceptación, considerar a s*’ como el siguiente s*

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Metaheurística propuesta

Construcción de solución inicial

Búsqueda de óptimo local

Perturbación¿Criterio de parada?

Fin

no

Generation Mechanism Based on GRASP

Local Search Using Variable Neighborhood

Search (VNS)

Ruin & RecreateAlgorithm

(Yepes y Medina, 2006)

si

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Búsqueda en entornos variables (VNS)

Variable Neighborhood Search (VNS)

• La estrategia para eludir un óptimo local consiste en cambiar de operador (Mladenovic y Hansen, 1997).

• Empleamos múltiples operadores seleccionados probabilísticamente (Yepes, 2002).

• La estrategia para eludir un óptimo local consiste en cambiar de operador (Mladenovic y Hansen, 1997).

• Empleamos múltiples operadores seleccionados probabilísticamente (Yepes, 2002).

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Destrucción y reconstrucción de soluciones

Perturbación:Destrucción y reconstrucción

de soluciones(Medina y Yepes, 2002)

Perturbación:Destrucción y reconstrucción

de soluciones(Medina y Yepes, 2002)

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Ejemplo de aplicación: problema HES-A

0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70 80 90 100

0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70 80 90 100

Modificación problemaR103 de Solomon (1987)

Modificación problemaR103 de Solomon (1987)

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Ejemplo de aplicación: problema HES-A

Mejor solución:Beneficio 184.699 (93.28% demanda satisfecha)

20 perturbaciones RR550.000 iteraciones/ciclo de perturbación

80000

100000

120000

140000

160000

180000

200000

1 10 100 1000

Tiempo de proceso (min)

Ben

efic

io RR=5; NF

RR=5; F

RR=10; NF

RR=10; F

NF→no factibleF→factible

RR→clientesdesconectados

50.000 iteraciones/ciclo

1.000 iteraciones/ciclo

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Ejemplo de aplicación: problema HES-A

100000

110000

120000

130000

140000

150000

0 20 40 60 80 100 120 140

Tiempo de proceso (min)

Ben

efic

io

RR=5RR=10

Mejor solución factible:Beneficio 143.454 (100% demanda satisfecha)

10 perturbaciones RR1050.000 iteraciones/ciclo de perturbación

Soluciones factibles

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Ejemplo de aplicación: problema HES-A

HES-A Mejor factible Mejor no factible

Recordalgoritmo del solterón

(Yepes y Medina, 2004)

Beneficio 143.454(84,22)

184.699(108,43)

170.335(100)

Distancia 1.339,60(108,99)

1.003,56(81,65)

1.229,13(100)

Vehículos 13(100)

12(92,31)

13(100)

Demanda 1458(100)

1360(93,28)

1458(100)

Tiempo relativo de

cálculo1 1.4 8

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Conclusiones

• Un aumento del número de perturbaciones y de las iteraciones en cada ciclo aumenta la calidad, pero con mayor tiempo de cálculo

• Buenos resultados con menor tiempo de cálculo frente otras heurísticas

• Soluciones de mayor beneficio pero sin satisfacer totalmente la demanda– Ventajosa la compensación al

cliente no satisfecho

VII Congreso de Transportes CIT 2006. Ciudad Real.

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización

J.R. Medina y V. Yepes

1.Introducción

2. El problema VRPHESTW

3. La búsqueda localiterada

4. Descripción de la metaheurística propuesta

5. Ejemplo de aplicación al problema VRPHESTW

6. Conclusiones

Búsqueda local iterada por reconstrucción de soluciones aplicada a la optimización de

rutas con flotas heterogéneas VRPHESTW

J.R. Medina1 y V. Yepes2

1Dept. Ingeniería e Infraestructuras de los Transportes2Dept. Ingeniería de la Construcción y Proyectos de Ingeniería Civil

Universidad Politécnica de Valencia