Ubicación óptima de las instalaciones

La localización óptima de instalaciones (OFL, por sus siglas en inglés) , también llamada análisis de localización , ^{[ 1 ]} es una clase de problema de optimización.En todos estos problemas, el objetivo es decidir dónde ubicar alguna instalación (por ejemplo, una escuela, una gasolinera, una fábrica, etc.) de manera que se optimicen ciertos criterios preestablecidos. Algunos ejemplos son:

"Decidir dónde ubicar una nueva escuela, teniendo en cuenta la ubicación de los estudiantes, de manera que la suma de los costos diarios de transporte de todos los estudiantes a la escuela sea lo más pequeña posible."
"Decidir dónde ubicar una nueva fábrica, teniendo en cuenta la ubicación de los ciudadanos, de manera que la distancia mínima entre la fábrica y la casa de un ciudadano sea lo mayor posible".

La OFL se estudia en la investigación operativa , la geometría computacional (una rama de la informática) y la teoría de la localización (una rama de la economía). Algunas técnicas utilizadas para la OFL también se aplican al análisis de clústeres .

Existen diversos tipos de problemas OFL. Se diferencian en su función objetivo (por ejemplo, suma de distancias o distancia mínima), en la dirección de optimización (maximización frente a minimización), en el número de instalaciones (una frente a muchas) y más.

Localización utilitaria: minimizar la suma de las distancias.

Un problema de localización de instalaciones de suma mínima es un problema de localización de instalaciones operativas (OFL) en el que la entrada es un conjunto de puntos en el espacio, y el objetivo es encontrar una ubicación para una instalación, de manera que la suma de las distancias entre la instalación y los puntos sea lo más pequeña posible. Si los puntos corresponden a personas y las distancias corresponden a su desutilidad (el costo que incurren al viajar a una instalación lejana), entonces el problema de localización de instalaciones de suma mínima es una instanciación de la regla utilitarista . Algunos casos especiales son:

Si solo hay 3 puntos de entrada, la solución es su punto de Fermat del triángulo.
Si hay n puntos, la solución es su mediana geométrica .
El problema de Weber es una generalización en la que cada punto de entrada tiene un peso, y el objetivo es minimizar la suma ponderada de las distancias. ^{[ 2 ]}^{[ 3 ]}

En su forma más general, puede haber múltiples instalaciones, pero cada una tiene un costo de construcción. El objetivo es seleccionar un subconjunto de instalaciones para abrir, minimizando la suma de las distancias desde cada punto de demanda hasta su instalación más cercana , más la suma de los costos de construcción de las instalaciones. ^{[ 4 ]} Otra formulación común limita el número de instalaciones a un entero fijo k en lugar de asignarles un costo. ^{[ 5 ]}

El problema de localización de instalaciones con suma mínima en grafos generales es NP-difícil de resolver de forma óptima, mediante reducción a partir de (por ejemplo) el problema de cobertura de conjuntos . Se han desarrollado varios algoritmos de aproximación para el problema de localización de instalaciones y muchas de sus variantes.

Sin suposiciones sobre el conjunto de distancias entre clientes y sitios (en particular, sin suponer que las distancias satisfacen la desigualdad triangular ), el problema se conoce como localización de instalaciones no métricas y puede aproximarse con un factor O(log n ). ^[⁴^] Este factor es ajustado, mediante una reducción que preserva la aproximación a partir del problema de cobertura de conjuntos.

Si asumimos que las distancias entre clientes y sitios no son dirigidas y satisfacen la desigualdad triangular, hablamos de un problema de localización de instalaciones métricas (MFL) . El MFL sigue siendo NP-difícil y difícil de aproximar con un factor mejor que 1,463. ^{[ 6 ]} El mejor algoritmo de aproximación conocido actualmente alcanza una razón de aproximación de 1,488. ^{[ 7 ]}

Ubicación igualitaria: Minimizar la distancia máxima

Un problema de localización de instalaciones minimax es un problema de localización de instalaciones operativas (OFL) en el que la entrada es un conjunto de puntos en el espacio, y el objetivo es encontrar una ubicación para una instalación, de manera que la distancia máxima entre la instalación y cualquiera de los puntos sea lo más pequeña posible. Si los puntos corresponden a personas y las distancias corresponden a su desutilidad, entonces el OFL minimax es una instanciación de la regla igualitaria . Algunos casos especiales son:

En el caso de la métrica euclidiana para $k = 1$ (una instalación) en el plano, se conoce como el problema del círculo más pequeño que lo encierra .
Para una instalación en el espacio tridimensional, se conoce como el problema de la esfera envolvente más pequeña o problema de 1 centro . Su estudio se remonta al menos al año 1860.
El problema general con k instalaciones, en un espacio métrico general, se llama k-centro métrico .

La variante de múltiples instalaciones se puede definir formalmente de la siguiente manera:

Dado un conjunto de puntos $\mathbb {R} ^{d}$ ,
encontrar un conjunto de puntos $\mathbb {R} ^{d}$
de modo que
$max p \in P (min q \in S (d(p, q)) )$ se minimiza. ^{[ 5 ]}

dureza NP

La solución exacta del problema del k -centro es NP-difícil. ^{[ 8 ]}^{[ 9 ]}^{[ 10 ]} Se encontró que la aproximación al problema también es NP-difícil cuando el error es pequeño. El nivel de error en el algoritmo de aproximación se mide como un factor de aproximación, que se define como la razón entre la aproximación y el óptimo. Se ha demostrado que la aproximación del problema del k -centro es NP-difícil cuando el factor de aproximación es menor que 1,822 (dimensión = 2) ^{[ 11 ]} o 2 (dimensión > 2). ^{[ 10 ]}

Algoritmos

solucionador exacto

Existen algoritmos para producir soluciones exactas a este problema. Un solucionador exacto se ejecuta en tiempo $n^{O({\sqrt {k}})}$ . ^{[ 12 ]}^{[ 13 ]}

aproximación 1 + ε

La aproximación 1 + ε consiste en encontrar una solución con un factor de aproximación no mayor que 1 + ε . Esta aproximación es NP-difícil ya que ε es arbitrario. Se propone un enfoque basado en el concepto de coreset con una complejidad de ejecución de $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ . ^{[ 14 ]} Como alternativa, también está disponible otro algoritmo basado en conjuntos centrales. Se ejecuta en $O(k^{n})$ . ^{[ 15 ]} El autor afirma que el tiempo de ejecución es mucho menor que el del peor caso y, por lo tanto, es posible resolver algunos problemas cuando k es pequeño (por ejemplo, k < 5).

Agrupamiento de puntos más alejados

Debido a la complejidad del problema, es impracticable obtener una solución exacta o una aproximación precisa. En cambio, se suele utilizar una aproximación con factor = 2 para casos de k grande . Esta aproximación se conoce como algoritmo de agrupamiento de puntos más alejados (FPC) o recorrido primero del más alejado . ^[¹⁰^] El algoritmo es bastante simple: se elige cualquier punto del conjunto como centro; se busca el punto más alejado del conjunto restante como otro centro; se repite el proceso hasta encontrar k centros.

Es fácil ver que este algoritmo se ejecuta en tiempo lineal. Dado que se ha demostrado que la aproximación con un factor menor que 2 es NP-difícil, FPC se consideró la mejor aproximación posible.

En cuanto al rendimiento de la ejecución, la complejidad temporal se mejora posteriormente a O( n log k ) con la técnica de descomposición en cajas. ^[¹¹^]

Maximizar la distancia mínima

El problema de localización de instalaciones maximin , también conocido como problema de localización de instalaciones problemáticas , busca una ubicación que maximice la distancia mínima a los puntos de entrada. Es otra implementación de la regla igualitaria , que supone que la utilidad de cada agente es una función creciente de la distancia a la instalación problemática.

En el caso de la métrica euclidiana, se conoce como el problema de la esfera vacía más grande .
El caso planar de una sola instalación ( problema del círculo vacío más grande ) puede resolverse en tiempo óptimo Θ ( n log n). ^{[ 16 ]}^{[ 17 ]}

Formulaciones de programación entera

Los problemas OFL a menudo se resuelven como programas enteros , planteados de la siguiente manera: supongamos que hay $n$ instalaciones y $m$ clientes. Deseamos elegir (1) cuál de los $n$ instalaciones que abrir, y (2) qué instalaciones (abiertas) utilizar para abastecer el $m$ clientes, con el fin de satisfacer una demanda fija al mínimo coste. Introducimos la siguiente notación: sea $f_{i}$ denota el costo (fijo) de apertura de la instalación $i$ , para $i=1,\dots ,n$ . Dejar $c_{ij}$ denota el costo de enviar un producto desde la instalación $i$ al cliente $j$ para $i=1,\dots ,n$ y $j=1,\dots ,m$ . Dejar $d_{j}$ denota la demanda del cliente $j$ para $j=1,\dots ,m$ Supongamos además que cada instalación tiene una producción máxima. Sea $u_{i}$ denota la cantidad máxima de producto que puede producir la instalación $i$ , es decir, dejemos $u_{i}$ denota la capacidad de la instalación $i$ . El resto de esta sección sigue ^{[ 18 ]} .

Ubicación de la instalación con capacidad limitada

En nuestra formulación inicial, introducimos una variable binaria. $x_{i}$ para $i=1,\dots ,n$ , dónde $x_{i}=1$ si la instalación $i$ está abierto y $x_{i}=0$ De lo contrario, introduzca además la variable. $y_{ij}$ para $i=1,\dots ,n$ y $j=1,\dots ,m$ que representa la fracción de la demanda $d_{j}$ llenado por instalación $i$ El llamado problema de localización de instalaciones con capacidad limitada viene dado entonces por ${\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{st}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ para todo }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ para todo }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ para todo }}i=1,\dots ,n{\text{ y }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ para todo }}i=1,\dots ,n\end{array}}$

Tenga en cuenta que el segundo conjunto de restricciones garantiza que si $x_{i}=0$ , es decir, instalación $i$ no está abierto, entonces $y_{ij}=0$ a pesar de $j$ , es decir, ninguna demanda de ningún cliente puede ser satisfecha desde la instalación. $i$ .

Ubicación de la instalación no incapacitada

Un caso común del problema de localización de instalaciones con capacidad anterior es el caso en el que $u_{i}=+\infty$ a pesar de $i=1,\dots ,n$ En este caso, siempre es óptimo satisfacer toda la demanda del cliente. $j$ desde la instalación abierta más cercana. Debido a esto, podemos reemplazar las variables continuas. $y_{ij}$ desde arriba con las variables binarias $z_{ij}$ , dónde $z_{ij}=1$ si el cliente $j$ es suministrado por la instalación $i$ , y $z_{ij}=0$ De lo contrario, el problema de localización de instalaciones sin restricciones de capacidad viene dado por: ${\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}$

dónde $M$ es una constante elegida para que sea suficientemente grande. La elección de $M$ puede afectar los resultados de los cálculos; la mejor opción en este caso es obvia: tomar $M=m$ . Entonces, si $x_{i}=1$ cualquier elección de la $z_{ij}$ cumplirá con el segundo conjunto de restricciones.

Otra posibilidad de formulación para el problema de ubicación de instalaciones sin restricciones de capacidad es desagregar las restricciones de capacidad (las grandes- $M$ restricciones). Es decir, reemplace las restricciones $\sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n$ con las restricciones $z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m$ En la práctica, esta nueva formulación funciona significativamente mejor, en el sentido de que tiene una relajación de programación lineal más ajustada que la primera formulación. ^{[ 18 ]} Nótese que al sumar las nuevas restricciones se obtiene la gran restricción original. $M$ restricciones. En el caso con capacidad limitada, estas formulaciones no son equivalentes. Puede encontrar más información sobre el problema de localización de instalaciones sin capacidad limitada en el Capítulo 3 de "Teoría de la localización discreta". ^{[ 19 ]}

ubicaciones Pareto-eficientes

En lugar de encontrar una ubicación que optimice un único objetivo, uno puede estar interesado en encontrar todas las ubicaciones que puedan ser óptimas para algún objetivo. Esto se define formalmente de la siguiente manera. Sea X un espacio normado con norma |.|. Sea A un subconjunto no vacío de X. Un punto x en X se llama ---

Estrictamente eficiente con respecto a A si para todo y ≠ x existe un a en A que está más cerca de x que de y (|ax| < |ay|). Equivalentemente: ^{[ 20 ]}^{: Prop.1.1} la intersección (para todo a en A) de Ball(a,|xa|) es el singleton {x}.
Eficiente con respecto a A si para todo y ≠ x existe un a en A que está más cerca de x que de y (|ax| < |ay|), o todos los a en A están al menos tan cerca de x como de y (|ax| ≤ |ay|). Equivalentemente: la intersección (para todo a en A) de Ball(a,|xa|), interseca la unión (para todo a en A) de interior(Ball(a,|xa|)), es vacía.
Débilmente eficiente con respecto a A si para todo y ≠ x existe un a en A que está al menos tan cerca de x como de y (|ax| ≤ |ay|). Equivalentemente: la intersección (para todo a en A) de interior(Ball(a,|xa|)) es vacía.

Estos conceptos se basan en considerar que cada punto en A representa la ubicación de un agente, y los puntos x e y son ubicaciones potenciales para una instalación. Cada agente prefiere que la instalación esté lo más cerca posible de su propia ubicación. Con esta interpretación, la eficiencia y la eficiencia débil corresponden a las nociones económicas de eficiencia de Pareto y eficiencia débil de Pareto, respectivamente.

Toda ubicación que minimice la suma de distancias, o la suma ponderada de distancias, es eficiente con respecto a los puntos de entrada. Toda ubicación que minimice la distancia máxima es débilmente eficiente con respecto a los puntos de entrada.

Estos conceptos de eficiencia satisfacen las siguientes propiedades para cada norma: ^{[ 20 ]}^{: Prop.1.2}

Si A es acotado, entonces los conjuntos de puntos estrictamente eficientes, eficientes y débilmente eficientes también son acotados.
Si A es un subconjunto de B, entonces la misma relación de contención se cumple entre los conjuntos de puntos estrictamente eficientes y el conjunto de puntos débilmente eficientes, pero no entre los conjuntos de puntos eficientes.
Los conjuntos de puntos estrictamente eficientes y eficientes son cerrados bajo la propiedad de cierre, pero el conjunto de puntos débilmente eficientes no lo es.

Con ciertas suposiciones sobre la norma, se satisfacen propiedades adicionales: ^{[ 20 ]}^{: Prop.1.3}

Si X es un espacio normado estrictamente convexo , entonces los tres conceptos de eficiencia son equivalentes.
Si X es un espacio de Hilbert (por ejemplo, cuando la norma es la norma L2), entonces para los tres conceptos de eficiencia, el conjunto de puntos que los satisfacen es la envoltura convexa cerrada de A.
Si X es bidimensional y estrictamente convexo, y A es acotado, entonces para los tres conceptos de eficiencia, el conjunto de puntos que los satisfacen es la envoltura convexa cerrada de A.
Si A es un conjunto compacto, entonces su conjunto de puntos débilmente eficientes es cerrado. Además, si X es estrictamente convexo, bidimensional o poliédrico, entonces sus conjuntos de puntos eficientes y puntos estrictamente eficientes son cerrados. ^{[ 20 ]}^{: Teorema 1.1, Cor. 2.1}

Un espacio normado es estrictamente convexo si y solo si, para cada conjunto A de tamaño 2, todos los puntos en conv(A) son estrictamente eficientes con respecto a A. ^{[ 21 ]}

Un espacio normado bidimensional es estrictamente convexo si y solo si, para cada subconjunto compacto A de X, todos los puntos en conv(A) son estrictamente eficientes con respecto a A. ^{[ 20 ]}^{: Cor.4.2} Para tres dimensiones, hay un contraejemplo basado en alguna métrica en un cilindro.

Historia

La historia del problema de localización se remonta generalmente al problema de Weber y sus formulaciones paralelas. ^{[ 22 ]} Alfred Weber planteó el problema de la siguiente manera: Deseamos encontrar la ubicación en un plano euclidiano para que una empresa se ubique, de manera que se minimice la distancia en toneladas-kilómetro y, por lo tanto, el costo del transporte de sus mercancías. Esta empresa envía y recibe mercancías desde tres ubicaciones fijas en proporciones fijas que se desplazan en línea recta. ^{[ 23 ]} Si bien este problema puede no haber sido novedoso, marca el inicio de su uso práctico. ^{[ 22 ]}

En 1957 ^{[ 24 ]} y 1962 ^{[ 25 ]} se formularon los primeros algoritmos para variaciones del problema de Weber con más de 3 puntos para que la instalación realizara la entrega (aunque el trabajo previo de E. Weiszfeld en 1937 puede interpretarse como hacer algo similar sin el contexto de Weber ^{[ 26 ]} ). Anteriormente, solo los métodos mecánicos, como un marco de Varignon , podían resolver estos problemas. ^{[ 25 ]}^{[ 24 ]}^{[ 22 ]} Al mismo tiempo, se estaba trabajando en el desarrollo y la resolución del problema minimax, que en lugar de considerar la distancia total recorrida considera la comunidad más afectada, escalada. ^{[ 27 ]}^{[ 28 ]}

En la década de 1970, en respuesta a la preocupación por los efectos locales de ciertas instalaciones derivados de la Primavera Silenciosa , se desarrollaron modelos de instalaciones problemáticas. El objetivo de estos modelos es opuesto al del modelo convencional: en lugar de mantener las instalaciones lo más cerca posible de las comunidades, buscan maximizar la distancia para minimizar el impacto que estas instalaciones tienen en las comunidades. ^{[ 29 ]}^{[ 30 ]}^{[ 31 ]}

Aplicaciones

Cuidado de la salud

En el ámbito sanitario, las decisiones erróneas sobre la ubicación de las instalaciones tienen un grave impacto en la comunidad, más allá de los simples indicadores de coste y servicio; por ejemplo, es probable que las instalaciones sanitarias de difícil acceso se asocien con un aumento de la morbilidad y la mortalidad. Desde esta perspectiva, la modelización de la ubicación de las instalaciones sanitarias es más crucial que la modelización similar en otros ámbitos. ^{[ 32 ]}

Gestión de residuos sólidos

La gestión de residuos sólidos urbanos sigue siendo un desafío para los países en desarrollo debido al aumento de la producción de residuos y a los altos costos asociados a su gestión. Mediante la formulación y resolución precisa de un problema de ubicación de instalaciones, es posible optimizar la ubicación de los vertederos para la eliminación de residuos. ^{[ 33 ]}

Agrupamiento

Un subconjunto particular de problemas de análisis de clústeres puede considerarse como un problema de localización de instalaciones. En un problema de agrupamiento basado en centroides, el objetivo es particionar $n$ puntos de datos (elementos de un espacio métrico común ) en clases de equivalencia —a menudo llamadas colores— de tal manera que los puntos del mismo color estén cerca unos de otros (equivalentemente, de tal manera que los puntos de diferentes colores estén lejos unos de otros). ^{[ 34 ]}

Para ver cómo se podría considerar (léase "transformar" o "reducir") un problema de agrupamiento basado en centroides como un problema de localización de instalaciones (métricas), considere cada punto de datos del primero como un punto de demanda en el segundo. Suponga que los datos que se van a agrupar son elementos de un espacio métrico. $M$ (por ejemplo, dejar $M$ ser $p$ Espacio euclidiano de -dimensiones para algún fijo $p$ ). En el problema de ubicación de instalaciones que estamos construyendo, permitimos que las instalaciones se coloquen en cualquier punto dentro de este espacio métrico. $M$ Esto define el conjunto de ubicaciones de instalaciones permitidas. $L$ Definimos los costos $c_{\ell ,d}$ ser las distancias por pares entre pares de puntos de ubicación-demanda (por ejemplo, ver métrica k-centro ). En un problema de agrupamiento basado en centroides, se dividen los datos en $k$ clases de equivalencia (es decir, colores), cada una de las cuales tiene un centroide. Veamos cómo una solución a nuestro problema de ubicación de instalaciones construido también logra dicha partición. Una solución factible es un subconjunto no vacío. $L'\subseteq L$ de $k$ ubicaciones. Estas ubicaciones en nuestro problema de ubicación de instalaciones comprenden un conjunto de $k$ centroides en nuestro problema de agrupamiento basado en centroides. Ahora, asigne cada punto de demanda. $d$ a la ubicación $\ell ^{*}$ que minimiza su costo de servicio; es decir, asignar el punto de datos $d$ al centroide $\ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}$ (resolver empates arbitrariamente). Esto logra la partición siempre que los costos del problema de ubicación de instalaciones $c_{\ell ,d}$ se definen de tal manera que son las imágenes de la función de distancia del problema de agrupamiento basado en centroides.

El popular libro de texto sobre algoritmos Algorithm Design ^{[ 35 ]} proporciona una descripción del problema relacionado y un algoritmo de aproximación. Los autores se refieren al problema de localización de instalaciones métricas (es decir, el problema de agrupamiento basado en centroides o el problema métrico). $k$ -problema del centro) como el problema de selección del centro , ampliando así la lista de sinónimos.

Además, observe que en nuestra definición anterior del problema de localización de instalaciones la función objetivo $f$ es general. Opciones específicas de $f$ dan lugar a diferentes variantes del problema de localización de instalaciones y, por lo tanto, a diferentes variantes del problema de agrupamiento basado en centroides. Por ejemplo, se podría optar por minimizar la suma de las distancias desde cada ubicación a cada uno de sus puntos de demanda asignados (al estilo del problema de Weber ), o se podría optar por minimizar el máximo de todas esas distancias (al estilo del problema de 1 centro ).

Véase también

Referencias

↑ Eiselt, HA; Marianov, Vladimir (2011). "1.1 Desarrollos pioneros en el análisis de localización, problemas de localización: su planteamiento, sus componentes y su aplicación". Fundamentos del análisis de localización . Springer. pp. 3–6 . doi : 10.1007/978-1-4419-7572-0 . ISBN 978-1-4419-7571-3.
↑ Marianov, Vladimir; Serra, Daniel (2011). "3.1 Problemas de mediana en redes, Introducción". Fundamentos del análisis de localización . Springer. pp. 31–43 . doi : 10.1007/978-1-4419-7572-0 . ISBN 978-1-4419-7571-3.
↑ Drezner, Zvi; Simchi-Levi, David (diciembre de 1992). "Comportamiento asintótico del problema de localización de Weber en el plano" . Annals of Operations Research . 40 : 163–172 . doi : 10.1007/BF02060475 – vía Springer Nature Link.
1 2 Hochbaum, DS (1982). "Heurísticas para el problema de la mediana de costo fijo". Programación matemática . 22 : 148–162 . doi : 10.1007/BF01581035 . S2CID 3451944 .
1 2 Hansen, Pierre; Peeters, Dominique; Richard, Denis; Thisse, Jacques-Francois (noviembre de 1985). "Los problemas de localización Minisum y Minimax revisados" . Operations Research . 33 (6): 1251– 1265. doi : 10.1287/opre.33.6.1251 – vía Informs PubsOnLine.
↑ Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: Improved Facility Location Algorithms". Journal of Algorithms . 31 : 228–248 . CiteSeerX 10.1.1.47.2033 . doi : 10.1006/jagm.1998.0993 . S2CID 5363214 .
↑ Li, S. (2011). "Un algoritmo de aproximación 1,488 para el problema de localización de instalaciones sin restricciones de capacidad". Autómatas, lenguajes y programación . LNCS . Vol. 6756. pp. 77–88 . CiteSeerX 10.1.1.225.6387 . doi : 10.1007/978-3-642-22012-8_5 . ISBN 978-3-642-22011-1.
↑ Fowler, RJ; Paterson, MS; Tanimoto, SL (1981), "El empaquetamiento y recubrimiento óptimos en el plano son NP-completos", Information Processing Letters , 12 (3): 133– 137, doi : 10.1016/0020-0190(81)90111-3.
↑ Megiddo, Nimrod ; Tamir, Arie (1982), "Sobre la complejidad de ubicar instalaciones lineales en el plano" (PDF) , Operations Research Letters , 1 (5): 194–197 , doi : 10.1016/0167-6377(82)90039-6.
1 2 3 González, Teófilo (1985), "Agrupamiento para minimizar la distancia máxima entre clústeres", Theoretical Computer Science , 38 : 293–306 , Bibcode : 1985TComS..38..293G , doi : 10.1016/0304-3975(85)90224-5 .
1 2 Feder, Tomás; Greene, Daniel (1988), "Algoritmos óptimos para agrupamiento aproximado", Actas del vigésimo simposio anual de la ACM sobre Teoría de la Computación - STOC '88 , págs. 434–444 , doi : 10.1145/62212.62255 , ISBN 0897912640, S2CID 658151
↑ HWang, RZ; Lee, RCT; Chang, RC (1993), "El enfoque de división de losas para resolver el problema del p-centro euclidiano", Algorithmica , 9 (1): 1– 22, doi : 10.1007/BF01185335 , S2CID 5680676
↑ HWang, RZ; Chang, RC; Lee, RCT (1993), "La estrategia de búsqueda generalizada sobre separadores para resolver algunos problemas NP-difíciles en tiempo subexponencial", Algorithmica , 9 (4): 398– 423, doi : 10.1007/bf01228511 , S2CID 2722869
↑ Bādoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), "Agrupamiento aproximado mediante conjuntos centrales", Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación (PDF) , págs. 250–257 , doi : 10.1145/509907.509947 , ISBN 1581134959, S2CID 5409535
↑ Kumar, Pankaj; Kumar, Piyush (2010), "Soluciones casi óptimas para problemas de k-agrupamiento" (PDF) , International Journal of Computational Geometry & Applications , 20 (4): 431– 447, doi : 10.1142/S0218195910003372
↑ Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag. ISBN 978-0-387-96131-6. 1.ª edición; 2.ª reimpresión, corregida y ampliada, 1988; traducción al ruso, 1989.pág . 256
↑ GT Toussaint, "Cálculo de los círculos vacíos más grandes con restricciones de ubicación", International Journal of Computer and Information Sciences , vol. 12, n.º 5, octubre de 1983, págs. 347–358.
1 2 Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Programación entera . Textos de Posgrado en Matemáticas. vol. 271.doi : 10.1007 /978-3-319-11008-0 . ISBN 978-3-319-11007-3.
↑ Mirchandani, Pitu B.; Francis, RL, eds. (1990). Teoría de la localización discreta . Nueva York: Wiley. ISBN 9780471892335. OCLC 19810449 .
1 2 3 4 5 DURIER, R; MICHELOT, C. (1986). "Conjuntos de puntos eficientes en un espacio normado" . Conjuntos de puntos eficientes en un espacio normado . 117 (2): 506– 528. ISSN 0022-247X .
^ Beauzamy, Bernardo; Maurey, Bernard (febrero de 1977). "Points minimaux et ensembles optimaux dans les espaces de Banach" . Revista de análisis funcional . 24 (2): 107– 139. doi : 10.1016/0022-1236(77)90049-0 . ISSN 0022-1236 . Archivado desde el original el 17 de febrero de 2024.
1 2 3 Drezner, Zvi; Kathrin, Klamorth; Schöbel, Anita; Wesolowsky, George O. (2004). "1.2 Historia y revisión de la literatura". Facility Location: Applications and Theory . Springer. pp. 3–11 . ISBN 3-540-21345-7.
↑ Weber, Alfred (julio de 1929). «II Orientación del transporte, sección II Las leyes de la orientación del transporte». Teoría de la localización de las industrias . Traducido por Friedrich, Carl Joachim. Chicago, Illinois: The University of Chicago Press. págs. 48-76 .
1 2 Miehle, William (11 de octubre de 1957). "Minimización de la longitud de los enlaces en redes" . Operations Research . 6 (2): 232– 243. doi : 10.1287/opre.6.2.232 . JSTOR 167615 – vía JSTOR.
1 2 Kuhn, Harold W.; Kuenne, Robert E. (diciembre de 1962). "Un algoritmo eficiente para la solución numérica del problema generalizado de Weber en economía espacial" . Journal of Regional Science . 4 (2): 21– 33. Bibcode : 1962JRegS...4...21K . doi : 10.1111/j.1467-9787.1962.tb00902.x – vía Wiley Online Library.
↑ Weiszfeld, E.; Plastria, Frank (29 de abril de 2008). "Sobre el punto para el cual la suma de las distancias a n puntos dados es mínima" . Annals of Operations Research . 167 : 7–41 . doi : 10.1007/s10479-008-0352-z – vía Springer Nature Link.
↑ Francis, Richard L. (15 de marzo de 1967). "Algunos aspectos de un problema de localización minimax" . Operations Research . 15 (6): 1163– 1169. doi : 10.1287/opre.15.6.1163 . JSTOR 168621 – vía JSTOR.
↑ Demjanov, Vladimir F. (diciembre de 1968). "Algoritmos para algunos problemas minimax" . Journal of Computer and System Sciences . 2 (4): 342– 380. doi : 10.1016/S0022-0000(68)80034-0 – vía Elsevier Science Direct.
↑ Church, RL; Cohon, JL (1976-10-01). Análisis de localización multiobjetivo de problemas de emplazamiento de instalaciones energéticas regionales (Informe). Brookhaven National Lab. (BNL), Upton, NY (Estados Unidos). OSTI 7294043 .
↑ Dutton, Ron; Hinman, George; Millham, CB (1 de junio de 1974). "La ubicación óptima de las instalaciones de energía nuclear en el noroeste del Pacífico" . Operations Research . 22 (3): 478– 487. doi : 10.1287/opre.22.3.478 . ISSN 0030-364X – vía Informs PubsOnLine.
↑ Church, Richard L; Drezner, Zvi (febrero de 2022). "Revisión de problemas molestos de localización de instalaciones" . Computers & Operations Research . 138 105468. doi : 10.1016/j.cor.2021.105468 – vía Elsevier Science Direct.
↑ Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "Un estudio sobre la ubicación de centros de atención médica". Computers & Operations Research . 79 : 223–263 . doi : 10.1016/j.cor.2016.05.018 .
↑ Franco, DGB; Steiner, MTA; Assef, FM (2020). "Optimización en la partición del vertedero de residuos en el estado de Paraná, Brasil". Journal of Cleaner Production . 283 125353. doi : 10.1016/j.jclepro.2020.125353 . S2CID 229429742 .
↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). Los elementos del aprendizaje estadístico (Segunda edición). Springer.
^ Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . Pearson.

Enlaces externos

Grupo de trabajo de EWGLA EURO sobre análisis de localización .
Sección de análisis de ubicación de INFORMS , una sociedad profesional dedicada a la localización de instalaciones.
Bibliografía sobre la ubicación de instalaciones recopilada por Trevor Hale , que contiene más de 3400 artículos.
Biblioteca de algoritmos de localización
Utilidad web para la localización de instalaciones (instalación única)
Facility Location Optimizer , una herramienta basada en MATLAB para resolver problemas de localización de instalaciones.

[1] Eiselt, HA; Marianov, Vladimir (2011). "1.1 Desarrollos pioneros en el análisis de localización, problemas de localización: su planteamiento, sus componentes y su aplicación". Fundamentos del análisis de localización . Springer. pp. 3–6 . doi : 10.1007/978-1-4419-7572-0 . ISBN 978-1-4419-7571-3.

[2] Marianov, Vladimir; Serra, Daniel (2011). "3.1 Problemas de mediana en redes, Introducción". Fundamentos del análisis de localización . Springer. pp. 31–43 . doi : 10.1007/978-1-4419-7572-0 . ISBN 978-1-4419-7571-3.

[3] Drezner, Zvi; Simchi-Levi, David (diciembre de 1992). "Comportamiento asintótico del problema de localización de Weber en el plano" . Annals of Operations Research . 40 : 163–172 . doi : 10.1007/BF02060475 – vía Springer Nature Link.

[:1-4] 1 2 Hochbaum, DS (1982). "Heurísticas para el problema de la mediana de costo fijo". Programación matemática . 22 : 148–162 . doi : 10.1007/BF01581035 . S2CID 3451944 .

[:2-5] 1 2 Hansen, Pierre; Peeters, Dominique; Richard, Denis; Thisse, Jacques-Francois (noviembre de 1985). "Los problemas de localización Minisum y Minimax revisados" . Operations Research . 33 (6): 1251– 1265. doi : 10.1287/opre.33.6.1251 – vía Informs PubsOnLine.

[6] Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: Improved Facility Location Algorithms". Journal of Algorithms . 31 : 228–248 . CiteSeerX 10.1.1.47.2033 . doi : 10.1006/jagm.1998.0993 . S2CID 5363214 .

[7] Li, S. (2011). "Un algoritmo de aproximación 1,488 para el problema de localización de instalaciones sin restricciones de capacidad". Autómatas, lenguajes y programación . LNCS . Vol. 6756. pp. 77–88 . CiteSeerX 10.1.1.225.6387 . doi : 10.1007/978-3-642-22012-8_5 . ISBN 978-3-642-22011-1.

[8] Fowler, RJ; Paterson, MS; Tanimoto, SL (1981), "El empaquetamiento y recubrimiento óptimos en el plano son NP-completos", Information Processing Letters , 12 (3): 133– 137, doi : 10.1016/0020-0190(81)90111-3.

[9] Megiddo, Nimrod ; Tamir, Arie (1982), "Sobre la complejidad de ubicar instalaciones lineales en el plano" (PDF) , Operations Research Letters , 1 (5): 194–197 , doi : 10.1016/0167-6377(82)90039-6.

[Gonzalez1985-10] 1 2 3 González, Teófilo (1985), "Agrupamiento para minimizar la distancia máxima entre clústeres", Theoretical Computer Science , 38 : 293–306 , Bibcode : 1985TComS..38..293G , doi : 10.1016/0304-3975(85)90224-5 .

[Feder1988-11] 1 2 Feder, Tomás; Greene, Daniel (1988), "Algoritmos óptimos para agrupamiento aproximado", Actas del vigésimo simposio anual de la ACM sobre Teoría de la Computación - STOC '88 , págs. 434–444 , doi : 10.1145/62212.62255 , ISBN 0897912640, S2CID 658151

[12] HWang, RZ; Lee, RCT; Chang, RC (1993), "El enfoque de división de losas para resolver el problema del p-centro euclidiano", Algorithmica , 9 (1): 1– 22, doi : 10.1007/BF01185335 , S2CID 5680676

[13] HWang, RZ; Chang, RC; Lee, RCT (1993), "La estrategia de búsqueda generalizada sobre separadores para resolver algunos problemas NP-difíciles en tiempo subexponencial", Algorithmica , 9 (4): 398– 423, doi : 10.1007/bf01228511 , S2CID 2722869

[14] Bādoiu, Mihai; Har-Peled, Sariel ; Indyk, Piotr (2002), "Agrupamiento aproximado mediante conjuntos centrales", Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación (PDF) , págs. 250–257 , doi : 10.1145/509907.509947 , ISBN 1581134959, S2CID 5409535

[15] Kumar, Pankaj; Kumar, Piyush (2010), "Soluciones casi óptimas para problemas de k-agrupamiento" (PDF) , International Journal of Computational Geometry & Applications , 20 (4): 431– 447, doi : 10.1142/S0218195910003372

[ps256-16] Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag. ISBN 978-0-387-96131-6. 1.ª edición; 2.ª reimpresión, corregida y ampliada, 1988; traducción al ruso, 1989.pág . 256

[17] GT Toussaint, "Cálculo de los círculos vacíos más grandes con restricciones de ubicación", International Journal of Computer and Information Sciences , vol. 12, n.º 5, octubre de 1983, págs. 347–358.

[:0-18] 1 2 Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Programación entera . Textos de Posgrado en Matemáticas. vol. 271.doi : 10.1007 /978-3-319-11008-0 . ISBN 978-3-319-11007-3.

[19] Mirchandani, Pitu B.; Francis, RL, eds. (1990). Teoría de la localización discreta . Nueva York: Wiley. ISBN 9780471892335. OCLC 19810449 .

[:32-20] 1 2 3 4 5 DURIER, R; MICHELOT, C. (1986). "Conjuntos de puntos eficientes en un espacio normado" . Conjuntos de puntos eficientes en un espacio normado . 117 (2): 506– 528. ISSN 0022-247X .

[21] Beauzamy, Bernardo; Maurey, Bernard (febrero de 1977). "Points minimaux et ensembles optimaux dans les espaces de Banach" . Revista de análisis funcional . 24 (2): 107– 139. doi : 10.1016/0022-1236(77)90049-0 . ISSN 0022-1236 . Archivado desde el original el 17 de febrero de 2024.

[:3-22] 1 2 3 Drezner, Zvi; Kathrin, Klamorth; Schöbel, Anita; Wesolowsky, George O. (2004). "1.2 Historia y revisión de la literatura". Facility Location: Applications and Theory . Springer. pp. 3–11 . ISBN 3-540-21345-7.

[23] Weber, Alfred (julio de 1929). «II Orientación del transporte, sección II Las leyes de la orientación del transporte». Teoría de la localización de las industrias . Traducido por Friedrich, Carl Joachim. Chicago, Illinois: The University of Chicago Press. págs. 48-76 .

[:4-24] 1 2 Miehle, William (11 de octubre de 1957). "Minimización de la longitud de los enlaces en redes" . Operations Research . 6 (2): 232– 243. doi : 10.1287/opre.6.2.232 . JSTOR 167615 – vía JSTOR.

[:5-25] 1 2 Kuhn, Harold W.; Kuenne, Robert E. (diciembre de 1962). "Un algoritmo eficiente para la solución numérica del problema generalizado de Weber en economía espacial" . Journal of Regional Science . 4 (2): 21– 33. Bibcode : 1962JRegS...4...21K . doi : 10.1111/j.1467-9787.1962.tb00902.x – vía Wiley Online Library.

[26] Weiszfeld, E.; Plastria, Frank (29 de abril de 2008). "Sobre el punto para el cual la suma de las distancias a n puntos dados es mínima" . Annals of Operations Research . 167 : 7–41 . doi : 10.1007/s10479-008-0352-z – vía Springer Nature Link.

[27] Francis, Richard L. (15 de marzo de 1967). "Algunos aspectos de un problema de localización minimax" . Operations Research . 15 (6): 1163– 1169. doi : 10.1287/opre.15.6.1163 . JSTOR 168621 – vía JSTOR.

[28] Demjanov, Vladimir F. (diciembre de 1968). "Algoritmos para algunos problemas minimax" . Journal of Computer and System Sciences . 2 (4): 342– 380. doi : 10.1016/S0022-0000(68)80034-0 – vía Elsevier Science Direct.

[29] Church, RL; Cohon, JL (1976-10-01). Análisis de localización multiobjetivo de problemas de emplazamiento de instalaciones energéticas regionales (Informe). Brookhaven National Lab. (BNL), Upton, NY (Estados Unidos). OSTI 7294043 .

[30] Dutton, Ron; Hinman, George; Millham, CB (1 de junio de 1974). "La ubicación óptima de las instalaciones de energía nuclear en el noroeste del Pacífico" . Operations Research . 22 (3): 478– 487. doi : 10.1287/opre.22.3.478 . ISSN 0030-364X – vía Informs PubsOnLine.

[31] Church, Richard L; Drezner, Zvi (febrero de 2022). "Revisión de problemas molestos de localización de instalaciones" . Computers & Operations Research . 138 105468. doi : 10.1016/j.cor.2021.105468 – vía Elsevier Science Direct.

[Ahmadi-32] Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "Un estudio sobre la ubicación de centros de atención médica". Computers & Operations Research . 79 : 223–263 . doi : 10.1016/j.cor.2016.05.018 .

[33] Franco, DGB; Steiner, MTA; Assef, FM (2020). "Optimización en la partición del vertedero de residuos en el estado de Paraná, Brasil". Journal of Cleaner Production . 283 125353. doi : 10.1016/j.jclepro.2020.125353 . S2CID 229429742 .

[34] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). Los elementos del aprendizaje estadístico (Segunda edición). Springer.

[35] Kleinberg, Jon; Tardos, Éva (2006). Diseño de algoritmos . Pearson.

[ 1 ]

[ 2 ]

[ 3 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 19 ]

[ 21 ]

[ 23 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]