Objektplaceringsproblem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. januar 2020; verifikation kræver 1 redigering .

Objektplaceringsproblemet , også kendt som udstyrsplaceringsanalyse eller k - centerproblemet , er en gren af ​​operationsforskning og beregningsgeometri , der undersøger den optimale placering af objekter for at minimere forsendelsesomkostninger, underlagt begrænsninger såsom at placere farlige materialer i nærheden af boliger. Teknikken er også anvendelig til klyngeanalyse .

Objektplaceringsproblem med minimering

Et simpelt objektplaceringsproblem er Weber-problemet , hvor et objekt placeres for at minimere den vægtede sum af afstande til et givet sæt punkter. Mere komplekse problemer i denne disciplin opstår under restriktioner for placering af objekter og ved brug af mere komplekse optimeringskriterier.

Objektplaceringsproblemet består i sin grundformulering af potentielle placeringspunkter L , hvor genstande kan åbnes, og punkter D , der skal serviceres. Målet er at vælge en delmængde F af objektplaceringspunkter for at minimere summen af ​​afstande fra hvert servicepunkt til det nærmeste serviceobjekt plus summen af ​​objektplaceringsomkostninger.

Problemet med at placere objekter på generelle grafer er NP-svært at løse optimalt, og kan løses ved at reducere (for eksempel) fra det sæt, der dækker problemet . Der er udviklet adskillige algoritmer til problemer med objektplacering og mange varianter af dette problem.

Uden antagelser om egenskaberne af afstande mellem klienter og objektplaceringer (især uden antagelsen om, at afstanden opfylder trekantens ulighed ), er problemet kendt som et ikke-metrisk objektplaceringsproblem, og det kan tilnærmes med en O(log)  n ) faktor [1] . Faktoren er stram, hvilket følger af den tilnærmelsesbevarende reduktion fra sætafdækningsproblemet.

Hvis vi antager, at afstandene mellem klienter og objektplaceringer er urettede og tilfredsstiller trekantens ulighed, taler vi om et metrisk objektplacering (MPO) problem . MPO forbliver et NP-hårdt problem og er vanskeligt at tilnærme sig med en faktor bedre end 1,463 [2] . På nuværende tidspunkt har den bedste tilnærmelsesalgoritme en koefficient på 1,488. [3] .

Minimax objektplacering

Minimax-placeringsproblemet leder efter en placering, der minimerer de maksimale afstande til placeringer, hvor afstanden fra et punkt til placeringer er afstanden fra punktet til den nærmeste placering. Den formelle definition er som følger: Givet et sæt punkter P  ⊂ ℝ d , skal du finde et sæt punkter S  ⊂ ℝ d , | S | =  k , således at værdien max p  ∈  P (min q  ∈  S (d( p ,  q ))) er minimal.

I tilfælde af en euklidisk metrik med k  = 1, er problemet kendt som det mindst begrænsende sfæreproblem eller 1-centerproblemet . Studiet af problemet kan spores tilbage til mindst 1860, se artiklen " Bounding Sphere " for detaljer.

NP-sværhedsgrad

Det er blevet bevist, at den nøjagtige løsning af k -centerproblemet er NP-hård [4] [5] [6] . Det blev konstateret, at problemtilnærmelsen også vil være NP-hård, hvis fejlen er lille. Fejlniveauet i tilnærmelsesalgoritmen måles ved tilnærmelseskoefficienten , der er defineret som forholdet mellem den tilnærmede løsning og den optimale. Det er blevet bevist, at tilnærmelsen af ​​k -centerproblemet er NP-hård, hvis tilnærmelseskoefficienten er mindre end 1,822 (for dimension =2) [7] eller 2 (for dimension >2) [6] .

Algoritmer

Præcis løsning

Der er algoritmer, der giver en nøjagtig løsning på problemet. En af disse algoritmer giver en løsning i tide [8] [9] .

Tilnærmelsesvis 1 + ε

Approksimation 1 +  ε finder en løsning med en tilnærmelseskoefficient, der ikke overstiger 1 +  ε . En sådan tilnærmelse er NP-svær for vilkårlig ε . En tilgang er blevet foreslået baseret på konceptet om et grundlæggende sæt , med implementeringskompleksitet [10] . En alternativ algoritme er tilgængelig, også baseret på basissæt. Det virker i tide [11] . Forfatteren hævder, at køretiden er meget mindre end den værst tænkelige tid, og det er muligt at løse nogle problemer i tilfælde af lille k (f.eks.   k  < 5).

Udvælgelse af fjerne punkter

På grund af problemets kompleksitet er det upraktisk at lede efter en nøjagtig løsning eller en tæt tilnærmelse. I stedet for store k anvendes en tilnærmelse med en faktor 2. Denne tilnærmelse er kendt som Farthest-point clustering (FPC) eller som den fjerneste -point clustering algoritme [6] . Algoritmen er ret simpel - vi vælger et vilkårligt punkt i sættet som centrum, finder det fjerneste af det resterende sæt og betragter det som det næste center. Vi fortsætter processen indtil vi har k centre.

Det er let at se, at algoritmen kører i lineær tid. Da det er blevet bevist, at en tilnærmelse med en faktor mindre end 2 er NP-hård, betragtes BOT som den bedste tilnærmelse.

Eksekveringstidskompleksiteten blev senere forbedret til O( n  log  k ) ved brug af boksnedbrydningsteknikken [7] .

Maksimal placering af objekter

Problemet med maximin objektplacering leder efter en placering, der maksimerer minimumsafstandene til siderne. I tilfælde af den euklidiske metriske er problemet kendt som det største tomme sfæreproblem . Det flade tilfælde ( største tomme cirkel ) kan løses i tiden Θ( n  \log n) [12] [13] .

Gratis software til at løse problemer med objektplacering

Navn
(i alfabetisk rækkefølge) 		Licens API sprog kort information
FLP regnearksløser Creative Commons Attribution 4.0 International License Et open source Microsoft Excel og VBA-baseret system til løsning af objektplaceringsproblemet med et link til et delt GIS . link Video tutorials link [14] .
ODL Studio LGPL Den begrænsede klyngekomponent i ODL Studio løser P-medianproblemet (afstandsvægtet placering). Programmet indeholder layoutplaner, rapporter og upload/download til Excel. [en]
SITATION freeware Det kan løse fem klasser af problemer, herunder: P-median, P-center, sæt dækning, maksimal dækning og problemer med faste omkostninger uden båndbreddegrænse. [2] [14]

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

Se også

Noter

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

Litteratur

Links