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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
Localizacion Discreta
• Plantas → Costes fijos, capacidades
• Clientes → demandas
• pares → distancias/costes
3/25
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
Problema de localizacion capacidades y demanda indivisible
4/25
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
Problemas combinados localizacion-rutas (LRP)
5/25
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
Problema de localizacion de plantas con capacidades ydistancias limitadas
6/25
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
Problema de localizacion de plantas con capacidades ydistancias limitadas
7/25
Introduccion TS para CDCPLP Cotas Inferiores 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)
8/25
Introduccion TS para CDCPLP Cotas Inferiores 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)
8/25
Introduccion TS para CDCPLP Cotas Inferiores 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)
8/25
Introduccion TS para CDCPLP Cotas Inferiores 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.
9/25
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
(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
Introduccion TS para CDCPLP Cotas Inferiores 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.
11/25
Introduccion TS para CDCPLP Cotas Inferiores 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
12/25
Introduccion TS para CDCPLP Cotas Inferiores 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.
13/25
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
(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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores Resultados Conclusiones
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
Introduccion TS para CDCPLP Cotas Inferiores 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 problemacomplejo
• Trabajo actual• Ampliacion de las familias de desigualdades y refuerzo de las
existentes.• Desarrollo de un algoritmo exacto.• Modelizacion alternativa.
25/25
Top Related