Problema de ubicación de instalaciones en espacio continuo
Estoy revisando la literatura del problema de ubicación de instalaciones (FLP). Aquí, Daskin y Dean (2004) proporcionaron una breve literatura sobre FLP de espacio discreto, que fue útil para distinguir diferentes tipos de modelos con diferentes objetivos. Chopra y Meindl (2013) mostraron un pequeño ejemplo de un FLP sobre espacio continuo con una sola selección de instalaciones, al que llamaron modelo de ubicación por gravedad , en el libro titulado: "Gestión de la cadena de suministro: estrategia, planificación y operación".
Estoy en busca de un artículo de revisión o artículos selectos que formularon FLP en un espacio continuo con múltiples selecciones de instalaciones. Además, el problema se formuló con un modelo no lineal en Chopra y Meindl (2013) porque consideraron la distancia euclidiana entre un nodo de demanda y las posibles coordenadas de la instalación. ¿Alguna vez se ha encontrado con un documento que formula el problema con un modelo lineal? ¿Es esto posible?
Para describir mejor el problema, suponga que hay un conjunto de nodos de demanda de tamaño polinomial y nos gustaría ubicar las instalaciones para satisfacer completamente la demanda y minimizar los costos de las instalaciones y los servicios. Cada instalación tiene un rango de servicio circular y el costo de la instalación es el mismo en todas las ubicaciones. Dado que las instalaciones no tienen restricciones de capacidad y no hay ningún incentivo para satisfacer una parte de la demanda con otra instalación, podemos suponer que cada nodo de demanda será completamente atendido por la instalación más cercana, y no interesa encontrar las ramificaciones. Además, podemos suponer que la distancia euclidiana es el factor que prevalece en el cálculo del costo del servicio.
También estoy interesado en la versión de instalación discretamente espaciada del problema descrito anteriormente. En particular, estoy buscando algoritmos que puedan manejar la cobertura de hasta 2 millones de nodos de demanda en una cantidad razonable de tiempo computacional, digamos menos de un día. De lo contrario, los modelos presentados en Daskin y Dean (2004) brindan un esquema razonable sobre el cual construir.
Respuestas
El tipo de problemas de ubicación que está buscando son problemas de ubicación plana donde el problema de Weber y los problemas de Weber múltiple se encuentran entre los más conocidos (y más simples). Drezner brinda una buena descripción general del problema y un procedimiento de solución llamado "procedimiento de Weizfeld". Para el problema de Weber múltiple existe una heurística simple y bastante famosa llamada " heurística de asignación de ubicación de Cooper " (o algo por el estilo).
Sé que puede formular el problema de Weber múltiple como un programa entero mixto no lineal y como una diferencia de problema de optimización convexa. Pero no puede formularlo como un programa lineal (a menos que$\mathcal{P=NP}$) ya que es un$\mathcal{NP}$-Problema de optimización difícil.
Si lo entiendo correctamente, se le proporciona un conjunto de nodos de demanda y desea ubicar un número finito de instalaciones, en cualquier parte del plano, para minimizar la suma de distancias entre cada nodo de demanda y su instalación asignada.
Más allá de la literatura sobre problemas de ubicación de instalaciones, puede encontrar algunas herramientas útiles en los métodos de agrupación (p. ej., el algoritmo K-means y similares), así como los problemas del árbol de Steiner.
El algoritmo K-means calcula los conglomerados, donde se ubica el centroide de cada conglomerado para minimizar la suma de las distancias al cuadrado a los puntos del conglomerado. Una versión similar con distancias no cuadradas es el problema de la mediana p. Se han propuesto algunos enfoques basados en la generación de columnas para ambos; consulte, por ejemplo, este documento .
El problema del árbol de Euclides de Steiner no es exactamente el problema que está mencionando, pero puede haber algunos trucos de modelado útiles de esta literatura, por ejemplo, este artículo .