Problema de Localizacion de Plantascon Capacidades y Distancias Limitadas

M. Albareda-Sambola, E. Fernandez, G. Laporte

Universitat Politecnica de CatalunyaHEC-Montreal

Reunion de coordinacionRed Espanola “Analisis y aplicaciones de decisiones sobre

localizacion de servicios y problemas relacionados”, Baeza 2007

Introduccion TS para CDCPLP Resultados Conclusiones

Esquema

Introduccion

Solucion vıa Busqueda Tabu

Resultados computacionales

Conclusiones

Introduccion TS para CDCPLP Resultados Conclusiones

Localizacion Discreta

• Plantas → Costes fijos, capacidades

• Clientes → demandas

• pares → distancias/costes

Introduccion TS para CDCPLP Resultados Conclusiones

Problema de localizacion capacidades y demanda indivisible

Introduccion TS para CDCPLP Resultados Conclusiones

Problemas combinados localizacion-rutas (LRP)

Introduccion TS para CDCPLP Resultados Conclusiones

En LRPs ...

Multiples decisiones:

1. Localizacion de plantas.

2. Asignacion de clientes a plantas.

3. Agrupamiento de clientes de una misma planta en vehıculos

4. Diseno de rutas

Introduccion TS para CDCPLP Resultados Conclusiones

Problema de localizacion de plantas con capacidades ydistancias limitadas

Introduccion TS para CDCPLP Resultados Conclusiones

Problema de localizacion de plantas con capacidades ydistancias limitadas

Introduccion TS para CDCPLP Resultados Conclusiones

CDCPLP

Dados

• un conjuto de localizaciones potenciales J, con costes fijos deapertura fj y capacidad bj ,

• una flota homogenea de vehıculos, con costes de operacion g ylımite de tiempo de viaje `,

• un conjunto de clientes I con demandas, di ,• costes de asignacion cij , y tiempos de viaje tij para cada par

planta-cliente;

decidir

• el conjunto de plantas a abrir,• la asignacion de clientes a plantas,• el uso de vehıculos

de forma que

• cada cliente sea atendido por un vehıculo,• se respeten las capacidades de las plantas,• ningun vehıculo exceda el lımite de tiempo de viaje, y• se minimice el coste total

(costes de apertura + uso de vehıculos + asignacion)

Introduccion TS para CDCPLP Resultados Conclusiones

CDCPLP

Dados

• un conjuto de localizaciones potenciales J, con costes fijos deapertura fj y capacidad bj ,

• una flota homogenea de vehıculos, con costes de operacion g ylımite de tiempo de viaje `,

• un conjunto de clientes I con demandas, di ,• costes de asignacion cij , y tiempos de viaje tij para cada par

planta-cliente;

decidir

• el conjunto de plantas a abrir,• la asignacion de clientes a plantas,• el uso de vehıculos

de forma que

• cada cliente sea atendido por un vehıculo,• se respeten las capacidades de las plantas,• ningun vehıculo exceda el lımite de tiempo de viaje, y• se minimice el coste total

(costes de apertura + uso de vehıculos + asignacion)

Introduccion TS para CDCPLP Resultados Conclusiones

CDCPLP

Dados

• un conjuto de localizaciones potenciales J, con costes fijos deapertura fj y capacidad bj ,

• una flota homogenea de vehıculos, con costes de operacion g ylımite de tiempo de viaje `,

• un conjunto de clientes I con demandas, di ,• costes de asignacion cij , y tiempos de viaje tij para cada par

planta-cliente;

decidir

• el conjunto de plantas a abrir,• la asignacion de clientes a plantas,• el uso de vehıculos

de forma que

• cada cliente sea atendido por un vehıculo,• se respeten las capacidades de las plantas,• ningun vehıculo exceda el lımite de tiempo de viaje, y• se minimice el coste total

(costes de apertura + uso de vehıculos + asignacion)

Introduccion TS para CDCPLP Resultados Conclusiones

Modelado

Variables:

yj se abre la planta j ; j ∈ J

zjk se usa el k-esimo vehıculo de la planta j ; j ∈ J, k ∈ K

xijk el k-esimo vehıculo de la planta j atiende al cliente i ;i ∈ I , j ∈ J, k ∈ K ,

donde |K | es una cota superior del numero de vehıculos a utilizaren cada planta.

Introduccion TS para CDCPLP Resultados Conclusiones

(P) Min∑

j

fjyj + g∑j ,k

zjk +∑i ,j

cij

∑k

xijk

s.t.∑j ,k

xijk = 1 ∀i ∈ I

∑i

tijxijk 6 `zjk ∀j ∈ J, k ∈ K∑i ,k

dijxijk 6 bjyj ∀j ∈ J

zjk 6 yj ∀j ∈ J, k ∈ K

xijk 6 zjk ∀i ∈ I , j ∈ J, k ∈ K

zjk 6 zj(k−1) ∀j ∈ J, k ∈ K\{1}xijk , yj , zjk ∈ {0, 1} ∀i ∈ I , j ∈ J, k ∈ K

Introduccion TS para CDCPLP Resultados Conclusiones

Buscando soluciones

La busqueda Tabu se ha aplicado con exito para diversosproblemas relacionados:

• Localizacion Discreta

• Asignacion generalizada

• Bin Packing

• Diseno de rutas

• Problemas combinados localizacion-rutas

Buenas espectativas para CDCPLP.

Introduccion TS para CDCPLP Resultados Conclusiones

Buscando soluciones

La busqueda Tabu se ha aplicado con exito para diversosproblemas relacionados:

• Localizacion Discreta

• Asignacion generalizada

• Bin Packing

• Diseno de rutas

• Problemas combinados localizacion-rutas

Buenas espectativas para CDCPLP.

Introduccion TS para CDCPLP Resultados Conclusiones

Caracterısticas Principales

• Inicializacion: Heurıstica Greedy

• Oscilacion etrategica: Permitimos infactibilidades respecto a

• Capacidad de las plantas

• Lımite de tiempo de viaje en los vehıculos

• Amplia gama de vecindarios

Introduccion TS para CDCPLP Resultados Conclusiones

Caracterısticas Principales

• Inicializacion: Heurıstica Greedy

• Oscilacion etrategica: Permitimos infactibilidades respecto a

• Capacidad de las plantas

• Lımite de tiempo de viaje en los vehıculos

• Amplia gama de vecindarios

Introduccion TS para CDCPLP Resultados Conclusiones

Caracterısticas Principales

• Inicializacion: Heurıstica Greedy

• Oscilacion etrategica: Permitimos infactibilidades respecto a

• Capacidad de las plantas

• Lımite de tiempo de viaje en los vehıculos

• Amplia gama de vecindarios

Introduccion TS para CDCPLP Resultados Conclusiones

Vecindarios

Distintos vecindarios para modificar:

• Conjunto de plantas abiertas

• Asignacion de plantas a clientes

• Uso de la flota de vehıculos

Jerarquıa de las decisiones

⇓

Jerarquıa en la exploracion de vecindarios

Introduccion TS para CDCPLP Resultados Conclusiones

Vecindarios

Distintos vecindarios para modificar:

• Conjunto de plantas abiertas

• Asignacion de plantas a clientes

• Uso de la flota de vehıculos

Jerarquıa de las decisiones

⇓

Jerarquıa en la exploracion de vecindarios

Introduccion TS para CDCPLP Resultados Conclusiones

Estrategia de la busqueda

• Pruebas con distintas alternativas

• Mejores resultados: Busqueda Tabu anidada

Conjunto de plantas abiertas

Asignación de plantas a clientes

Agrupación en vehículos

• En cada nivel, distintos vecindariosSeleccion segun el estatus de la solucion.

Introduccion TS para CDCPLP Resultados Conclusiones

Estrategia de la busqueda

• Pruebas con distintas alternativas

• Mejores resultados: Busqueda Tabu anidada

Conjunto de plantas abiertas

Asignación de plantas a clientes

Agrupación en vehículos

• En cada nivel, distintos vecindariosSeleccion segun el estatus de la solucion.

Introduccion TS para CDCPLP Resultados Conclusiones

Estrategia de la busqueda

• Pruebas con distintas alternativas

• Mejores resultados: Busqueda Tabu anidada

Conjunto de plantas abiertas

Asignación de plantas a clientes

Agrupación en vehículos

• En cada nivel, distintos vecindariosSeleccion segun el estatus de la solucion.

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional

• Instancias derivadas de SSCFLP1

• Informacion vehıculos (tij , ` y g) generada aleatoriamente.

• Dos grupos de experimentos:

1. Instancias 10x20. (6)

6 combinaciones (`, g)

etiq. A B C D E F

` 40 40 50 50 100 100g 50 100 80 150 150 300

tij ∈ [10, 50] con/sin correlacion con cij .−→ 72 instancias

2. Instancias 15x30 y 20x40: (12 + 7 )“C”, con correlacion entre c y t.

1www-eio.upc.es/personnel/homepages/elena/sscplp/

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional

• Instancias derivadas de SSCFLP1

• Informacion vehıculos (tij , ` y g) generada aleatoriamente.

• Dos grupos de experimentos:

1. Instancias 10x20. (6)

6 combinaciones (`, g)

etiq. A B C D E F

` 40 40 50 50 100 100g 50 100 80 150 150 300

tij ∈ [10, 50] con/sin correlacion con cij .−→ 72 instancias

2. Instancias 15x30 y 20x40: (12 + 7 )“C”, con correlacion entre c y t.

1www-eio.upc.es/personnel/homepages/elena/sscplp/

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional

• Instancias derivadas de SSCFLP1

• Informacion vehıculos (tij , ` y g) generada aleatoriamente.

• Dos grupos de experimentos:

1. Instancias 10x20. (6)

6 combinaciones (`, g)

etiq. A B C D E F

` 40 40 50 50 100 100g 50 100 80 150 150 300

tij ∈ [10, 50] con/sin correlacion con cij .−→ 72 instancias

2. Instancias 15x30 y 20x40: (12 + 7 )“C”, con correlacion entre c y t.

1www-eio.upc.es/personnel/homepages/elena/sscplp/

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional

• Instancias derivadas de SSCFLP1

• Informacion vehıculos (tij , ` y g) generada aleatoriamente.

• Dos grupos de experimentos:1. Instancias 10x20. (6)

6 combinaciones (`, g)

etiq. A B C D E F

` 40 40 50 50 100 100g 50 100 80 150 150 300

tij ∈ [10, 50] con/sin correlacion con cij .−→ 72 instancias

2. Instancias 15x30 y 20x40: (12 + 7 )“C”, con correlacion entre c y t.

1www-eio.upc.es/personnel/homepages/elena/sscplp/

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional

• Instancias derivadas de SSCFLP1

• Informacion vehıculos (tij , ` y g) generada aleatoriamente.

• Dos grupos de experimentos:1. Instancias 10x20. (6)

6 combinaciones (`, g)

etiq. A B C D E F

` 40 40 50 50 100 100g 50 100 80 150 150 300

tij ∈ [10, 50] con/sin correlacion con cij .−→ 72 instancias

2. Instancias 15x30 y 20x40: (12 + 7 )“C”, con correlacion entre c y t.

1www-eio.upc.es/personnel/homepages/elena/sscplp/

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional: Instancias 10x20

Instancias sin correlacion entre t y c

0

2

4

6

8

10

12

desv

iaci

on %

0

50

100

150

200

250

300

350

( l, g

)

tabu %dev g l

p1 p2 p3 p4 p5 p6

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional: Instancias 10x20

Instancias con correlacion entre t y c

0

2

4

6

8

10

12

desv

iaci

ón %

0

50

100

150

200

250

300

350

( l,g

)

tabu %dev g l

p1 p2 p3 p4 p5 p6

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional: Instancias 10x20

Instancias sin correlacion entre t y c ; conjunto de plantas

0

2

4

6

8

10

abiertas en sol. TS abiertas en ambas abiertas en sol. óptima

P1 P2 P3 P4 P5 P6

A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional: Instancias 10x20Instancias sin correlacion entre t y c . Distribucion costes

0%

25%

50%

75%

100%

apertura vehículos asignación

P1 P2 P3 P4 P5 P6

A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F A B C D E F

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional: Instancias 10x20

Instancias sin correlacion entre t y c . Tiempo TS

0

5

10

15

20

25

30

35

40

segu

ndos

0

50

100

150

200

250

300

350

( l, g

)

tiempo TS g l

p1 p2 p3 p4 p5 p6

Introduccion TS para CDCPLP Resultados Conclusiones

Experiencia computacional: Instancias grandes

Desviacion resp. mejor sol CPLEX (2h)

Desviaciones resp. a la solucion de CPLEX

-5

0

5

10

15

20instancias 15x30 instancias 20x40

Introduccion TS para CDCPLP Resultados Conclusiones

Conclusiones e investigacion futura

• Hemos introducido el Problema de Localizacion de Plantascon Capacidades y Distancias Limitadas, que esta a mitad decamino entre localizacion pura y localizacion-rutas, con elobjetivo de capturar la influencia de las consideraciones sobregestion de flotas en las decisiones sobre localizacion, pero sinincurrir en la complejidad del diseno de rutas.

• Aun sin el diseno de las rutas, se trata de un problema muycomplejo

• Trabajo actual• Estudio de modelos alternativos y refuerzo de sus cotas

asociadas.• Desarrollo de un algoritmo exacto.

Introduccion TS para CDCPLP Resultados Conclusiones

Conclusiones e investigacion futura

• Hemos introducido el Problema de Localizacion de Plantascon Capacidades y Distancias Limitadas, que esta a mitad decamino entre localizacion pura y localizacion-rutas, con elobjetivo de capturar la influencia de las consideraciones sobregestion de flotas en las decisiones sobre localizacion, pero sinincurrir en la complejidad del diseno de rutas.

• Aun sin el diseno de las rutas, se trata de un problema muycomplejo

• Trabajo actual• Estudio de modelos alternativos y refuerzo de sus cotas

asociadas.• Desarrollo de un algoritmo exacto.

Introduccion TS para CDCPLP Resultados Conclusiones

Conclusiones e investigacion futura

• Hemos introducido el Problema de Localizacion de Plantascon Capacidades y Distancias Limitadas, que esta a mitad decamino entre localizacion pura y localizacion-rutas, con elobjetivo de capturar la influencia de las consideraciones sobregestion de flotas en las decisiones sobre localizacion, pero sinincurrir en la complejidad del diseno de rutas.

• Aun sin el diseno de las rutas, se trata de un problema muycomplejo

• Trabajo actual• Estudio de modelos alternativos y refuerzo de sus cotas

asociadas.• Desarrollo de un algoritmo exacto.