Problema de Localización de Plantas con Capacidades y Distancias

Problema de Localizacion de Plantascon Capacidades y Distancias Limitadas

Reunion de coordinacionOPTIMOS

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

Universitat Politecnica de CatalunyaHEC-Montreal

Mostoles, Octubre 2007

Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones

Esquema

Introduccion

Solucion vıa Busqueda Tabu

Cotas Inferiores

Resultados computacionales

Conclusiones

2/25


Localizacion Discreta

• Plantas → Costes fijos, capacidades

• Clientes → demandas

• pares → distancias/costes

3/25


Problema de localizacion capacidades y demanda indivisible

4/25


Problemas combinados localizacion-rutas (LRP)

5/25


Problema de localizacion de plantas con capacidades ydistancias limitadas

6/25


Problema de localizacion de plantas con capacidades ydistancias limitadas

7/25


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)

8/25


CDCPLP

Dados




planta-cliente;

decidir


de forma que



8/25


CDCPLP

Dados




planta-cliente;

decidir


de forma que



8/25


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.

9/25


(P) Min∑

j

fjyj + g∑j ,k

zjk +∑i ,j

cij

∑k

xijk

s.a.∑j ,k

xijk = 1 ∀i ∈ I

∑i

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

dixijk 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

10/25


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.

11/25


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

12/25


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.

13/25


Agregamos lımites de distancia recorrida

Nuevas variables:

yjk se abre la planta j con exactamente k vehıculos; j ∈ J; k ∈ K

xij el cliente i se atiende des de la planta j ; i ∈ I , j ∈ J

y nuevos coeficientes:

fjk = fj + k · g

14/25


(RP) Min∑j ,k

fjk yjk +∑i ,j

cij xij

s.a.∑

j

xij = 1 ∀i ∈ I

∑i

tij xij 6 `∑k

k yjk ∀j ∈ J∑i

di xij 6 bj

∑k

yjk ∀j ∈ J∑k

yjk 6 1 ∀j ∈ J

xij 6∑k

yjk ∀i ∈ I , j ∈ J

xij , yjk ∈ {0, 1} ∀i ∈ I , j ∈ J, k ∈ K

15/25


La relajacion lineal de (RP)

Proposicion Las cotas de las relajaciones LP de (P) y (RP)coinciden si reforzamos (P) con:

yj 6∑k

zjk ∀j∑k

xijk 6 yj , ∀i , j

16/25


Desigualdades validas para (RP)

Numero de plantas Si b(1) > b(2) > · · · > b(|J|):

∑j∈J

∑k∈K

yjk ≥ min

{s :

s∑r=1

b(r) >∑i∈I

di

}

Numero de vehıculos∑j∈J

∑k∈K

kyjk ≥⌈

1`

∑i∈I

minj∈J

tij

⌉Cover plantas Para ∈ J fijo y C1 ⊂ I con

∑i∈C1

di > b:∑i∈C1

xi ≤ (|C1| − 1)∑k∈K

yk

17/25


Desigualdades validas para (RP)Cover vehıculos (CV) Para ∈ J fijo and C2 ⊂ I , sea

k =

⌈1`

∑i∈C2

ti

⌉:

∑i∈C2

xi ≤ (|C2| − 1)

k−1∑s=1

ys + |C2||K |∑s=k

ys

Refuerzo Para s ∈ {1, . . . , k − 1}, seanns > max. n. de clientes de C2 alcanzables con s vehıculos.Son validas:

∑i∈C2

xi ≤k−1∑s=1

ns ys + |C2||K |∑s=k

ys

Separacion La familia original, mediante PLE.La version reforzada, heurısticamente a partir de laanterior.

18/25


Cortes de optimalidad para (RP)Para ∈ J fijo y C3 ⊆ I , si k 6 |K | es tal que

∑i∈C3

ti 6 k`existe una solucion optima de (PR) que cumple:

|K |∑s=k+1

ys 6∑i 6∈C3

xi

Refuerzo Sins 6 mın. num. clientes que habrıa que anadir a C3 para

justificar el uso de s vehıculos:

|K |∑s=k+1

nsys 6∑i 6∈C3

xij

Separacion La formulacion original, mediante PLE(Un problema por par (, k). No cualquier k) .La version reforzada, a partir de la anterior.

19/25


Experiencia computacional

• Instancias derivadas de SSCFLP1

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

• Caracterısticas:

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

1http://www-eio.upc.es/~elena/

20/25

http://www-eio.upc.es/~elena/


La relajacion linealInstancias con correlacion entre t y c

Desviaciones resp. al óptimo (C)

-12

-9

-6

-3

0

3

6

A B C D E FTabú

RP

LP

21/25


La relajacion lineal

Instancias sin correlacion entre t y c

Desviaciones resp. al óptimo (NC)

-12

-9

-6

-3

0

3

6

A B C D E FTabú

RP

LP

22/25


Modelo reforzado

Instancias con correlacion entre t y c

Mejora de la desviación respecto RP (C)

0.0

0.5

1.0

A B C D E F

CP

CV

CV+

{CP,CV}

{CP,CV+}

23/25


Modelo reforzado

Instancias sin correlacion entre t y c

Mejora de la desviación respecto RP (NC)

0.0

0.5

1.0

A B C D E F

CP

CV

CV+

{CP,CV}

{CP,CV+}

24/25


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 problemacomplejo

• Trabajo actual• Ampliacion de las familias de desigualdades y refuerzo de las

existentes.• Desarrollo de un algoritmo exacto.• Modelizacion alternativa.

25/25

Documents

Problema de Localización de Plantas con Capacidades y Distancias