Algoritmos para el problema de localización de plantas y centros de distribución maximizando beneficio

Algorithms for the problem of location of plants and distribution centers maximizing Benefit

Este artículo presenta un caso particular del problema de localización de instalaciones. La característica de este es que considera un conjunto de clusters que representan la acumulación de clientes que demandan un producto en particular. Se desea localizar P centros de distribución donde la demanda de los clusters se satisface solo si localizamos un centro de distribución en dicho cluster. Además, se debe determinar tanto el número de plantas como sus respectivas ubicaciones con el fin de abastecer los diferentes centros de distribución localizados. El objetivo es maximizar la utilidad considerando, por un lado, los ingresos que se obtienen por satisfacer la demanda de los diferentes clusters y, por otro lado, los costos de instalación que se incurren al localizar los centros de distribución y las plantas como también los costos de transporte de material desde las plantas a los centros de distribución. Otras aplicaciones de este problema se aprecian en redes de telecomunicaciones, redes eléctricas, etc. Se presenta un nuevo modelo de programación lineal entera que permite resolver instancias pequeñas, hasta 300 clusters, en un tiempo CPU aceptable, los problemas fueron programados con AMPL, y resueltos con CPLEX 11.0. Para instancias de mayor tamaño se presentan heurísticas que permiten obtener soluciones con un GAP menor al 1%.

INTRODUCCIÓN

El problema de localización de instalaciones consiste en decidir la ubicación de las instalaciones para satisfacer a los clientes maximizando las utilidades. Este problema ha sido tratado por muchos autores, quienes presentan diferentes tipos de modelos pero considerando la misma función objetivo: minimizar los costos de localización y de transporte. El problema de localización no capacitado, el que no considera la capacidad de las plantas y demandas de los clientes [4] tiene restricciones del tipo ∑y_ij =1, para todo i (1) y ∑y_ij≤ x_j, para todo j (2); donde la variable yij es la fracción de la demanda del cliente i satisfecha por la instalación J y la variable xj es 1 si se localiza una instalación en j. La restricción (1) estipula que la demanda del cliente i debe ser satisfecha en su totalidad y la restricción (2) estipula que la demanda del cliente i no puede ser satisfecha a partir de la instalación J si no se localiza dicha instalación. En [5] se incorporan adicionalmente al problema las restricciones de capacidad y demanda: ∑d_iy_ij ≤ s_j x_j, para todo j (3) donde sj es la capacidad de la instalación j y d_i es la demanda del cliente i. La restricción (3) asegura que cada planta no puede satisfacer la demanda más allá de su capacidad. En [9] el problema de localización de plantas capacitadas se compone solamente de las restricciones (1), (2) y (3).

En el problema de localización de p instalaciones capacitadas con condiciones globales [10], al objetivo de minimizar los costos de transporte entre las instalaciones y el costo de localización de estas, se agregan además los costos de producción y mano de obra.