Solucionador de Localización de Instalaciones Online

Pseudocódigo

El problema equilibra dos costes que tiran en direcciones opuestas: abrir instalaciones cuesta dinero, pero cada instalación abierta acorta el trayecto hasta los clientes. La formulación exacta es un programa entero; en la práctica se usa una heurística voraz con mejora local.

// Exacto (pequeño): probar cada subconjunto de sitios
mejor = infinito
para cada subconjunto no vacío S de sitios candidatos:
    coste = suma de costeApertura[f] para f en S
    para cada cliente c:
        coste += min sobre f en S de costeServicio[f][c]
    mejor = min(mejor, coste)

// Voraz (grande): abrir la instalación que más ahorra
S = {}
repetir:
    f* = el sitio cerrado que más reduce el coste total
    si abrir f* no reduce el coste: parar
    S = S + {f*}

// Después: búsqueda local con intercambio, apertura y cierre

La clave es que los clientes siempre se asignan a la instalación abierta más barata para ellos, así que el único grado de libertad real es qué subconjunto abrir. Eso convierte un problema aparentemente continuo en uno combinatorio sobre subconjuntos, y es también lo que lo hace NP-difícil: hay 2 elevado a n subconjuntos y ninguna forma conocida de recorrerlos en tiempo polinómico.

Ejemplo resuelto, paso a paso

Decide qué instalaciones abrir con tres sitios candidatos y cuatro clientes, comparando todos los subconjuntos.

Grafo de ejemplo: Costes de apertura: F1 vale 10, F2 vale 8, F3 vale 6. Costes de servicio por cliente: F1 sirve a C1 y C2 por 2 y 3 pero a C3 y C4 por 9 cada uno; F2 sirve a C3 y C4 por 2 y 3 pero a C1 y C2 por 8 y 7; F3 sirve a los cuatro por 5 cada uno.

1. Abrir solo F1. Coste de apertura 10, más 2 + 3 + 9 + 9 de servicio, total 33. F1 es excelente para sus dos clientes cercanos y pésimo para los otros dos.
2. Abrir solo F2. Apertura 8, más 8 + 7 + 2 + 3, total 28. Es la imagen especular de F1.
3. Abrir F1 y F2. Apertura 10 + 8 = 18, y ahora cada cliente elige su mejor opción: 2 + 3 + 2 + 3 = 10 de servicio, total 28. Los costes de servicio son inmejorables, pero pagar dos aperturas se come toda la ventaja.
4. Abrir solo F3. Apertura 6, más 5 + 5 + 5 + 5 = 20 de servicio, total 26. F3 no es la mejor opción para ningún cliente concreto, y aun así gana.
5. Abrir las tres. Apertura 10 + 8 + 6 = 24, más 2 + 3 + 2 + 3 = 10, total 34. Abrir más instalaciones empeora el resultado.

El óptimo es abrir únicamente F3, con coste total 26. Merece la pena detenerse en esto: F3 no es la instalación preferida de ningún cliente, y sin embargo el subconjunto óptimo es exactamente esa. Una heurística que asignara cada cliente a su instalación de servicio más barato abriría F1 y F2 y llegaría a 28. El compromiso entre coste de apertura y coste de servicio es lo único que importa, y razonar cliente a cliente no lo captura.

Complejidad y de dónde sale

Tiempo: NP-difícil; exacto O(2^n · n · m) · Espacio: O(n · m)

Con n sitios candidatos y m clientes, la enumeración exacta prueba los 2 elevado a n subconjuntos no vacíos y, para cada uno, asigna los m clientes a su instalación abierta más barata en O(n) por cliente, lo que da O(2 elevado a n por n por m). Eso solo es practicable hasta unos 20 o 25 sitios. El problema es NP-difícil, así que no se espera un algoritmo polinómico exacto. La buena noticia es que la variante sin capacidades sí admite aproximación: existen algoritmos con factor constante en torno a 1,5 basados en redondeo de programación lineal y en búsqueda local, lo cual contrasta con la coloración de grafos, donde no se conoce ninguna aproximación decente. El voraz que abre en cada paso la instalación que más ahorra tiene garantía logarítmica y va bien en la práctica.

Cuándo usar Localización de Instalaciones y cuándo no

La variante correcta depende de si las instalaciones tienen límite de capacidad y de cuántos clientes hay.

Errores frecuentes

• Asignar clientes antes de decidir qué abrir. La asignación es trivial una vez fijado el conjunto abierto: cada cliente va a su instalación abierta más barata. Razonar al revés, eligiendo primero la instalación favorita de cada cliente, lleva a abrir de más, como muestra el ejemplo donde ese razonamiento da 28 frente al óptimo de 26.
• Suponer que abrir más instalaciones siempre ayuda. Abrir las tres del ejemplo cuesta 34, peor que abrir solo F3 con 26. Cada apertura añade un coste fijo que debe amortizarse con el ahorro en servicio, y con frecuencia no lo hace.
• Ignorar el límite de capacidad cuando existe. La variante sin capacidades permite que una instalación atienda a todos los clientes. Si en la realidad hay un tope de demanda, la solución óptima sin capacidades puede ser sencillamente inviable, y hace falta la formulación con capacidades.
• Usar distancia euclídea cuando el coste real no lo es. Los costes de servicio suelen incluir tiempo de conducción, peajes, franjas horarias o tarifas por zona. Sustituirlos por distancia en línea recta cambia el problema y a menudo la respuesta.
• Tratar el resultado como definitivo cuando la demanda varía. La localización de instalaciones es una decisión a largo plazo tomada con una previsión de demanda. Merece la pena comprobar si el subconjunto óptimo sigue siéndolo bajo demandas alternativas antes de construir nada.

Preguntas frecuentes

¿Qué es el problema de localización de instalaciones?

Dado un conjunto de emplazamientos candidatos con coste de apertura y un conjunto de clientes con coste de servicio desde cada emplazamiento, el problema pide qué instalaciones abrir para minimizar la suma del coste de apertura y el de servicio. Modela la ubicación de almacenes, la colocación de servidores, la planificación de redes comerciales y el emplazamiento de centros de datos.

¿Por qué es difícil la localización de instalaciones?

Porque la asignación de clientes es trivial una vez decidido qué abrir, así que todo el problema se reduce a elegir un subconjunto de emplazamientos. Con n candidatos hay 2 elevado a n subconjuntos y ninguna forma conocida de explorarlos en tiempo polinómico. El problema es NP-difícil, aunque la variante sin capacidades sí admite aproximación con factor constante.

¿Cuál es la diferencia entre localización con y sin capacidades?

Sin capacidades, una instalación abierta puede atender a cualquier número de clientes. Con capacidades, cada instalación tiene un límite de demanda, así que los clientes pueden verse obligados a acudir a una instalación más cara porque la más cercana ya está llena. La variante con capacidades es sensiblemente más difícil y sus soluciones son estructuralmente distintas.

¿Abrir más instalaciones reduce siempre el coste?

No. Cada apertura añade un coste fijo, y ese coste solo se justifica si el ahorro en servicio lo supera. En el ejemplo anterior abrir las tres instalaciones cuesta 34 mientras que abrir solo una cuesta 26. Ese equilibrio entre coste fijo y coste variable es la esencia del problema.

¿Cuál es la diferencia entre localización de instalaciones y k-medias?

K-medias divide los puntos en k grupos minimizando la distancia dentro de cada grupo, sin ningún coste de apertura y con k fijado de antemano. La localización de instalaciones decide cuántas instalaciones abrir y cuáles, equilibrando coste de apertura frente a coste de servicio. K-medias es un problema de agrupamiento; la localización es un problema de decisión económica.