Localización de plantas sin capacidades

Problema de cubrimiento

Supongamos que queremos instalar parques infantiles en una ciudad. Queremos minimizar los costos de instalación (apertura) de estos parques, bajo la condición de que ningún niño ha de estar a más de una distancia prefijada de algún parque.

Este problema respondería al siguiente modelado (donde los niños son los clientes y los parques las plantas). Las variables a considerar serían:

• \( x_{ij} \) = Variable de decisión binaria que toma valor 1 si la demanda del cliente \( j \) está cubierta por la planta \( i \) y 0 en caso contrario.
• \( y_i \) = Variable de decisión binaria que toma valor 1 se se abre la planta \( i \) y 0 en caso contrario.

Y tenemos los siguientes datos:

• \( d_{ij} \) = Distancia de la planta \( i \) al cliente \( j \).
• \( f_i \) = Costo de apertura de la planta \( i \).
• \( R \) = Distancia máxima prefijada de un cliente a una planta.

La función objetivo, al tratarse de minimizar costos de apertura, será:

\[ \min_{i=1}^n f_i y_i \]

Y para las restricciones:

1. Un cliente sólo podrá ir a una planta abierta. Es decir, las \( n \) primeras restricciones son: \[ \sum_{j=1} x_{ij} \le m y_i, \forall i \in I \]
2. Cada cliente ha de verse cubierto por al menos una planta. Luego, las siguientes n restricciones son:\[ \sum_{i=1}^n x_{ij} \ge 1, \forall j \in J \]
3. Ningún cliente ha de quedar a una distancia superior de \( R \) de alguna planta. Luego, las siguientes \( n \) restricciones son: \[ \sum_{i=1}^n x_{ij} d_{ij} \le R, \forall j \in J \]
   

Problema de cercanía

Este modelo intenta minimizar la máxima distancia que hay entre una planta abierta y los clientes a los que abastece. Un ejemplo sería ver en una ciudad qué centros de urgencias se abren de manera que ningún cliente que viva alejado del centro quede aislado.

Se definen las variables como:

• \( x_{ij} \) = Variable de decisión binaria que toma valor 1 si la demanda del cliente \( j \) está cubierta por la planta \( i \) y 0 en caso contrario.
• \( y_i \) = Variable de decisión binaria que toma valor 1 si se abre la planta \( i \) y 0 en caso contrario.

Para resolver el problema se dispone de los siguientes datos:

• \( c_{ij} \) = Costo de desplazamiento del cliente \( j \) a la planta \( i \).

Ahora tenemos una bifurcación del problema: considerando los costos de apertura, o sin tenerlos en cuenta.

Sin costos de apertura

En la función objetivo, las cantidades son distancias, y por tanto no podemos sumarlas directamente a los costos de apertura, por ello, no los tendremos en cuenta. El problema consiste en:

\[ \min_j \max_i \{ c_{ij} x_{ij} \} \]

Vamos a modelizar este problema como un problema de programación lineal. Para ello definimos una variable auxiliar:

• \( r \) = coste máximo a minimizar.

Luego nuestra función objetivo quedaría:

\[ \min r \]

Y para las restricciones:

1. Cada cliente ha de verse cubierto por una y sólo una planta. Luego, las \( m \) primeras restricciones son: \[ \sum_{i=1}^n x_{ij} = 1, \forall j \in J \]
2. Sólo se abrirá una planta en el caso de que sea necesario para un cliente, luego y \( i \) no puede valer 0 si algún \( x_{ij} \) vale 1. Es decir, las \( m \times n \) restricciones siguientes son: \[ x_{ij} \le y_i, \forall i \in I, j \in J \]
3. Como hemos llamado \( r \) a la máxima distancia, la última restricción sería: \[ \sum_{i=1}^n c_{ij} x_{ij} \le r, \forall j \in J \]

Por lo que finalmente, nuestro PPL quedará:

Con costos de apertura

Para esta sección, necesitaremos los siguientes datos:

• \( f_i \) = Costos de apertura de la planta \( i \)
  

En este caso fijaremos el costo máximo de apertura de las plantas (que denotaremos por \( F \) ) y el mínimo de centros a abrir (que llamaremos \( K \) ). Para que el problema tenga sentido, al menos \( K \) centros han de tener costo de apertura inferior a \( F\).

Ahora, nuestro problema consistirá en minimizar la mayor distancia de los usuarios a cada planta, para que todos estén lo más cerca posible de, al menos, una planta. Seguimos considerando las variables:

• \( x_{ij} \) = Variable de decisión binaria que toma valor 1 si la demanda del cliente \( j \) está cubierta por la planta \( i \) y 0 en caso contrario.
• \( y_i \) = Variable de decisión binaria que toma valor 1 si se abre la planta \( i \) y 0 en caso contrario.

Y los datos:

• \( c_{ij} \) = Costo de desplazamiento del cliente \( j \) a la planta \( i \). Emplearemos indistintamente distancia y costo de desplazamiento, es decir, cuando nos refiramos a distancia, también hablamos de los \( c_{ij} \).
  

Podemos afrontar este problema de varias formas:

1. Buscando para cada cliente el centro más cercano y miniminizar esta distancia. En este caso, la solución óptima consistiría en elegir el centro más cercano a cada cliente, y abrirla. Esto es, abrir la planta resultante del \( \min_i \min_j c_{ij} x_{ij} \) . Este problema no nos resulta interesante.
2. En el caso de estar, por ejemplo, ante plantas consideradas como ”peligrosas” para la población, como alguna central nuclear o fábrica que vierta residuos tóximos, nos convendría máximizar el máximo de la distancia de cada planta a cada cliente. Es decir, \( \max_i \max_j c_{ij} x_{ij} \). Este problema sería análogo al caso anterior, por lo que tampoco vamos a desarrollarlo.
3. Eligiendo la planta más lejana a cada cliente y minimizando esta distancia, es decir, \( \min_j \max_i c_{ij} x_{ij} \). ¿Tendría sentido tener en cuenta que todos los clientes visiten todas las plantas? En este caso si. Por ejemplo, si consideramos \( n \) bares, siendo cada bar, un cliente, y \( m \) mayoristas (uno de refrescos, otro de cerveza, otro de embutidos...), siendo cada mayorista, una planta, es claro que cada bar necesita visitar cada mayorista por que necesita abastecimiento de todas ellas.
4. Considerando lo contrario al anterior. Para cada cliente vemos el centro más cercano y ”lo alejamos”. Esto sería, \( \max_j \min_i c_{ij} x_{ij} \) . En este caso estaríamos hablando también de plantas con residuos tóxicos, vertederos, etc.
5. Eligiendo aquellos centros que tengan a todos los clientes lo más cerca posible (minimiza la distancia del cliente que más alejado está). Esto sería, \( \min_i \max_j c_{ij} x_{ij} \). Lo que sería análogo a, en el caso 3, intercambiar el papel de plantas y clientes.
6. Escogiendo los centros que tengan a algún cliente lo más lejos posible (máximiza la distancia del cliente más cercano). Sería \( \max_i \min_j c_{ij} x_{ij} \). Lo que sería análogo a, en el caso 4, intercambiar el papel de plantas y clientes.

Y en todos estos casos, las restricciones a considerar serían:

• Cada cliente ha de verse cubierto por al menos una planta. Luego, las \( m \) primeras restricciones son: \[ \sum_{i=1}^n x_{ij} \ge 1, \forall j \in J \]
• Que haya, al menos, \( k \) plantas abiertas: \[ \sum_{i=1}^n \ge k \]
• Que los costos de apertura no superen al prefijado: \[ f_i y_i \le F, \forall i \in I \]
• Sólo se abrirá una planta en el caso de que sea necesario para un cliente: \[ x_{ij} \le y_i, \forall i \in I, j \in J \]