Un modelo temporal de localización de plantas y almacenes con existencias finales en cada periodo

1 UN MODELO TEMPORAL DE LOCALIZACIÓN DE PLANTAS Y ALMACENES CON EXISTENCIAS FINALES EN CADA PERIODO. Autores: Hinojosa Bergillos, Yolanda Puerto Albandoz, Justo [email protected] [email protected] Dpto. de Economía Aplicada I. Dpto. de Estadística e I.O. Universidad de Sevilla Universidad de Sevilla Palabras clave: Localización de plantas, programación entera mixta, dual lagrangiano, inventarios, heurístico. Resumen: En este trabajo se aborda un problema de localización de plantas de producción y centros de almacenamiento con objeto de satisfacer las demandas de un grupo de clientes. La distribución de productos se realiza en dos etapas diferenciadas: Envío desde las plantas de producción a los diferentes almacenes y envío posterior desde éstos a los distintos clientes. El estudio se realiza a lo largo de un horizonte temporal finito considerando las existencias finales en los almacenes como existencias iniciales del período siguiente. Asimismo, se supone que tanto almacenes como plantas tienen capacidad limitada. Nuestro objetivo consiste en determinar la política óptima, en el horizonte temporal fijado, para la instalación (o en su caso, cierre) de plantas y almacenes, de forma que se satisfagan las demandas de los clientes, en cada período, a mínimo coste. En este coste se incluyen los costes de apertura (o en su caso, cierre), mantenimiento y funcionamiento de plantas y almacenes, así como, los costes de transporte y almacenamiento de existencias finales. El modelo es formulado como un problema de programación entera mixta. Para su resolución se propone una relajación lagrangiana junto con un procedimiento heurístico mediante el cual se obtiene una buena solución del problema original. 1.-Introducción. Son muchas las situaciones reales en las que grandes compañías manufacturan y distribuyen diversos tipos de productos. Una de las primeras cuestiones que dichas compañías han de plantearse es dónde ubicar las plantas de producción y/o los almacenes desde donde distribuirán sus productos a los diferentes clientes con objeto de cubrir las demandas de éstos a mínimo coste. Éste es el caso, por citar algún ejemplo, de compañías que fabrican y almacenan piezas de recambio de coches, de aquellas que elaboran y distribuyen catálogos entre distintas agencias y comercios o de las que, en general, producen y distribuyen algún tipo de bien. Si las ubicaciones admisibles para las plantas de producción y/o distribución son finitas y conocidas de antemano, nos enfrentamos con un problema 2 clásico dentro de la Teoría de Localización discreta conocido como el problema de localización de plantas. Estos problemas han sido ampliamente estudiados y, en términos generales, pueden clasificarse en: 1) Problemas de localización de plantas simples sin restricciones de capacidad (SPLP); 2) Problemas de localización de plantas con restricciones de capacidad (CPLP). Aunque ambos tipos de problemas pueden ser formulados como problemas de programación entera-mixta (véase, por ejemplo, Aikens (1985)), no va a ser posible, en general, obtener su solución exacta en tiempo polinomial por pertenecer a la clase de problemas conocidos como problemas NP-duros (véase Krarup y Pruzan (1983) quienes probaron que incluso el SPLP es un problema NP-duro). Se han estudiado muchas extensiones de estos problemas (véase, por ejemplo, Aikens (1985), Drezner (1995) o Daskin (1995)) donde se puede encontrar una buena recopilación de estos problemas y de sus extensiones). Podemos resaltar dos de ellas, la primera consiste en introducir aspectos temporales en el modelo. En este caso las variables de decisión no son sólo las que hacen referencia a la planificación del transporte y localización de plantas, sino también al período de tiempo en que las plantas se ponen en funcionamiento (véase por ej., Warszawski's (1973), Van Roy y Erlenkotter (1982) o más recientemente Chardaire et al. (1996) ). En la segunda se supone la existencia de una cierta estructura en el esquema de transporte (problemas multietápicos), es decir, el transporte desde las plantas hasta los clientes se realiza en dos etapas bien diferenciadas. Estos modelos ha sido escasamente estudiados en la literatura clásica sobre localización (véase Kaufman et al. (1977) o Tcha y Lee (1984) ), aunque en la última década han aparecido importantes trabajos (véase Daskin (1995) , Marín (1996), Crainic y Delorme (1993), Barros y Labbé (1994) o Pirkul y Jayaraman (1996)). La principal peculiaridad de estos modelos es que los productos son enviados desde las plantas de producción a los almacenes para posteriormente ser transportados desde estos a los diferentes clientes. Por tanto, el problema de decisión consiste en localizar las plantas y almacenes y en determinar la cantidad de los diferentes productos que será enviada desde cada planta en funcionamiento a cada almacén abierto y desde éste a cada cliente. Adicionalmente, en ambas extensiones se puede considerar o no restricciones sobre capacidad. El marco más natural para estos problemas es la combinación de ambas extensiones, es decir, la consideración conjunta de aspectos multietápicos y multitemporales. Esta combinación ha sido estudiada por primera vez por Hinojosa, Puerto y Fernández (2000) quienes consideran un modelo bietápico en el que los productos son enviados desde las 3 plantas de producción a un conjunto de almacenes para posteriormente ser distribuidos desde éstos a los diferentes clientes. Adicionalmente, realizan el estudio a través de un horizonte temporal finito en el que se permite tanto la apertura de nuevas plantas como el cierre de las ya existentes. Sin embargo, este modelo no considera la existencia de stock al final de cada temporada lo cual tiene sentido cuando se trabaje con productos perecederos o de temporada pero, deja de tenerlo cuando se trabaja con productos que permanecen de una temporada a otra como podría ser el caso de las piezas de recambio de coches. El modelo que abordamos en el presente trabajo es una extensión del citado anteriormente en el que las existencias al final de cada temporada se mantienen almacenadas en las plantas de distribución o almacenes hasta el inicio de la temporada siguiente, considerándose en esta como existencias iniciales. En todo momento se supone que tanto almacenes como plantas de producción tienen capacidad limitada, por lo que tanto la cantidad producida como la almacenada ha de estar sujeta a esta restricción. Nuestro objetivo es determinar en el horizonte temporal fijado, la política óptima para la instalación (o en su caso, cierre) de plantas y almacenes así como para la distribución de productos. Por política óptima se entiende aquella que permita satisfacer en cada período las demandas de todos los clientes a mínimo coste. En este coste se incluyen los costes de apertura (o en su caso, cierre), mantenimiento y funcionamiento de plantas y almacenes, así como, los costes de transporte y los costes de almacenamiento de las existencias al final de cada período. Este modelo es un problema de programación entera mixta con un elevado número de variables (por ejemplo, un problema con 100 clientes, 15 almacenes, 5 plantas, 2 tipos diferentes de productos y 5 periodos de tiempo tiene 15970 variables y 1334 restricciones). Esto hace que el tiempo computacional requerido para su resolución exacta por acotación ramificación sea prohibitivo. Por tanto se propone un método alternativo para la obtención de soluciones aproximadas que incorpora un método dual ascendente aplicado a una relajación lagrangiana del problema junto con un procedimiento heurístico. El trabajo queda organizado como sigue. En la sección 2 se presenta la formulación matemática del modelo como un problema de programación entera mixta. En la sección 3 proponemos una relajación Lagrangiana del mismo, la cual puede ser resuelta de forma óptima tras la resolución de un número finito de problemas lineales junto con la aplicación de un algoritmo del subgradiente. En la sección 4 se desarrolla un procedimiento heurístico para la obtención de una solución factible de nuestro modelo. En la quinta sección se presentan algunas conclusiones. 4 2.-El modelo. En este modelo se aborda un problema de localización de plantas con objeto de diseñar y planificar un sistema de distribución a lo largo de un horizonte temporal en el que se fija el estudio del mismo. Para este tipo de problemas suele ser usual considerar meses o temporadas como longitud de cada período de tiempo. Se asume que los conjuntos de clientes y productos, así como las posibles ubicaciones para las plantas de producción y almacenes están fijos y son conocidos de antemano, por lo que no cambiarán a lo largo del citado horizonte. Se denotará por: • 1,...,In= {} al conjunto de clientes a los que se referenciará por iI∈ . • 1,...,Lq= {} al conjunto de los diferentes tipos de productos, referenciados por lL∈ . • 1,...,Jm= {} al conjunto de posibles ubicaciones para los almacenes, referenciados por jJ∈ . • 1,...,Kp = {} al conjunto de posibles ubicaciones para las plantas de producción, referenciadas por kK∈ . Se considera que tanto las plantas de producción como los almacenes tienen una capacidad limitada, así se denotará por: • t j W la capacidad del almacén j en el período de tiempo t , • t k C la capacidad de la planta k en el período de tiempo t y por • t il d la demanda que el cliente i tiene del producto l durante el período t . Al comienzo del primer período de tiempo se supone que existe un subconjunto c K dentro del conjunto total de posibles ubicaciones para plantas donde ya existen plantas en funcionamiento. Éstas se pueden cerrar al final de cualquier período del horizonte temporal, pero una vez cerradas no pueden volver a ser abiertas. Se denotará por o K el conjunto de posibles ubicaciones donde no existen plantas en funcionamiento antes del comienzo del primer período de tiempo. Estas plantas podrán ser abiertas al comienzo de cualquier período de tiempo, pero una vez abiertas ya no podrán volver a ser cerradas dentro del horizonte temporal considerado. En los mismos términos se supone la existencia de subconjuntos c Jy o J para los almacenes. Esta hipótesis es bastante razonable. En muchas ocasiones el hecho de cerrar y abrir sin que exista una continuidad trae consigo una pérdida de mercado puesto que los consumidores requieren una cierta regularidad para mantenerse como clientes 5 habituales de una determinada firma o comercio. Esto nos permite definir las variables de decisión del problema como: • , 1si el almacen es abierto al comienzo del periodo 0en otro caso t oj jt jJtz  ∀∈∀=   • , 1si el almacen es cerrado al final del periodo 1 0en otro caso t cj jt jJtTz  ∀∈∀<−=   • , 1si el almacen se mantiene abierto durante todo el horizonte temporal 0en otro caso T cj j jJz  ∀∈=   • t k ζ es definido de forma análoga para el conjunto de plantas. • : t ijl x=fracción (con respecto a t il d) de producto lenviado desde el almacén j al cliente i durante el período t . • : t jkl y=fracción (con respecto a t j W) de producto lenviado desde la planta k al almacén j durante el período t . • : t jl I=stock de producto len el almacén j al final del período t . Asimismo, para asegurar una cobertura mínima de la demanda se obliga a que haya un mínimo número de plantas y almacenes abiertos al comienzo y al final del horizonte temporal. Se denotará por 1,T NWNW (respectivamente 1,T NPNP ) al mínimo número de almacenes y plantas respectivamente que han de estar abiertos al comienzo del primer período y al final del último. Por último se supone un estructura de costes que incluye costes de apertura (o en su caso, cierre), mantenimiento y funcionamiento de plantas y almacenes, así como, costes de transporte y costes de almacenamiento de las existencias al final de cada período. Estos costes se denotarán por: • , : t oj jJF ∀∈= coste total por abrir el almacén j al comienzo del período t . Este coste incluye el coste de apertura al comienzo del período t más el coste de mantenimiento y funcionamiento del almacén j desde el período t hasta el final del horizonte temporal • , 1 : t cj jJtTF ∀∈∀<−= coste total por cerrar el almacén j al final del período t . 6 Este coste incluye el coste de cierre al final del período t más el coste de mantenimiento y funcionamiento del almacén j desde el comienzo del horizonte temporal hasta el final del período t . • , : T cj jJF ∀∈= coste total por mantener abierto el almacén j durante todo el horizonte temporal. • t k G es definido de forma análoga para el conjunto de plantas. • : t jkl b=coste por unidad de producto lenviado desde la planta k al almacén j durante el período t . • : t ijl c=coste por unidad de producto lenviado desde el almacén j al cliente i durante el período t . • : t jl p=coste por unidad de existencia de producto l en el almacén j al final del período t . Por simplificación de notación se considerará: • } { } { 1,...,si ,...,si o jt c tjJ T tTjJ ∈  =∈   y análogamente kt T para las plantas. De acuerdo con las hipótesis y notación descritas, la formulación matemática del problema es la siguiente: 11111111111 1111 () min (,,,): + qpqq TnmTmTm tttttttt ijlijliljkljkljjljl tijltjkltjl p TmT tttt jjkk tjtk PfxyzcxdbyWpI FzG ζ ζ =========== ==== =++ + ∑∑∑∑∑∑∑∑∑∑∑ ∑∑∑∑ sujeto a: 1 111 1 , , (1) , jt mt ijl j qq nttttr ilijljljj illrT xilt dxIWzjt = ===∈ ≥∀∀∀ +≤∀∀ ∑ ∑∑∑∑ 1 1 1 1 1 (2) , 1,...,1 (3) jt qttr jljj lrT ttt jjkljl k IWzjtT WyI + + =∈ − = ≤∀∀=− + ∑∑ 1 11 , , (4) , (5) kt pnttt ilijljl i qmtttr jjklkk jlrT dxIjlt WyCkt ζ = ==∈ =+∀∀∀ ≤∀∀ ∑∑ ∑∑∑ 7 11 11 11 ; (6) ; occo TT tTtT jjjj jJjJtjJjJt tTtT kkkk zzNWzzNW NPNP ζζζζ ∈∈=∈∈= +≥+≥ +≥+≥ ∑∑∑∑∑∑ 11 11 1 (7) 1 ; 1 (8) 1 ; occo TT kKkKtkKkKt TT tt jcjo tt Tt kc t zjJzjJ kK ζ ∈∈=∈∈= == = =∀∈≤∀∈ =∀∈ ∑∑∑∑∑∑ ∑∑ ∑1 0 1 (9) 0 ,; 0 ,, 1,...,1 (10) ,0 Tt ko t Tt jljljl tt ijljkl kK IIjlIjltT xyi ζ = ≤∀∈ ==∀≥∀=− ≥∀ ∑ } { ,,,,; ,0,1 ,, (11) tt jk jkltzjkt ζ ∈∀ Las restricciones (1) obligan a que se satisfaga la demanda que cada cliente i tiene de cada uno de los productos l en cada período de tiempo t . Esta demanda ha de ser satisfecha por los diferentes almacenes. Las restricciones (2), (3) y (5) hacen referencia a las limitaciones de capacidad. Las restricciones (2) obligan a que el número total de unidades de todos los productos enviados desde el almacén j más las existencias al final del período t sean inferior o igual a la capacidad de dicho almacén en el período t . Las restricciones (5) son análogas a las restricciones (2) pero referidas a plantas en las que no se considera que haya existencias finales. Por último, las restricciones (3) obligan a que la cantidad de existencias en el almacén j al final del período t sea menor o igual que la capacidad de dicho almacén en el período siguiente, para que puedan ser consideradas en éste último como existencias iniciales. Las restricciones (4) son ecuaciones de balance de flujo para cada almacén, cada producto y cada período de tiempo. Nótese que la cantidad de producto l enviada desde las plantas al almacén j en el período t más las existencias al final del período anterior ha de ser igual a la cantidad de producto l enviada desde dicho almacén a los distintos clientes más las existencias al final del presente período. Las restricciones (6) y (7) establecen el mínimo número de almacenes y plantas que han de estar abiertas al comienzo y al final del horizonte temporal. Las restricciones (8) y (9) hacen referencia a las características anteriormente señaladas de los conjuntos oc JJJ =Uy K oc KK =U. Las restricciones (10) obligan a que las existencias al comienzo y al final del horizonte temporal valgan 0. Por último, las restricciones (11) establecen las variables continuas y binarias del problema. 8 El problema )(P es un problema de programación entera-mixta, por lo que su resolución mediante un algoritmo exacto es computacionalmente intratable al tratarse de un problema de los clasificados como NP-duros. Por esta razón proponemos un método heurístico que se basa en : 1) realizar una relajación lagrangiana del problema, obteniendo la solución del problema dual lagrangiano mediante el algoritmo del subgradiente y 2) usar un procedimiento “ad hoc” para obtener una buena solución factible del problema )(P a partir de las soluciones de los problemas relajados. 3.- Descomposición del problema. Obtención de cotas inferiores. En esta sección se describirá someramente la técnica utilizada para la obtención de cotas inferiores de la solución óptima del problema )(P . Esta técnica, conocida como relajación lagrangiana, es bastante usual en la resolución aproximada de problemas de programación entera-mixta (véase Fisher (1981) para una descripción detallada de la misma) y es usada habitualmente en trabajos relacionados con la localización de plantas ( véase Barros y Labbé (1994), Beasley (1993), Crainic y Delorme (1993), Erlenkotter (1978), Guignard et al. (1990) o Pirkul et al. (1996)). La relajación lagrangiana nos permitirá, como ya se ha mencionado, obtener una cota inferior de la solución óptima de nuestro problema. En nuestro problema proponemos relajar las restricciones que hacen referencia a la satisfacción de las demandas (1), a las que se les asocia unos multiplicadores 0 t il µ ≥, con objeto de incorporarlas a la función objetivo. De igual forma, se relajarán las ecuaciones de balance de flujo (4) a las que se le asociarán unos multiplicadores t jl λ ∈ℜ. Esto dará lugar al problema relajado, que denotaremos por )) , (( µ λ LR , donde estas restricciones no aparecen como tales, sino incorporadas a la función objetivo por medio de los multiplicadores (para más detalle, véase Hinojosa, Puerto y Fernández (2000) en el que se realiza una relajación del mismo tipo para un problema similar). Denotemos por )(Av el valor de la función objetivo del problema )(A . Se prueba que el problema )) , (( µ λ LR en el que ya no aparecen las restricciones (1) y (4) puede ser descompuesto en dos subproblemas, a los que denotaremos por )) , (1( µ λ LR y )) , (2( µ λ LR respectivamente. . El problema )) , (1( µ λ LR sólo afecta a los almacenes y el problema )) , (2( µ λ LR a las plantas. Estos dos problemas pueden ser resueltos de forma independiente, por lo que sus soluciones respectivas serán usadas para resolver el problema relajado )) , (( µ λ LR , obteniéndose que ((,))(1(,))(2(,))vLRvLRvLR λµλµλµ =+ . 9 Para resolver el problema )) , (1( µ λ LR , se prueba que puede ser a su vez, descompuesto en m subproblemas independientes (que denotaremos por 1(,) j LR λµ ), uno por cada almacén y cada uno de éstos en T subproblemas independientes (que se denotarán por 1(,) jt LR λµ ), uno por cada período de tiempo considerado. Estos últimos problemas son problemas continuos de programación lineal para los cuales existen algoritmos muy eficaces que permiten su resolución con facilidad. Adicionalmente, al resolver estos últimos T subproblemas para cada almacén m j ,...,1 = , se obtiene el valor de las variables binarias t j z para todo tj, . La resolución de estos T subproblemas se interpreta como el coste que supone abrir el almacén j en cada período de tiempo, por lo que si c jJ ∈, { } 1,..., (1(,))min(1(,)) jjt tT vLRvLR λµλµ = = y en caso de que o jJ ∈ será el mínimo entre el anterior valor y 0. Una vez resuelto 1(,) j LR λµ para todo valor de j , se verifica que 1 (1(,))(1(,)) m j j vLRvLR λµλµ = =∑. Se puede proceder de forma similar para resolver el problema )) , (2( µ λ LR , obteniéndose igualmente el período de tiempo en que cada planta tiene que ser abierta ( o cerrada, si es el caso) y por tanto, el valor de las variables binarias t k ζ para todo tk, . De esta forma, tras sucesivas descomposiciones se obtiene la solución del problema relajado para cada conjunto de multiplicadores 0 t il µ ≥ y t jl λ ∈ℜ. Se conoce (ver Fisher (1981)) que para cada conjunto de multiplicadores, la solución de )) , (( µ λ LR verifica la siguiente relación: )),((max:)()( , ηλ µλLRvDLvPv=≥ Al problema )(DL se le conoce con el nombre de dual lagrangiano y puede ser resuelto mediante el algoritmo del subgradiente (ver Held et al. (1974)), para el cual proponemos el siguiente conjunto de multiplicadores iniciales: • tlj t jl ,, 0 ∀= λ . • { } tlidct il t ijl j t il ,, max ∀= µ . La resolución del problema dual nos permitirá obtener la máxima, o al menos una buena cota inferior de la solución de nuestro problema original. Sin embargo, por norma general, esta solución no será factible, es decir, no verificará las restricciones que fueron relajadas en el problema )(P por lo que, resolveremos el problema dual y una vez obtenida la mejor