Problém s umístěním objektu

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. ledna 2020; ověření vyžaduje 1 úpravu .

Problém umístění objektů , také známý jako analýza umístění zařízení nebo problém k - centra , je odvětvím operačního výzkumu a výpočetní geometrie , které zkoumá optimální umístění objektů, aby se minimalizovaly náklady na dopravu, s výhradou omezení, jako je umístění nebezpečných materiálů v blízkosti obydlí. Technika je také použitelná pro shlukovou analýzu .

Problém umístění objektu s minimalizací

Jednoduchým problémem umístění objektu je Weberův problém , ve kterém je umístěn jeden objekt, aby se minimalizoval vážený součet vzdáleností k danému souboru bodů. Složitější problémy v této disciplíně vznikají při omezení umístění objektů a při použití složitějších optimalizačních kritérií.

Ve své základní formulaci se problém umístění objektů skládá z potenciálních bodů umístění L , kde lze objekty otevřít, a bodů D , které je třeba opravit. Cílem je vybrat podmnožinu F bodů umístění objektů, aby se minimalizoval součet vzdáleností od každého servisního bodu k nejbližšímu servisnímu objektu plus součet nákladů na umístění objektů.

Problém umísťování objektů na obecných grafech je NP-těžce řešitelný optimálně a lze jej vyřešit redukcí (například) z nastaveného krycího problému . Bylo vyvinuto několik algoritmů pro problémy s umístěním objektů a mnoho variant tohoto problému.

Bez předpokladů o vlastnostech vzdáleností mezi klienty a umístěními objektů (zejména bez předpokladu, že vzdálenost splňuje trojúhelníkovou nerovnost ), je problém znám jako nemetrický problém umístění objektů a lze jej aproximovat pomocí O(log  n ) faktor [1] . Faktor je těsný, což vyplývá z aproximace zachovávající redukce z nastaveného krycího problému.

Pokud předpokládáme, že vzdálenosti mezi klienty a umístěním objektů jsou neorientované a splňují trojúhelníkovou nerovnost, mluvíme o problému metrického umístění objektů (MPO) . MPO zůstává NP-obtížným problémem a je obtížné jej aproximovat faktorem lepším než 1,463 [2] . V současnosti má nejlepší aproximační algoritmus koeficient 1,488. [3] .

Minimax umístění objektu

Problém umístění minimaxu hledá umístění, které minimalizuje maximální vzdálenosti k umístěním, kde vzdálenost od určitého bodu k umístění je vzdálenost od bodu k nejbližšímu umístění. Formální definice je následující: Je-li dána množina bodů P  ⊂ ℝ d , musíte najít množinu bodů S  ⊂ ℝ d , | S | =  k , takže hodnota max p  ∈  P (min q  ∈  S (d( p ,  q ))) je minimální.

V případě euklidovské metriky s k  = 1 je problém známý jako problém nejmenší ohraničující koule nebo problém 1 centra . Studium problému lze vysledovat minimálně do roku 1860, podrobnosti naleznete v článku „ Bounding Sphere “.

NP-obtížnost

Bylo dokázáno, že přesné řešení úlohy k -centra je NP-těžké [4] [5] [6] . Bylo zjištěno, že aproximace problému bude také NP-těžká, pokud je chyba malá. Míra chyby v aproximačním algoritmu je měřena aproximačním koeficientem , který je definován jako poměr aproximovaného řešení k optimálnímu. Bylo prokázáno, že aproximace problému k -centra je NP-těžká, pokud je aproximační koeficient menší než 1,822 (pro rozměr =2) [7] nebo 2 (pro rozměr >2) [6] .

Algoritmy

Přesné řešení

Existují algoritmy, které poskytují přesné řešení problému. Jeden z těchto algoritmů poskytuje řešení v čase [8] [9] .

Přibližná hodnota 1 + ε

Aproximace 1 +  ε najde řešení s aproximačním koeficientem nepřesahujícím 1 +  ε . Taková aproximace je NP-těžká pro libovolné ε . Byl navržen přístup založený na konceptu základního souboru , se složitostí implementace [10] . K dispozici je alternativní algoritmus, rovněž založený na základních sadách. Funguje v čase [11] . Autor tvrdí, že doba běhu je mnohem kratší než doba nejhoršího případu a že je možné vyřešit některé problémy v případě malých k (řekněme   k  < 5).

Výběr vzdálených bodů

Vzhledem ke složitosti problému je nepraktické hledat přesné řešení nebo blízkou aproximaci. Místo toho se pro velké k široce používá aproximace s faktorem 2. Tato aproximace je známá jako shlukování nejvzdálenějších bodů (FPC) nebo jako algoritmus shlukování nejvzdálenějších bodů [6] . Algoritmus je poměrně jednoduchý - jako střed zvolíme libovolný bod množiny, najdeme nejvzdálenější ze zbývající množiny a považujeme jej za další střed. Pokračujeme v procesu, dokud nebudeme mít k středů.

Je snadné vidět, že algoritmus běží v lineárním čase. Protože bylo prokázáno, že aproximace s faktorem menším než 2 je NP-těžká, je BOT považována za nejlepší aproximaci.

Složitost doby provádění byla později vylepšena na O( n  log  k ) pomocí techniky box decomposition [7] .

Maximální umístění objektů

Problém umístění objektu maximin hledá umístění, které maximalizuje minimální vzdálenosti do stran. V případě euklidovské metriky je problém známý jako problém největší prázdné koule . Plochý případ ( největší prázdný kruh ) lze vyřešit v čase Θ( n  \log n) [12] [13] .

Svobodný software pro řešení problémů s umístěním objektů

Jméno
(v abecedním pořadí) 		Licence API jazyk krátké informace
FLP Spreadsheet Solver Mezinárodní licence Creative Commons Attribution 4.0 Open source Microsoft Excel a systém založený na VBA pro řešení problému s umístěním objektů s odkazem na sdílený GIS . odkaz Odkaz na videonávody [14] .
Studio ODL LGPL Komponenta omezeného clusteru v ODL Studio řeší problém P-mediánu (vzdáleně vážené umístění). Program zahrnuje plány rozložení, zprávy a nahrávání/stahování do Excelu. [jeden]
SITUACE freeware Dokáže vyřešit pět tříd problémů, včetně: P-medián, P-centrum, Set Coverage, Maximum Coverage a Fixed Cost Problem with No Bandwidth Limit. [2] [14]

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

Viz také

Poznámky

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

Literatura

Odkazy