Problema de colocación de objetos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de enero de 2020; la verificación requiere 1 edición .

El problema de ubicación de objetos , también conocido como análisis de ubicación de equipos o problema del centro k , es una rama de la investigación de operaciones y la geometría computacional que investiga la ubicación óptima de los objetos para minimizar los costos de envío, sujeto a restricciones como colocar materiales peligrosos cerca. viviendas La técnica también es aplicable al análisis de conglomerados .

Problema de colocación de objetos con minimización

Un problema de colocación de objetos simple es el problema de Weber , en el que se coloca un objeto para minimizar la suma ponderada de distancias a un conjunto de puntos dado. Problemas más complejos en esta disciplina surgen bajo restricciones en la colocación de objetos y cuando se utilizan criterios de optimización más complejos.

En su formulación básica, el problema de ubicación de objetos consiste en puntos de ubicación potenciales L donde los objetos pueden abrirse y puntos D que deben recibir servicio. El objetivo es seleccionar un subconjunto F de puntos de ubicación de objetos para minimizar la suma de distancias desde cada punto de servicio hasta el objeto de servicio más cercano, más la suma de los costos de ubicación de objetos.

El problema de colocar objetos en gráficos generales es NP-difícil de resolver de manera óptima y puede resolverse reduciendo (por ejemplo) del problema de cobertura de conjuntos . Se han desarrollado varios algoritmos para problemas de colocación de objetos y muchas variantes de este problema.

Sin suposiciones sobre las propiedades de las distancias entre clientes y ubicaciones de objetos (en particular, sin la suposición de que la distancia satisface la desigualdad triangular ), el problema se conoce como un problema de ubicación de objetos no métrico y se puede aproximar con un O(log  n ) factor [1] . El factor es ajustado, lo que se deriva de la reducción que preserva la aproximación del problema de cobertura de conjuntos.

Si asumimos que las distancias entre los clientes y las ubicaciones de los objetos no están dirigidas y satisfacen la desigualdad del triángulo, estamos hablando de un problema de ubicación métrica de objetos (MPO) . MPO sigue siendo un problema NP-difícil y es difícil de aproximar con un factor mejor que 1.463 [2] . En la actualidad, el algoritmo de mejor aproximación tiene un coeficiente de 1,488. [3] .

Colocación de objetos Minimax

El problema de ubicación minimax busca una ubicación que minimice las distancias máximas a las ubicaciones, donde la distancia desde un punto a las ubicaciones es la distancia desde el punto a la ubicación más cercana. La definición formal es la siguiente: Dado un conjunto de puntos P  ⊂ ℝ d , necesitas encontrar un conjunto de puntos S  ⊂ ℝ d , | S | =  k , tal que el valor max p  ∈  P (min q  ∈  S (d( p ,  q ))) es mínimo.

En el caso de una métrica euclidiana con k  = 1, el problema se conoce como el problema de la esfera mínima delimitante o el problema de 1 centro . El estudio del problema se remonta al menos a 1860, consulte el artículo " Bounding Sphere " para obtener más información.

NP-dificultad

Se ha demostrado que la solución exacta del problema del k -centro es NP-hard [4] [5] [6] . Se encontró que la aproximación del problema también será NP-difícil si el error es pequeño. El nivel de error en el algoritmo de aproximación se mide por el coeficiente de aproximación , que se define como la relación entre la solución aproximada y la óptima. Se ha demostrado que la aproximación del problema del k -centro es NP-difícil si el coeficiente de aproximación es menor que 1.822 (para dimensión =2) [7] o 2 (para dimensión >2) [6] .

Algoritmos

solución exacta

Hay algoritmos que dan una solución exacta al problema. Uno de estos algoritmos da una solución en el tiempo [8] [9] .

Aproximación 1 + ε

La aproximación 1 +  ε encuentra una solución con un coeficiente de aproximación que no exceda de 1 +  ε . Tal aproximación es NP-difícil para ε arbitrario . Se ha propuesto un enfoque basado en el concepto de conjunto básico , con complejidad de implementación [10] . Está disponible un algoritmo alternativo, también basado en conjuntos básicos. Funciona en el tiempo [11] . El autor argumenta que el tiempo de ejecución es mucho menor que el tiempo en el peor de los casos y es posible resolver algunos problemas en el caso de k pequeño (digamos,   k  < 5).

Selección de puntos lejanos

Debido a la complejidad del problema, no es práctico buscar una solución exacta o una aproximación cercana. En cambio, para k grande , se usa ampliamente una aproximación con un factor de 2. Esta aproximación se conoce como agrupamiento del punto más lejano (FPC) o como el algoritmo de agrupamiento del punto más lejano [6] . El algoritmo es bastante simple: elegimos un punto arbitrario del conjunto como centro, encontramos el más alejado del conjunto restante y lo consideramos el siguiente centro. Continuamos el proceso hasta tener k centros.

Es fácil ver que el algoritmo se ejecuta en tiempo lineal. Dado que se ha demostrado que una aproximación con un factor menor que 2 es NP-hard, se considera que BOT es la mejor aproximación.

La complejidad del tiempo de ejecución se mejoró posteriormente a O( n  log  k ) utilizando la técnica de descomposición de cajas [7] .

Colocación máxima de objetos

El problema de colocación de objetos maximin busca una ubicación que maximice las distancias mínimas a los lados. En el caso de la métrica euclidiana, el problema se conoce como el problema de la esfera vacía más grande . El caso plano ( el círculo vacío más grande ) se puede resolver en el tiempo Θ( n  \log n) [12] [13] .

Software gratuito para resolver problemas de colocación de objetos

Nombre
(en orden alfabético) 		Licencia lenguaje API breve informacion
Solucionador de hoja de cálculo FLP Creative Commons Reconocimiento 4.0 Licencia internacional Un sistema basado en Microsoft Excel y VBA de código abierto para resolver el problema de colocación de objetos con un enlace a un GIS compartido . link Videotutoriales link [14] .
Estudio ODL LGPL El componente de clúster restringido en ODL Studio resuelve el problema de la mediana P (ubicación ponderada por distancia). El programa incluye planos de distribución, informes y carga/descarga a Excel. [una]
SITACIÓN software gratuito Puede resolver cinco clases de problemas, que incluyen: P-mediana, P-centro, Cobertura establecida, Cobertura máxima y Problema de costo fijo sin límite de ancho de banda. [2] [14]

http://www.opendoorlogistics.com/tutorials/tutorial-territory-design/step-3-automated-territory-design/

Véase también

Notas

  1. ↑ Hochbaum, 1982 , pág. 148–162.
  2. ↑ Guha, Khuller, 1999 , pág. 228.
  3. ↑ Li, 2011 , pág. 77–88.
  4. ↑ Fowler, Paterson, Tanimoto, 1981 , pág. 133–137.
  5. ↑ Megido, Tamir, 1982 , p. 194–197.
  6. ↑ 1 2 3 González, 1985 , p. 293–306.
  7. ↑ 1 2 Feder, Greene, 1988 , p. 434–444.
  8. ↑ Hwang, Lee, Chang, 1993 , pág. 1–22.
  9. ↑ Hwang, Chang, Lee, 1993 , pág. 398–423.
  10. ↑ Badoiu, Har-Peled, Indyk, 2002 , pág. 250–257.
  11. ↑ Kumar y Kumar, 2010 .
  12. ↑ Preparata y Sheimos, 1989 .
  13. ↑ Toussaint, 1983 , pág. 347–358.
  14. ↑ 12 Csoke , 2015 .

Literatura

Enlaces