El problema de la localización en Logística

El problema de la localización de instalaciones

Todos estamos familiarizados con el problema de la distribución, ya sea media o larga distancia o incluso última milla y la necesidad de consolidar la mercancía en centros logísticos como paso intermedio entre los puntos de fabricación y los puntos de demanda final: Tenemos un conjunto de clientes (nodos) que debemos visitar para entregar o recoger ciertos bienes (figura de la izquierda) y estas demandas se satisfacen desde uno o varios centros logísticos. Son varias las cuestiones a resolver:

  1. ¿Cuántos centros logísticos instalamos?
  2. ¿Dónde los localizamos? Y ¿con qué capacidad?
  3. ¿Qué beneficios tanto para el operador logístico como para los clientes finales existen entre instalar 1, 2 o más?
  4. ¿Qué criterios de optimización usamos? ¿Distancia media, distancia máxima, cobertura…? O, ¿podemos responder a las cuestiones anteriores usando un modelo/criterio de costes (además del coste asociado al transporte, existe un coste fijo adicional por cada centro logístico que usamos/instalamos)?

Antes de ver el enfoque metodológico, es importante resaltar otros escenarios donde surgen problemas de localización muy comunes y cruciales:

  • Localización de estaciones, por ejemplo, de bicicleta para un nuevo sistema, de metro, para una nueva red o ampliación de otra existente. A partir de un conjunto amplio de localizaciones candidatas y dependiendo del presupuesto disponible, nos preguntamos ¿cuáles son las 25, 50 ó 100 mejores localizaciones para las estaciones de bici?
  • Localización de hospitales, comisarías, colegios.
  • Localización de tiendas o centros comerciales.
  • Localización de vertederos, incineradoras, puntos de reciclaje o similares.
  • Localización de lockers donde dejar y recoger paquetes.
  • Localización de puntos de recarga de vehículos eléctricos o drones.

El problema de la p-mediana

DEFINICIÓN. El problema de localización de plantas, también conocido como facility location problem, se ocupa de la colocación óptima de las instalaciones para minimizar, por ejemplo, los costes de transporte teniendo en cuenta otros factores o restricciones (por ejemplo, evitar la colocación de materiales peligrosos cerca de las viviendas o de otros competidores).

El problema es por tanto determinar las mejores p localizaciones entre un conjunto de localizaciones candidatas. En esta ocasión se requieren las siguientes variables:

  • Variables:
El problema de la p mediana. Variables
 
 

Estos problemas son de OPTIMIZACIÓN LINEAL ENTERA y, debido al carácter binario (xi∈{0,1}) de las variables de decisión, son, computacionalmente hablando, NP-duros. Esto significa que la complejidad de éstos aumenta a un ritmo exponencial en función del tamaño del problema. Por este motivo, la obtención de la solución óptima no es tarea fácil cuando el problema es grande.

Variantes del problema clásico

  • El problema del p-centro o minmax, cuando debemos determinar las mejores p localizaciones entre un conjunto de localizaciones candidatas que minimice la máxima de las distancias, es decir, dejar lo mejor colocado posible al nodo más alejado de todos.
  • El problema p-next center. Este problema es una extensión o variante del p-center en el que se desea minimizar la distancia al segundo nodo más cercano. Este problema, es de gran interés en situación de catástrofe donde alguno de los nodos claves (hospital por ejemplo) queda inhabilitado y la distancia que debían recorrer los habitantes para llegar a éste ya no es tal, sino que ahora recorren la distancia al segundo hospital más cercano.
  • El problema maximin. El problema de localización maximin busca las ubicaciones que maximicen la distancia mínima a los clientes (pues localizamos, por ejemplo, un vertedero).
  • El problema con capacidades. Si nos enfrentamos ante un problema de la p-mediana pero los nodos/clientes poseen unas demandas H={h1,…,hn} y cada planta tiene una capacidad máxima C, añadimos ciertas restricciones que nos garanticen dicha demanda.
  • El problema de la cobertura. Problema de la localización de un conjunto de, por ejemplo, estaciones de bicicleta maximizando la cobertura a los ciudadanos.

Analicemos un ejemplo

Finalicemos el post con una tabla comparativa de distancias medias (p-mediano) y máximas (p-center) para un problema simulado de 50 nodos en la provincia de Jaén que queremos sean servidos desde p centros logísticos elegidos entre esas mismas 50 localizaciones:

Ejemplo problema simulado 50 nodos

Los resultados de 8 simulaciones para p = 1, 2, 3 y 5 centros logísticos, tanto para el enfoque p-mediano como el p-center son los siguientes (en negrita los valores que el algoritmo ha minimizado):

EnfoqueMedia (km)Max (km)
1-mediano2458,249136,596
2-mediano1595,22099,420
3-mediano1190,15499,415
5-mediano799,09050,582
1-centro o minmax2796,36199,415
2-centro o minmax1777,90174,632
2-centro o minmax1409,06157,184
5-centro o minmax969,63339,725

Así, si deseamos minimizar la distancia media recorrida por la flota, se aprecia un ahorro en esta distancia media entre localizar un solo centro (1-mediano) y localizar 5 centros (5-mediano) del 67,49 %. O simplemente un ahorro del 35,11 % entre localizar 1 o 2 centros logísticos. Vemos además que se recomienda localizar en la zona de Linares para un solo centro o en Úbeda y Andújar para 2 centros.

Pero, en las imágenes anteriores ¿no hay clientes excesivamente lejos de los centros logísticos? En efecto, para un centro hay clientes hasta a 136,596 km. Pues bien, si nos centramos en minimizar la máxima de las distancias (enfoque del p-center) se aprecia un ahorro en esta distancia media entre el 1-center y el 5-center del 60,04 % (de 99,415 km a 39,725 km). O un ahorro del 24,93 % entre localizar 1 o 2 centros logísticos, localizando en la zona de Úbeda para un solo centro o localizando en Jaén y Villacarrillo para 2 centros, de forma que los nodos más alejados estén lo más cerca posible (sacrificando, como se puede ver en la tabla, las distancia media).

Localización de antenas

Nuestro compañero Víctor Berrocal ha trabajado anteriormente en este problema para la localización de antenas de telecomunicaciones. Por su complejidad, propuso un algoritmo de tipo ABC (Artificial Bee Colony algorithm). Aquí os dejamos la referencia y un par de imágenes de las soluciones propuestas:

  • Berrocal-Plaza, V., Vega-Rodríguez, M. A., Gómez-Pulido, J. A., & Sánchez-Pérez, J. M. (2011, November). Artificial bee colony algorithm applied to WiMAX network planning problem. In 2011 11th International Conference on Intelligent Systems Design and Applications (pp. 504-509). IEEE.
Artificial bee colony algorithm applied to WiMAX network planning problem. Victor Berrocal

Si se ha enfrentado a este problema anteriormente, ha trabajado con otros enfoques, desea conocer las heurísticas más utilizadas en OGA para resolverlo o cualquier otra cuestión, no dude en contactarnos.

Acerca del autor

Autor
Alfredo García oga
Alfredo García
Senior Optimization Consultant en oga

Catedrático en la Universidad Pablo de Olavide (UPO) y Doctor en Matemáticas por la Universidad de Sevilla. Senior Optimization Consultant​ en oga.

Apasionado de la Matemática, como ciencia fundamental, pero sobre todo de la Matemática Aplicada. Lo que más le motiva es la resolución de problemas reales y es por ello que, tras más de 20 años de experiencia, ha trabajado en Matemáticas Puras, Investigación Operativa, Optimización Multiobjetivo, Computación Evolutiva y finalmente en Machine Learning y Business Analytics.