Revista de Matema´tica: Teor´ıa y Aplicaciones 2000 7(1-2) : 117–124
cimpa – ucr – ccss issn: 1409-2433
un problema de localizacio´n de plantas de
gran escala
Miguel Angel Gutie´rrez Andrade*– Sergio De los Cobos Silva**
Blanca Rosa Pe´rez Salvador***– John Goddard****
Recibido: 16 Junio 2000
Resumen
En este art´ıculo se desarrolla un algoritmo heur´ıstico y su correspondiente imple-
mentacio´n para resolver un problema de localizacio´n de plantas de gran escala, en
donde surgen potencialmente ma´s de 640 plantas a localizar a lo largo de la Repu´bli-
ca Mexicana. Originalmente se trato´ de obtener solucio´n exacta al problema, usando
dos te´cnicas cla´sicas: descomposicio´n de Benders y ramificacio´n y acotamiento. Am-
bas te´cnicas resultan adecuadas y eficientes para resolver problemas de taman˜o chico,
pero las implantaciones en computadora para este problema no convergieron despue´s
de muchas horas de proceso. Se requer´ıa obtener una solucio´n al problema mediante
alguna te´cnica que quiza´ no diera la solucio´n exacta, pero s´ı una solucio´n de buena cal-
idad. Para la solucio´n de este problema real, se empleo´ la te´cnica de recocido simulado
con excelentes resultados.
Palabras clave: localizacio´n, sobrecalentamiento simulado, recocido simulado, heur´ıstica.
Abstract
We develop an heuristic algorithm and its implementation for solving a large scale
facility location problem, where there can arise over 640 facilities to be located in
Mexico. Originally, we tried to obtain an exact solution to the problem, using two
classical techniques: Benders decomposition, and branch and bound. Both techniques
*Depto. de Sistemas, Universidad Auto´noma Metropolitana-Azcapotzalco, Av. San Pablo 180, Colonia
Reynosa Tamaulipas, 02200 Me´xico, D.F. Me´xico; E-Mail: gama@hp9000a1.uam.mx
**Depto. de Ingenier´ıa Ele´ctrica, Universidad Auto´noma Metropolitana-Iztapalapa, Av. Michoaca´n y La
Pur´ısima, Col. Vicentina, CP 09340 Me´xico D.F., Me´xico; E-Mail: cobos@xanum.uam.mx
***Depto. de Matema´ticas, Universidad Auto´noma Metropolitana-Iztapalapa, Av. Michoaca´n y La
Pur´ısima, Col. Vicentina, CP 09340 Me´xico D.F., Me´xico.
****Misma direccio´n que S. de los Cobos; E-Mail: jgc@xanum.uam.mx
117
118 m.a. gutie´rrez – s. de los cobos – b.r. pe´rez – j. goddard
are adequate and efficient for solving low-scale problems, but computer implementa-
tions for this problem did not converge after several hours of computing. Hence, we
needed a good solution even if it was not exact. We used the simulated annealing
technique with excellent results.
Keywords: facility location, simulated annealing, heuristics.
Mathematics Subject Classification: 90B80
1. Descripcio´n del problema de localizacio´n de plantas
El problema de localizacio´n de plantas tiene la siguiente estructura: hay n sitios en una
regio´n que requiere un producto. La demanda para el producto en el sitio i es di unidades,
para i = 1, . . . , n. La demanda tiene que satisfacerse manufacturando el producto dentro
de la regio´n. Se necesitan m o menos plantas para manufacturar el producto que satisfaga
la demanda, donde m se especifica. El costo por construir una planta en el sitio i es fi
unidades monetarias. Si una planta se construye en el sitio i, ki unidades es la capacidad
de produccio´n.
Si existe una ruta de transporte entre el sitio i al j, kij es la capacidad sobre el
horizonte de planeacio´n y cij es el costo de transporte de una unidad entre el sitio i al
j y fij es el costo fijo por usar la ruta entre el sitio i al j. El problema es determinar
un subconjunto o´ptimo de sitios de localizacio´n de las plantas y un plan de transporte
que minimice el costo total de construccio´n de plantas y el transporte de productos. El
problema de determinar un subconjunto de sitios para localizar plantas y los costos fijos
de transporte entre sitios es un problema de optimizacio´n combinatoria. Una vez que se
conoce una solucio´n de este problema, es decir, se ha decidido donde colocar las plantas,
el problema de determinar la cantidad o´ptima transportada a lo largo de las rutas es un
simple problema de transporte. As´ı, cada vez que se asignan las plantas a sitios, se debe
resolver un problema de transporte para obtener la distribucio´n o´ptima del producto.
Este problema puede formularse como un problema entero usando variables de decisio´n
con las siguientes interpretaciones:
yi = 1 si la planta se localiza en el sitio i,
yi = 0 en otro caso.
yij = 1 si existe una ruta de transporte del sitio i al j,
yij = 0 en otro caso.
xij = cantidad (en unidades) del producto transportado del sitio i al j.
Entonces el problema de localizacio´n de plantas puede formularse matema´ticamente como:
min
∑
i
∑
j
cijxij +
∑
i
fiyi +
∑
i
∑
j
fijyij
Sujeto a
∑
j xij − kiyi ≤ 0 ∀i
xij − kijyij ≤ 0 ∀i, j∑
i xij ≥ dj ∀j∑
i yi ≤ m
xij ≥ 0, ∀i, j; yi, yij = 0 o´ 1 ∀i, j
un problema de localizacio´n de plantas de gran escala 119
El problema de localizacio´n de plantas esta´ clasificado dentro de la familia NP -completa
y por lo tanto los algoritmos conocidos para resolver el problema de manera exacta, son
no polinomiales, como por ejemplo, enumeracio´n impl´ıcita y ramificacio´n y acotamiento.
2. Aplicacio´n del recocido simulado
El algoritmo de recocido simulado puede usarse para atacar este problema y obtener
soluciones que no necesariamente son o´ptimas, pero se puede mostrar un comportamiento
muy favorable del me´todo con respecto a instancias que se conoce la solucio´n. Para mayores
detalles acerca de la filosof´ıa del algoritmo vea [1].
2.1. Descripcio´n del algoritmo
El algoritmo de recocido simulado se implemento´ de la siguiente manera:
El espacio de soluciones S, para el problema combinatorio, esta´ representado por
todos los vectores binarios y1, y2, . . . , yn tal que yi = 0 o´ 1 y
∑n
i=1 yi ≤ m. Donde
yi = 0 si no se coloca planta en el sitio i y yi = 1 si se coloca planta en el sitio i.
La funcio´n de costo a minimizar, se escoge como: f =
∑
i
∑
j cijxij +
∑
i fiyi donde
xij es la cantidad (en unidades) del producto transportado del sitio i al sitio j y
f es la suma del costo de la localizacio´n de las plantas, ma´s el costo de transporte
del producto. Para este caso los costos fijos fij se tomaron iguales a cero ya que no
existe ningu´n costo fijo por el uso de los caminos.
Las nuevas soluciones se obtienen a partir de dos mecanismos de generacio´n: uno
que selecciona aleatoriamente un sitio i, si existe planta en el sitio i se quita y si no
existe, entonces se coloca una planta. El otro mecanismo genera aleatoriamente un
sitio i, si existe una planta en i se cambia a otro sitio j donde no exista, tomado de
manera aleatoria y si no existe planta en el sitio i, se busca aleatoriamente un sitio
j donde exista una planta y se intercambia. La seleccio´n de uno u otro mecanismo
se hace de manera aleatoria. Con probabilidad p se hace intercambio de plantas y
con probabilidad 1 − p se abre una planta o se cierra. El valor de p puede variarse
dependiendo del para´metro de control.
La actualizacio´n de la funcio´n de costo entre la solucio´n actual y la nueva solucio´n
puede hacerse fa´cilmente en la parte de costos fijos u´nicamente al quitar, agregar o
intercambiar los costos de plantas que se den de alta y de baja. La parte del costo de
transporte debe calcularse para cada nueva configuracio´n usando la solucio´n actual
y modificando los suministros variados por medio de penalizaciones.
El valor inicial c del para´metro de control se obtuvo de manera que la tasa de
aceptacio´n de las soluciones propuestas fuera mayor o igual al 95%.
Los valores subsiguientes del para´metro de control se obtuvieron decrementando e´ste
en 1% donde no se acepto´ ninguna nueva solucio´n despue´s de explorar r veces sobre
las soluciones vecinas.
120 m.a. gutie´rrez – s. de los cobos – b.r. pe´rez – j. goddard
El nu´mero de iteraciones r para un valor fijo del para´metro de control se tomo´ igual
al taman˜o ma´ximo de la vecindad de una solucio´n n+ n(n− 1) = n2
La Figura 1 describe el algoritmo usado de recocido simulado para este problema.
Algoritmo de Recocido Simulado para el Problema de Localizacio´n
de Plantas
Propo´sito: Obtener los sitios donde colocar las plantas y la asignacio´n de
plantas a consumidores.
Descripcio´n:
Paso 1: Tome c un valor grande apropiado.
Paso 2: Asigne valores 0 o 1 a yi con i ∈ {1, 2, . . . , n} de manera arbi-
traria. Obtenga el valor correspondiente de la funcio´n objetivo f .
Paso 3: Asigne el valor verdadero a la variable lo´gica CHANGE.
Paso 4: Si la variableCHANGE tiene valor falso, entonces pare.
Paso 5: Haga CHANGE igual a falso.
Paso 6: Repita los puntos 1-11 r veces.
1.- Seleccione aleatoriamente un nu´mero u ∈ {1, 2, . . . , n}.
2.- Genere un nu´mero aleatorio x,
uniformemente distribuido en (0, 1).
3.- Si x ≥ p abra (o cierre) la planta u,
en caso contrario interca´mbiela por una cerrada (abierta).
4.- Evalu´e el valor ∆f .
5.- Si ∆f < 0 entonces vaya a 9.
6.- Sea P (∆f) = exp(−∆f/c).
7.- Genere un nu´mero aleatorio x, uniformemente distribuido en (0, 1).
8.- Si x ≥ P (∆f) entonces vaya a 11.
9.- Acepte el cambio hecho y reactualice el valor de f .
10.- S´ı ∆f 6= 0 entonces CHANGE ←− verdadero.
11.- Fin del paso 6.
Paso 7: Reduzca c e incremente p y r.
Paso 8: Vaya al paso 4.
Figura 1: Algoritmo de recocido simulado para el problema de localizacio´n de plantas
2.2. Experiencia computacional
La prueba del algoritmo se llevo´ a cabo generando de manera aleatoria instancias
del problema de localizacio´n de plantas. Para valores preestablecidos del nu´mero m de
plantas y el nu´mero n de centros de consumo, se generaron 100 instancias aleatorias del
problema. Para cada planta se tomo´ como costo fijo un nu´mero aleatorio con distribucio´n
uniforme entre (100-500); para cada consumidor se tomo´ como costo de transporte un
nu´mero aleatorio con distribucio´n uniforme entre (40-200) y finalmente para la demanda
en cada sitio, se tomo´ un nu´mero aleatorio con distribucio´n uniforme entre (10-100).
Para calcular la eficiencia del algoritmo se uso´ el siguiente ı´ndice
eficiencia = 1− f − fopt
fopt
un problema de localizacio´n de plantas de gran escala 121
donde f denota el valor de la funcio´n objetivo en la solucio´n obtenida y fopt es el valor
o´ptimo de la instancia del problema, donde el valor fopt se obtiene usando un algoritmo
exacto. Para obtener los o´ptimos que se requieren en la Tabla 1 se uso´ el algoritmo de
Khumawala [3].
La Tabla 1 reporta la eficiencia del algoritmo con respecto al valor o´ptimo de la funcio´n
objetivo. Los valores que aparecen son con base en los promedios obtenidos en las 100
instancias resueltas para cada valor del nu´mero m de plantas y del nu´mero n de sitios de
consumo.
Nu´mero Nu´mero de Plantas (m)
de Nodos (n) Eficiencia
5 10 15 20
5 0.9899 0.9966 0.9989 0.9977
10 15 25 30
10 0.9962 0.9929 0.9957 0.9912
15 25 35 40
15 0.9924 0.9985 0.9963 0.9796
20 25 35 40
20 0.9919 0.9847 0.9863 0.9895
25 30 35 40
25 0.9911 0.9884 0.9943 0.9886
30 40 50 60
30 0.9891 0.9920 0.9881 0.9866
35 40 50 60
35 0.9904 0.9906 0.9898 0.9923
40 45 50 60
40 0.9857 0.9943 0.9917 0.9862
Cuadro 1: Eficiencia promedio del algoritmo para las 100 instancias.
3. Problema de Localizacio´n de Plantas de Gran Escala
El problema consiste en la localizacio´n de plantas productoras de tortilla empacada
y tiene la siguiente estructura: se consideran 80 centros de demanda en la Repu´blica
Mexicana que corresponden a 85 ciudades con ma´s de 50,000 habitantes que requieren
del producto. Se tiene que satisfacer la demanda, para lo anterior se requiere construir
plantas de tortilla empacada en algunas zonas. El costo por construir una planta en un sitio,
depende del taman˜o de la planta (para propo´sitos de las corridas del modelo se consideraron
tres taman˜os: 2 toneladas diarias, 5.34 toneladas diarias, 16 toneladas diarias). Adema´s
se considero´ que el costo de los insumos (harina de ma´ız) depende de la distancia de la
planta a la fa´brica de harina ma´s cercana a la misma.
El problema consiste en determinar un conjunto o´ptimo de sitios de localizacio´n de las
plantas, nu´mero de plantas y sus respectivas capacidades; as´ı como la zona de influencia
122 m.a. gutie´rrez – s. de los cobos – b.r. pe´rez – j. goddard
de las mismas. Las zonas de influencia se reflejan en un plan o´ptimo de transporte en el
horizonte de planeacio´n (a 10 an˜os).
Se desea minimizar el costo total de construccio´n anualizado de las plantas y el costo
total de transporte de la tortilla de ma´ız empacada.
Entre los supuestos usados tenemos:
Costos. Como ya se menciono´, existen dos componentes principales en los costos del prob-
lema a minimizar: Costos de transporte y costos fijos.
Costos de transporte. Para obtener los costos de transporte se consideraron las distan-
cias existentes en la red carretera entre cada par de sitios. Estas distancias se obtuvieron
del Atlas de Carreteras de Me´xico editado por Gu´ıa Roji (1999) en donde se tomaron en
cuenta las rutas comerciales. Cabe mencionar que existen dos rutas mar´ıtimas que son:
Mazatla´n- La Paz y Mochis-La Paz, en donde se tomo´ un costo de transporte del doble del
considerado por v´ıa terrestre. El costo de transporte se obtiene multiplicando la distancia
por el costo por kilo´metro-tonelada transportada. El valor del costo por kilo´metro por
tonelada transportada se considero´ homoge´neo en todo el territorio e igual a 1.25 pesos.
Costos fijos. Los costos fijos consisten de varios rubros: Costos de inversio´n (costo de
depreciacio´n de equipo), costos de insumos, costos de operacio´n, costos de distribucio´n,
gastos financieros, utilidad y varios. Todos los costos fijos se tomaron anualizados.
Demandas. Con base en las estimaciones de consumo potencial de tortilla y de la dis-
tribucio´n del mismo por entidad federativa y ciudad, se obtuvo una demanda potencial
en cada uno de los sitios considerados. Se tomaron en cuenta dos escenarios de acuerdo
a que el consumo de la tortilla empacada, en principio, se limita u´nicamente a las clases
media y alta. Uno de los escenarios supone la captacio´n de un 10% de demanda y el otro
del 20%.
Nu´mero de plantas. Debido a la gran diversidad en cuanto al taman˜o de la demanda,
se dividieron los centros de demanda en dos clases: (1) Zona Metropolitana, Guadalajara,
Monterrey y Puebla. (2) los 76 centros restantes.
Para la primera clase, es claro que en la solucio´n o´ptima se deben colocar plantas de al
menos el taman˜o de la demanda en las mismas y de capacidad ma´xima adema´s de dejar
la opcio´n al modelo de colocar plantas adicionales para satisfacer la demanda de sitios
cercanos a la misma. En la segunda clase se tomaron como posibles opciones de solucio´n,
la construccio´n de dos plantas de 2 toneladas diarias, 2 plantas de 5.34 toneladas diarias, 4
plantas de 16 toneladas diarias; dando un total de ocho posibilidades. Esto es, la solucio´n
puede ser una combinacio´n de las ocho posibilidades.
Centros de insumo. Se consideraron 19 puntos de insumos de harina de ma´ız, estos
lugares corresponden a la existencia de fa´bricas de harina de ma´ız ocho de MICONSA
(localizadas en Los Mochis, Sin.; Guadalajara, Jal.; Tlalnepantla, Edo. de Mex.; Arriaga,
Chis.; Jaltipa´n, Ver.; Atlacomulco, Edo. de Mex.; Acapulco, Gro. y Monterrey, N.L.) y once
de MASECA (localizadas en Monterrey, N.L.; Rı´o Bravo, Tamps.; Tampico, Tamps.; Chi-
nameca, Ver.; Teotihuacan, Edo. de Mex.; Zamora, Mich.; Guadalajara, Jal.; Acaponeta,
Nay.; Culiaca´n, Sin.; Obrego´n, Son. y Chihuahua, Chi.) Para cada posible lugar de local-
izacio´n se considera la distancia mı´nima entre dicho lugar y todos los puntos de insumo.
un problema de localizacio´n de plantas de gran escala 123
3.1. Enfoques cla´sicos de solucio´n
El problema se trato´ de solucionar de manera exacta mediante dos te´cnicas cla´sicas que
se han venido utilizando: descomposicio´n de Benders [6] y ramificacio´n y acotamiento [3]
y [5]. Ambas te´cnicas resultan adecuadas y eficientes para resolver problemas de taman˜o
chico, pero para el problema anteriormente descrito, donde se tienen 640 variables binarias
estas te´cnicas son impracticables, pues para instancias mayores de 60 variables binarias
presentan problemas de tiempo de ejecucio´n excesivo.
3.2. Solucio´n con recocido simulado
Como ya se comento´ el algoritmo de recocido simulado puede usarse para resolver
el problema expuesto. Para ello se procedio´ a implantar un co´digo de computadora que
resolviera el problema. El lenguaje que se uso´ en la programacio´n fue FORTRAN 77; el
programa consta de alrededor de 1800 l´ıneas de co´digo y corre en una computadora PC.
En este programa se especifico´ un mecanismo de generacio´n de vecindades y un programa
de enfriamiento. El mecanismo de generacio´n de vecindades y el programa de enfriamiento
ya se especificaron en la Seccio´n 2. Se hicieron varias corridas para cada combinacio´n del
periodo y reduccio´n del para´metro de control.
3.3. Resultados obtenidos
En ambas corridas (10% de tortillas empacadas tienen distancias pequen˜as. Esto es,
so´lo existe transferencia entre ciudades cercanas lo que asegura el plan de distribucio´n
o´ptimo. Existen pocos movimientos en la red carretera. Entre 140 ligas interciudades
existentes, so´lo la mitad (aproximadamente 70) de ellas tienen flujo de mercanc´ıa. Se
observa que los costos de transporte (flete) son muy pequen˜os.
Dado que el costo de colocar una planta es muy superior al costo de transporte, op-
timizar las inversiones es predominante, entonces es lo´gico que la capacidad total debe
ser ligeramente mayor que la demanda total. En las corridas, las capacidades instaladas
son 0.44% u´nicamente 0.15% las capacidades de las plantas. En la mayor´ıa de los casos,
la capacidad instalada en cada ciudad es similar a la demanda de la misma, lo cual es
razonable ya que se evitan transferencias de la mercanc´ıa entre las ciudades. Esto significa
que el modelo de optimizacio´n tiende a satisfacer las demandas locales.
Para el caso de 10% de demanda, el costo de transporte es slo 1.25% de la inversin
total.Para el caso de 20% de demanda, el costo de transporte es slo 0.82% de la inversin
total. Las zonas de influencia se reducen a regiones pequen˜as.
Existen varias ciudades que no requieren ninguna inversio´n ya que sus demandas son
pequen˜as y pueden satisfacerse por zonas aledan˜as. A pesar de considerar so´lo el 10%
demanda potencial, se requiere muchas plantas en que invertir, lo cual implica un mercado
futuro atractivo. Se observa que el modelo introduce, por lo general plantas grandes para
satisfacer las demandas, esto se debe a que los costos marginales son menores que los costos
en que se incurrir´ıa si se instalaran plantas ma´s chicas. El modelo u´nicamente introduce
plantas chicas o medianas para ajustar la demanda a la oferta. Por otro lado, como el
costo de inversio´n es muy superior al costo de transporte, es preferible instalar plantas
124 m.a. gutie´rrez – s. de los cobos – b.r. pe´rez – j. goddard
grandes y hacer transferencias de flujo para satisfacer demandas en los centros donde la
demanda es menor.
4. Conclusiones
En este art´ıculo se presento´ un algoritmo de recocido simulado para resolver el proble-
ma de localizacio´n de plantas. Este algoritmo se probo´ para instancias de taman˜o medio,
comparando su eficiencia con respecto a los valores o´ptimos dados por un algoritmo exacto.
Se observo´ que la eficiencia mı´nima fue del 0.9796, por lo que concluimos que el algoritmo
heur´ıstico da soluciones de buena calidad.
Los algoritmos exactos que resuelven el problema de Localizacio´n de Plantas son viables
para problemas en donde el nu´mero de plantas a localizar es pequen˜o o mediano, en este
estudio, para 40 plantas ya los algoritmos exactos tienen problemas de convergencia, para
80 plantas los algoritmos exactos no convergieron.
El algoritmo de recocido simulado se uso´ para resolver un problema de Localizacio´n
de Plantas de gran escala. Para este problema se requer´ıa localizar 640 plantas a lo largo
de la Repu´blica Mexicana. Los resultados obtenidos fueron excelentes.
Se menciona que los resultados del modelo fueron excelentes ya que en la solucio´n del
problema real se observa: pocos movimientos en la red carretera; las distancias recorridas
entre una planta y un centro de demanda es pequen˜a, es decir, el modelo tiende a satisfacer
demandas locales; la capacidad total instalada es ligeramente mayor a la utilizada, esto
implica que se aprovecha casi totalmente las capacidades de las plantas
Referencias
[1] Aarts, E.; Korst, J. (1989) Simulated Annealing and Boltzmann Machines. John Wiley & Sons,
Chichester.
[2] Emden-Weinert, T., Proksch, M., (1999) “Practice simulated annealing for the airline crew
scheduling problem”, Journal of Heuristics 5(4): 419–436.
[3] Khumawala, B.M. (1972) “An efficient branch and bound algorithm for the warehouse location
problem”, Management Science 18: 718–731.
[4] Geraldo, R.; Mateus, G.R.; Luna, H.; Sirihal, A. (2000) “Heuristics for distribution network
design in telecommunication”, Journal of Heuristics 6(1): 133–150.
[5] Mirchandani, P.B.; Reilly, J.M. (1986) “Spatial nodes in discrete location problems”, Annals
of Operations Research 6: 203–222.
[6] Mirchandani, P.B.; Francis, R.L. (Eds.) (1990) Discrete Location Theory. John Wiley & Sons,
New York.
[7] Privault, C.; Herault, L. (1998) “Solving a real world assignment problem with a metaheuris-
tic”, Journal of Heuristics 4(4): 383–398.