1
UN MODELO TEMPORAL DE LOCALIZACIÓN DE PLANTAS Y ALMACENES
CON EXISTENCIAS FINALES EN CADA PERIODO.
Au o es: Hinojosa Be gillos, Yolanda Pue o Albandoz, Jus o
[email p o ec ed] [email p o ec ed]
Dp o. de Economía Aplicada I. Dp o. de Es adís ica e I.O.
Uni e sidad de Se illa Uni e sidad de Se illa
Palab as cla e: Localización de plan as, p og amación en e a mix a, dual lag angiano,
in en a ios, heu ís ico.
Resumen:
En es e abajo se abo da un p oblema de localización de plan as de p oducción y cen os de
almacenamien o con obje o de sa is ace las demandas de un g upo de clien es. La dis ibución de p oduc os se
ealiza en dos e apas di e enciadas: En ío desde las plan as de p oducción a los di e en es almacenes y en ío
pos e io desde és os a los dis in os clien es. El es udio se ealiza a lo la go de un ho izon e empo al ini o
conside ando las exis encias inales en los almacenes como exis encias iniciales del pe íodo siguien e.
Asimismo, se supone que an o almacenes como plan as ienen capacidad limi ada. Nues o obje i o consis e en
de e mina la polí ica óp ima, en el ho izon e empo al ijado, pa a la ins alación (o en su caso, cie e) de
plan as y almacenes, de o ma que se sa is agan las demandas de los clien es, en cada pe íodo, a mínimo cos e.
En es e cos e se incluyen los cos es de ape u a (o en su caso, cie e), man enimien o y uncionamien o de
plan as y almacenes, así como, los cos es de anspo e y almacenamien o de exis encias inales.
El modelo es o mulado como un p oblema de p og amación en e a mix a. Pa a su esolución se p opone
una elajación lag angiana jun o con un p ocedimien o heu ís ico median e el cual se ob iene una buena
solución del p oblema o iginal.
1.-In oducción.
Son muchas las si uaciones eales en las que g andes compañías manu ac u an y
dis ibuyen di e sos ipos de p oduc os. Una de las p ime as cues iones que dichas
compañías han de plan ea se es dónde ubica las plan as de p oducción y/o los almacenes
desde donde dis ibui án sus p oduc os a los di e en es clien es con obje o de cub i las
demandas de és os a mínimo cos e. És e es el caso, po ci a algún ejemplo, de compañías
que ab ican y almacenan piezas de ecambio de coches, de aquellas que elabo an y
dis ibuyen ca álogos en e dis in as agencias y come cios o de las que, en gene al, p oducen
y dis ibuyen algún ipo de bien. Si las ubicaciones admisibles pa a las plan as de p oducción
y/o dis ibución son ini as y conocidas de an emano, nos en en amos con un p oblema
2
clásico den o de la Teo ía de Localización disc e a conocido como el p oblema de
localización de plan as. Es os p oblemas han sido ampliamen e es udiados y, en é minos
gene ales, pueden clasi ica se en:
1) P oblemas de localización de plan as simples sin es icciones de capacidad (SPLP);
2) P oblemas de localización de plan as con es icciones de capacidad (CPLP).
Aunque ambos ipos de p oblemas pueden se o mulados como p oblemas de
p og amación en e a-mix a ( éase, po ejemplo, Aikens (1985)), no a a se posible, en
gene al, ob ene su solución exac a en iempo polinomial po pe enece a la clase de
p oblemas conocidos como p oblemas NP-du os ( éase K a up y P uzan (1983) quienes
p oba on que incluso el SPLP es un p oblema NP-du o).
Se han es udiado muchas ex ensiones de es os p oblemas ( éase, po ejemplo, Aikens
(1985), D ezne (1995) o Daskin (1995)) donde se puede encon a una buena ecopilación
de es os p oblemas y de sus ex ensiones). Podemos esal a dos de ellas, la p ime a consis e
en in oduci aspec os empo ales en el modelo. En es e caso las a iables de decisión no son
sólo las que hacen e e encia a la plani icación del anspo e y localización de plan as, sino
ambién al pe íodo de iempo en que las plan as se ponen en uncionamien o ( éase po ej.,
Wa szawski's (1973), Van Roy y E lenko e (1982) o más ecien emen e Cha dai e e al.
(1996) ). En la segunda se supone la exis encia de una cie a es uc u a en el esquema de
anspo e (p oblemas mul ie ápicos), es deci , el anspo e desde las plan as has a los
clien es se ealiza en dos e apas bien di e enciadas. Es os modelos ha sido escasamen e
es udiados en la li e a u a clásica sob e localización ( éase Kau man e al. (1977) o Tcha y
Lee (1984) ), aunque en la úl ima década han apa ecido impo an es abajos ( éase Daskin
(1995) , Ma ín (1996), C ainic y Delo me (1993), Ba os y Labbé (1994) o Pi kul y
Jaya aman (1996)). La p incipal peculia idad de es os modelos es que los p oduc os son
en iados desde las plan as de p oducción a los almacenes pa a pos e io men e se
anspo ados desde es os a los di e en es clien es. Po an o, el p oblema de decisión consis e
en localiza las plan as y almacenes y en de e mina la can idad de los di e en es p oduc os
que se á en iada desde cada plan a en uncionamien o a cada almacén abie o y desde és e a
cada clien e. Adicionalmen e, en ambas ex ensiones se puede conside a o no es icciones
sob e capacidad.
El ma co más na u al pa a es os p oblemas es la combinación de ambas ex ensiones, es
deci , la conside ación conjun a de aspec os mul ie ápicos y mul i empo ales. Es a
combinación ha sido es udiada po p ime a ez po Hinojosa, Pue o y Fe nández (2000)
quienes conside an un modelo bie ápico en el que los p oduc os son en iados desde las
3
plan as de p oducción a un conjun o de almacenes pa a pos e io men e se dis ibuidos desde
és os a los di e en es clien es. Adicionalmen e, ealizan el es udio a a és de un ho izon e
empo al ini o en el que se pe mi e an o la ape u a de nue as plan as como el cie e de las
ya exis en es. Sin emba go, es e modelo no conside a la exis encia de s ock al inal de cada
empo ada lo cual iene sen ido cuando se abaje con p oduc os pe ecede os o de empo ada
pe o, deja de ene lo cuando se abaja con p oduc os que pe manecen de una empo ada a
o a como pod ía se el caso de las piezas de ecambio de coches.
El modelo que abo damos en el p esen e abajo es una ex ensión del ci ado
an e io men e en el que las exis encias al inal de cada empo ada se man ienen almacenadas
en las plan as de dis ibución o almacenes has a el inicio de la empo ada siguien e,
conside ándose en es a como exis encias iniciales. En odo momen o se supone que an o
almacenes como plan as de p oducción ienen capacidad limi ada, po lo que an o la
can idad p oducida como la almacenada ha de es a suje a a es a es icción. Nues o obje i o
es de e mina en el ho izon e empo al ijado, la polí ica óp ima pa a la ins alación (o en su
caso, cie e) de plan as y almacenes así como pa a la dis ibución de p oduc os. Po polí ica
óp ima se en iende aquella que pe mi a sa is ace en cada pe íodo las demandas de odos los
clien es a mínimo cos e. En es e cos e se incluyen los cos es de ape u a (o en su caso,
cie e), man enimien o y uncionamien o de plan as y almacenes, así como, los cos es de
anspo e y los cos es de almacenamien o de las exis encias al inal de cada pe íodo. Es e
modelo es un p oblema de p og amación en e a mix a con un ele ado núme o de a iables
(po ejemplo, un p oblema con 100 clien es, 15 almacenes, 5 plan as, 2 ipos di e en es de
p oduc os y 5 pe iodos de iempo iene 15970 a iables y 1334 es icciones). Es o hace que
el iempo compu acional eque ido pa a su esolución exac a po aco ación ami icación sea
p ohibi i o. Po an o se p opone un mé odo al e na i o pa a la ob ención de soluciones
ap oximadas que inco po a un mé odo dual ascenden e aplicado a una elajación lag angiana
del p oblema jun o con un p ocedimien o heu ís ico.
El abajo queda o ganizado como sigue. En la sección 2 se p esen a la o mulación
ma emá ica del modelo como un p oblema de p og amación en e a mix a. En la sección 3
p oponemos una elajación Lag angiana del mismo, la cual puede se esuel a de o ma
óp ima as la esolución de un núme o ini o de p oblemas lineales jun o con la aplicación de
un algo i mo del subg adien e. En la sección 4 se desa olla un p ocedimien o heu ís ico pa a
la ob ención de una solución ac ible de nues o modelo. En la quin a sección se p esen an
algunas conclusiones.
4
2.-El modelo.
En es e modelo se abo da un p oblema de localización de plan as con obje o de diseña y
plani ica un sis ema de dis ibución a lo la go de un ho izon e empo al en el que se ija el
es udio del mismo. Pa a es e ipo de p oblemas suele se usual conside a meses o
empo adas como longi ud de cada pe íodo de iempo. Se asume que los conjun os de
clien es y p oduc os, así como las posibles ubicaciones pa a las plan as de p oducción y
almacenes es án ijos y son conocidos de an emano, po lo que no cambia án a lo la go del
ci ado ho izon e. Se deno a á po :
•
1,...,In=
{}
al conjun o de clien es a los que se e e encia á po
iI∈
.
•
1,...,Lq=
{}
al conjun o de los di e en es ipos de p oduc os, e e enciados po
lL∈
.
•
1,...,Jm=
{}
al conjun o de posibles ubicaciones pa a los almacenes, e e enciados
po
jJ∈
.
•
1,...,Kp
=
{}
al conjun o de posibles ubicaciones pa a las plan as de p oducción,
e e enciadas po
kK∈
.
Se conside a que an o las plan as de p oducción como los almacenes ienen
una capacidad limi ada, así se deno a á po :
•
j
W la capacidad del almacén
j
en el pe íodo de iempo
,
•
k
C la capacidad de la plan a k en el pe íodo de iempo
y po
•
il
d la demanda que el clien e
i
iene del p oduc o l du an e el pe íodo
.
Al comienzo del p ime pe íodo de iempo se supone que exis e un subconjun o c
K
den o del conjun o o al de posibles ubicaciones pa a plan as donde ya exis en plan as en
uncionamien o. És as se pueden ce a al inal de cualquie pe íodo del ho izon e empo al,
pe o una ez ce adas no pueden ol e a se abie as. Se deno a á po o
K el conjun o de
posibles ubicaciones donde no exis en plan as en uncionamien o an es del comienzo del
p ime pe íodo de iempo. Es as plan as pod án se abie as al comienzo de cualquie pe íodo
de iempo, pe o una ez abie as ya no pod án ol e a se ce adas den o del ho izon e
empo al conside ado. En los mismos é minos se supone la exis encia de subconjun os c
Jy
o
J pa a los almacenes. Es a hipó esis es bas an e azonable. En muchas ocasiones el hecho
de ce a y ab i sin que exis a una con inuidad ae consigo una pé dida de me cado pues o
que los consumido es equie en una cie a egula idad pa a man ene se como clien es
5
habi uales de una de e minada i ma o come cio. Es o nos pe mi e de ini las a iables de
decisión del p oblema como:
• ,
1si el almacen es abie o al comienzo del pe iodo
0en o o caso
oj
j
jJ z 
∀∈∀=


• ,
1si el almacen es ce ado al inal del pe iodo
1 0en o o caso
cj
j
jJ Tz

∀∈∀<−=


• ,
1si el almacen se man iene abie o du an e odo el ho izon e empo al
0en o o caso
T
cj
j
jJz 
∀∈=


•
k
ζ
es de inido de o ma análoga pa a el conjun o de plan as.
• :
ijl
x= acción (con espec o a
il
d) de p oduc o len iado desde el almacén
j
al
clien e
i
du an e el pe íodo
.
• :
jkl
y= acción (con espec o a
j
W) de p oduc o len iado desde la plan a k al
almacén
j
du an e el pe íodo
.
• :
jl
I=s ock de p oduc o len el almacén
j
al inal del pe íodo
.
Asimismo, pa a asegu a una cobe u a mínima de la demanda se obliga a que haya un
mínimo núme o de plan as y almacenes abie os al comienzo y al inal del ho izon e
empo al. Se deno a á po 1,T
NWNW ( espec i amen e 1,T
NPNP ) al mínimo núme o de
almacenes y plan as espec i amen e que han de es a abie os al comienzo del p ime
pe íodo y al inal del úl imo.
Po úl imo se supone un es uc u a de cos es que incluye cos es de ape u a (o en su caso,
cie e), man enimien o y uncionamien o de plan as y almacenes, así como, cos es de
anspo e y cos es de almacenamien o de las exis encias al inal de cada pe íodo. Es os
cos es se deno a án po :
•
, :
oj
jJF
∀∈=
cos e o al po ab i el almacén
j
al comienzo del pe íodo
.
Es e cos e incluye el cos e de ape u a al comienzo del pe íodo
más el cos e de
man enimien o y uncionamien o del almacén
j
desde el pe íodo
has a el inal del
ho izon e empo al
•
, 1 :
cj
jJ TF
∀∈∀<−=
cos e o al po ce a el almacén
j
al inal del pe íodo
.

6
Es e cos e incluye el cos e de cie e al inal del pe íodo
más el cos e de
man enimien o y uncionamien o del almacén
j
desde el comienzo del ho izon e
empo al has a el inal del pe íodo
.
•
, :
T
cj
jJF
∀∈=
cos e o al po man ene abie o el almacén
j
du an e odo el
ho izon e empo al.
•
k
G es de inido de o ma análoga pa a el conjun o de plan as.
• :
jkl
b=cos e po unidad de p oduc o len iado desde la plan a k al almacén
j
du an e
el pe íodo
.
• :
ijl
c=cos e po unidad de p oduc o len iado desde el almacén
j
al clien e
i
du an e
el pe íodo
.
• :
jl
p=cos e po unidad de exis encia de p oduc o l en el almacén
j
al inal del
pe íodo
.
Po simpli icación de no ación se conside a á:
•
}
{
}
{
1,...,si
,...,si
o
j
c
jJ
T
TjJ
∈

=∈


y análogamen e k
T pa a las plan as.
De acue do con las hipó esis y no ación desc i as, la o mulación ma emá ica del
p oblema es la siguien e:
11111111111
1111
() min (,,,):
+
qpqq
TnmTmTm
ijlijliljkljkljjljl
ijl jkl jl
p
TmT
jjkk
j k
P xyzcxdbyWpI
FzG
ζ
ζ
===========
====
=++
+
∑∑∑∑∑∑∑∑∑∑∑
∑∑∑∑
suje o a:
1
111
1 , , (1)
,
j
m
ijl
j
qq
n
ilijljljj
ill T
xil
dxIWzj
=
===∈
≥∀∀∀
+≤∀∀
∑
∑∑∑∑
1
1
1
1
1
(2)
, 1,...,1 (3)
j
q
jljj
l T
jjkljl
k
IWzj T
WyI
+
+
=∈
−
=
≤∀∀=−
+
∑∑
1
11
, , (4)
, (5)
k
pn
ilijljl
i
qm
jjklkk
jl T
dxIjl
WyCk
ζ
=
==∈
=+∀∀∀
≤∀∀
∑∑
∑∑∑
7
11
11
11
; (6)
;
occo
TT
T T
jjjj
jJjJ jJjJ
T T
kkkk
zzNWzzNW
NPNP
ζζζζ
∈∈=∈∈=
+≥+≥
+≥+≥
∑∑∑∑∑∑
11
11
1
(7)
1 ; 1 (8)
1 ;
occo
TT
kKkK kKkK
TT
jcjo
T
kc
zjJzjJ
kK
ζ
∈∈=∈∈=
==
=
=∀∈≤∀∈
=∀∈
∑∑∑∑∑∑
∑∑
∑1
0
1 (9)
0 ,; 0 ,, 1,...,1 (10)
,0
T
ko
T
jljljl
ijljkl
kK
IIjlIjl T
xyi
ζ
=
≤∀∈
==∀≥∀=−
≥∀
∑
}
{
,,,,; ,0,1 ,, (11)
jk
jkl zjk
ζ
∈∀
Las es icciones (1) obligan a que se sa is aga la demanda que cada clien e
i
iene de
cada uno de los p oduc os l en cada pe íodo de iempo
. Es a demanda ha de se sa is echa
po los di e en es almacenes. Las es icciones (2), (3) y (5) hacen e e encia a las
limi aciones de capacidad. Las es icciones (2) obligan a que el núme o o al de unidades de
odos los p oduc os en iados desde el almacén
j
más las exis encias al inal del pe íodo
sean in e io o igual a la capacidad de dicho almacén en el pe íodo
. Las es icciones (5)
son análogas a las es icciones (2) pe o e e idas a plan as en las que no se conside a que
haya exis encias inales. Po úl imo, las es icciones (3) obligan a que la can idad de
exis encias en el almacén
j
al inal del pe íodo
sea meno o igual que la capacidad de
dicho almacén en el pe íodo siguien e, pa a que puedan se conside adas en és e úl imo como
exis encias iniciales. Las es icciones (4) son ecuaciones de balance de lujo pa a cada
almacén, cada p oduc o y cada pe íodo de iempo. Nó ese que la can idad de p oduc o l
en iada desde las plan as al almacén
j
en el pe íodo
más las exis encias al inal del
pe íodo an e io ha de se igual a la can idad de p oduc o l en iada desde dicho almacén a
los dis in os clien es más las exis encias al inal del p esen e pe íodo. Las es icciones (6) y
(7) es ablecen el mínimo núme o de almacenes y plan as que han de es a abie as al
comienzo y al inal del ho izon e empo al. Las es icciones (8) y (9) hacen e e encia a las
ca ac e ís icas an e io men e señaladas de los conjun os
oc
JJJ
=Uy K
oc
KK
=U. Las
es icciones (10) obligan a que las exis encias al comienzo y al inal del ho izon e empo al
algan 0. Po úl imo, las es icciones (11) es ablecen las a iables con inuas y bina ias del
p oblema.
8
El p oblema
)(P
es un p oblema de p og amación en e a-mix a, po lo que su esolución
median e un algo i mo exac o es compu acionalmen e in a able al a a se de un p oblema de
los clasi icados como NP-du os. Po es a azón p oponemos un mé odo heu ís ico que se
basa en : 1) ealiza una elajación lag angiana del p oblema, ob eniendo la solución del
p oblema dual lag angiano median e el algo i mo del subg adien e y 2) usa un
p ocedimien o “ad hoc” pa a ob ene una buena solución ac ible del p oblema
)(P
a pa i
de las soluciones de los p oblemas elajados.
3.- Descomposición del p oblema. Ob ención de co as in e io es.
En es a sección se desc ibi á some amen e la écnica u ilizada pa a la ob ención de co as
in e io es de la solución óp ima del p oblema
)(P
. Es a écnica, conocida como elajación
lag angiana, es bas an e usual en la esolución ap oximada de p oblemas de p og amación
en e a-mix a ( éase Fishe (1981) pa a una desc ipción de allada de la misma) y es usada
habi ualmen e en abajos elacionados con la localización de plan as ( éase Ba os y Labbé
(1994), Beasley (1993), C ainic y Delo me (1993), E lenko e (1978), Guigna d e al. (1990)
o Pi kul e al. (1996)). La elajación lag angiana nos pe mi i á, como ya se ha mencionado,
ob ene una co a in e io de la solución óp ima de nues o p oblema.
En nues o p oblema p oponemos elaja las es icciones que hacen e e encia a la
sa is acción de las demandas (1), a las que se les asocia unos mul iplicado es 0
il
µ
≥, con
obje o de inco po a las a la unción obje i o. De igual o ma, se elaja án las ecuaciones de
balance de lujo (4) a las que se le asocia án unos mul iplicado es
jl
λ
∈ℜ. Es o da á luga al
p oblema elajado, que deno a emos po
))
,
((
µ
λ
LR
, donde es as es icciones no apa ecen
como ales, sino inco po adas a la unción obje i o po medio de los mul iplicado es (pa a
más de alle, éase Hinojosa, Pue o y Fe nández (2000) en el que se ealiza una elajación
del mismo ipo pa a un p oblema simila ).
Deno emos po
)(A
el alo de la unción obje i o del p oblema
)(A
. Se p ueba que el
p oblema
))
,
((
µ
λ
LR
en el que ya no apa ecen las es icciones (1) y (4) puede se
descompues o en dos subp oblemas, a los que deno a emos po
))
,
(1(
µ
λ
LR
y
))
,
(2(
µ
λ
LR
espec i amen e. . El p oblema
))
,
(1(
µ
λ
LR
sólo a ec a a los almacenes y el p oblema
))
,
(2(
µ
λ
LR
a las plan as. Es os dos p oblemas pueden se esuel os de o ma independien e,
po lo que sus soluciones espec i as se án usadas pa a esol e el p oblema
elajado
))
,
((
µ
λ
LR
, ob eniéndose que
((,))(1(,))(2(,)) LR LR LR
λµλµλµ
=+
.
9
Pa a esol e el p oblema
))
,
(1(
µ
λ
LR
, se p ueba que puede se a su ez, descompues o en
m
subp oblemas independien es (que deno a emos po
1(,)
j
LR
λµ
), uno po cada almacén y
cada uno de és os en
T
subp oblemas independien es (que se deno a án po
1(,)
j
LR
λµ
), uno
po cada pe íodo de iempo conside ado. Es os úl imos p oblemas son p oblemas con inuos
de p og amación lineal pa a los cuales exis en algo i mos muy e icaces que pe mi en su
esolución con acilidad. Adicionalmen e, al esol e es os úl imos
T
subp oblemas pa a cada
almacén
m
j
,...,1
=
, se ob iene el alo de las a iables bina ias
j
z pa a odo
j,
. La
esolución de es os
T
subp oblemas se in e p e a como el cos e que supone ab i el almacén
j
en cada pe íodo de iempo, po lo que si c
jJ
∈,
{
}
1,...,
(1(,))min(1(,))
jj
T
LR LR
λµλµ
=
= y
en caso de que o
jJ
∈ se á el mínimo en e el an e io alo y 0. Una ez esuel o
1(,)
j
LR
λµ
pa a odo alo de
j
, se e i ica que
1
(1(,))(1(,))
m
j
j
LR LR
λµλµ
=
=∑.
Se puede p ocede de o ma simila pa a esol e el p oblema
))
,
(2(
µ
λ
LR
, ob eniéndose
igualmen e el pe íodo de iempo en que cada plan a iene que se abie a ( o ce ada, si es el
caso) y po an o, el alo de las a iables bina ias
k
ζ
pa a odo
k,
.
De es a o ma, as sucesi as descomposiciones se ob iene la solución del p oblema
elajado pa a cada conjun o de mul iplicado es 0
il
µ
≥ y
jl
λ
∈ℜ.
Se conoce ( e Fishe (1981)) que pa a cada conjun o de mul iplicado es, la solución de
))
,
((
µ
λ
LR
e i ica la siguien e elación:
)),((max:)()( ,
ηλ
µλLR DL P =≥
Al p oblema
)(DL
se le conoce con el nomb e de dual lag angiano y puede se esuel o
median e el algo i mo del subg adien e ( e Held e al. (1974)), pa a el cual p oponemos el
siguien e conjun o de mul iplicado es iniciales:
• lj
jl ,, 0 ∀=
λ
.
•
{
}
lidc
il
ijl
j
il ,, max ∀=
µ
.
La esolución del p oblema dual nos pe mi i á ob ene la máxima, o al menos una buena co a
in e io de la solución de nues o p oblema o iginal. Sin emba go, po no ma gene al, es a
solución no se á ac ible, es deci , no e i ica á las es icciones que ue on elajadas en el
p oblema
)(P
po lo que, esol e emos el p oblema dual y una ez ob enida la mejo