Problemă de plasare a obiectelor

Problema de plasare a obiectelor , cunoscută și sub numele de analiza locației echipamentelor sau problema centrului k , este o ramură a cercetării operaționale și a geometriei computaționale care investighează locația optimă a obiectelor pentru a minimiza costurile de transport, sub rezerva unor constrângeri precum plasarea materialelor periculoase în apropiere. locuințe. Tehnica este aplicabilă și analizei cluster .

Problemă de plasare a obiectelor cu minimizarea

O problemă simplă de plasare a obiectelor este problema Weber , în care un obiect este plasat pentru a minimiza suma ponderată a distanțelor către un anumit set de puncte. Probleme mai complexe din această disciplină apar sub restricții privind plasarea obiectelor și atunci când se utilizează criterii de optimizare mai complexe.

În formularea sa de bază, problema de plasare a obiectelor constă din potențiale puncte de plasare L unde obiectele pot fi deschise și punctele D care trebuie deservite. Scopul este de a selecta un subset F de puncte de plasare a obiectelor pentru a minimiza suma distanțelor de la fiecare punct de serviciu la cel mai apropiat obiect de serviciu, plus suma costurilor de plasare a obiectelor.

Problema plasării obiectelor pe grafice generale este NP-greu de rezolvat în mod optim și poate fi rezolvată prin reducerea (de exemplu) din problema de acoperire a mulțimii . Au fost dezvoltați mai mulți algoritmi pentru problemele de plasare a obiectelor și multe variante ale acestei probleme.

Fără ipoteze despre proprietățile distanțelor dintre clienți și plasările de obiecte (în special, fără ipoteza că distanța satisface inegalitatea triunghiului ), problema este cunoscută ca o problemă de plasare a obiectelor nemetrice și poate fi aproximată cu un O(log  n ) factorul [1] . Factorul este strâns, ceea ce rezultă din reducerea aproximării-conservare din problema acoperirii seturilor.

Dacă presupunem că distanțele dintre clienți și plasările de obiecte sunt nedirecționate și satisfac inegalitatea triunghiului, vorbim despre o problemă de plasare a obiectelor metrice (MPO) . MPO rămâne o problemă NP-hard și este dificil de aproximat cu un factor mai bun decât 1,463 [2] . În prezent, cel mai bun algoritm de aproximare are un coeficient de 1,488. [3] .

Plasarea obiectelor Minimax

Problema de plasare minimax caută o plasare care minimizează distanțele maxime până la destinații de plasare, unde distanța de la un punct la destinații de plasare este distanța de la punctul la cea mai apropiată destinație de plasare. Definiția formală este următoarea: Având în vedere o mulțime de puncte P  ⊂ ℝ d , trebuie să găsiți o mulțime de puncte S  ⊂ ℝ d , | S | =  k , astfel încât valoarea max p  ∈  P (min q  ∈  S (d( p ,  q ))) este minimă.

În cazul unei metrici euclidiene cu k  = 1, problema este cunoscută ca problema sferei cu cea mai mică limită sau problema cu 1 centru . Studiul problemei poate fi urmărit cel puțin până în 1860, vezi articolul „ Bounding Sphere ” pentru detalii.

NP-dificultate

S-a dovedit că soluția exactă a problemei k -centrului este NP-hard [4] [5] [6] . Sa constatat că aproximarea problemei va fi, de asemenea, NP-hard dacă eroarea este mică. Nivelul de eroare în algoritmul de aproximare este măsurat prin coeficientul de aproximare , care este definit ca raportul dintre soluția aproximată și cea optimă. S-a dovedit că aproximarea problemei k - centrului este NP-hard dacă coeficientul de aproximare este mai mic de 1,822 (pentru dimensiunea =2) [7] sau 2 (pentru dimensiunea >2) [6] .

Algoritmi

Solutie exacta

Există algoritmi care oferă o soluție exactă a problemei. Unul dintre acești algoritmi oferă o soluție în timp [8] [9] .

Aproximație 1 + ε

Aproximația 1 +  ε găsește o soluție cu un coeficient de aproximare care nu depășește 1 +  ε . O astfel de aproximare este NP-hard pentru ε arbitrar . S-a propus o abordare bazată pe conceptul de set de bază , cu complexitate de implementare [10] . Este disponibil un algoritm alternativ, de asemenea bazat pe seturi de bază. Funcționează în timp [11] . Autorul susține că timpul de rulare este mult mai mic decât cel mai rău caz și este posibil să se rezolve unele probleme în cazul k mic (să zicem,   k  < 5).

Selectarea punctelor îndepărtate

Din cauza complexității problemei, este imposibil să se caute o soluție exactă sau o aproximare apropiată. În schimb, pentru k mare , este utilizată pe scară largă o aproximare cu un factor de 2. Această aproximare este cunoscută sub denumirea de clustering în cel mai îndepărtat punct (FPC) sau ca algoritm de clustering în cel mai îndepărtat punct [6] . Algoritmul este destul de simplu - alegem un punct arbitrar al mulțimii ca centru, găsim cel mai îndepărtat din mulțimea rămasă și îl considerăm următorul centru. Continuăm procesul până când avem k centri.

Este ușor de observat că algoritmul rulează în timp liniar. Deoarece s-a dovedit că o aproximare cu un factor mai mic de 2 este NP-hard, BOT este considerată cea mai bună aproximare.

Complexitatea timpului de execuție a fost ulterior îmbunătățită la O( n  log  k ) folosind tehnica de descompunere a casetei [7] .

Plasarea maximă a obiectelor

Problema de plasare a obiectelor maximin caută o locație care maximizează distanțele minime față de laturi. În cazul metricii euclidiene, problema este cunoscută drept cea mai mare problemă de sferă goală . Cazul plat ( cel mai mare cerc gol ) poate fi rezolvat în timp Θ( n  \log n) [12] [13] .

Software gratuit pentru rezolvarea problemelor de plasare a obiectelor

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

Vezi și

• Centrul graficului
• Problemă de atribuire cuadratică
• algoritmul lui Dijkstra
• Locația obiectului (joc competitiv)

Note

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

Literatură

• Preparata F., Sheimos M. . Geometrie computațională: o introducere . - M .: Mir , 1989. - ISBN 5-03-001041-6 .
• Bādoiu M., Har-Peled S., Indyk P.  Aproximate clustering via core-sets  // Proceedings of the34th annual ACM symposium on Theory of Computing. - 2002. - P. 250-257.
• Csoke M. Problema locației unității . — Universitatea de Stat al Guvernatorilor, 2015.
• Feder T., Greene D.  Algoritmi optimi pentru gruparea aproximativă  // Proceedings of the twentieth annual ACM symposium on Theory of Computing. - 1988. - P. 434-444.
• Fowler R. J., Paterson M. S., Tanimoto S. L.  Ambalarea și acoperirea optime în avion sunt NP-complete // Scrisori de procesare a informațiilor. - 1981. - Vol. 12. - P. 133-137. - doi : 10.1016/0020-0190(81)90111-3 .
• Gonzalez T.  Clustering to minimize the maximum intercluster distance  // Teoretic Computer Science . - 1985. - Vol. 38. - P. 293-306. - doi : 10.1016/0304-3975(85)90224-5 . Arhivat din original pe 24 ianuarie 2013.
• Guha S., Khuller S.  Greedy Strikes Back: Algoritmi îmbunătățiți de locație a instalației // Journal of Algorithms. - 1999. - Vol. 31. - P. 228. - doi : 10.1006/jagm.1998.0993 .
• Hochbaum D. S.  Euristică pentru problema mediană a costurilor fixe // Programare matematică . - 1982. - Vol. 22. - P. 148-162. - doi : 10.1007/BF01581035 .
• Hwang R. Z., Lee R. C. T., Chang R. C.  Abordarea divizării plăcii pentru a rezolva problema euclidiană a centrului p  // Algorithmica. - 1993. - Vol. 9, nr. 1. - P. 1–22. - doi : 10.1007/BF01185335 .
• Hwang R. Z., Chang R. C., Lee R. C. T.  Strategia de căutare generalizată peste separatori pentru a rezolva unele probleme NP-Hard în timp subexponențial  // Algorithmica. - 1993. - Vol. 9, nr. 4. - P. 398-423. - doi : 10.1007/bf01228511 .
• Kumar P., Kumar P.  Soluții aproape optime pentru probleme de k-clustering  // International Journal of Computational Geometry & Applications. - 2010. - Vol. 20, nr. patru.
• Li Shi. . A 1.488. Algoritm de aproximare pentru problema locației instalației necapacitate // Automate, limbaje și programare. — Note de curs în Informatică . - 2011. - Vol. 6756.—P. 77–88. - ISBN 978-3-642-22011-1 . - doi : 10.1007/978-3-642-22012-8_5 .
• Megiddo N., Tamir A.  Despre complexitatea localizării instalațiilor liniare în plan  // Operations Research Letters. - 1982. - Vol. 1, nr. 5. - P. 194-197. - doi : 10.1016/0167-6377(82)90039-6 .
• Toussaint G. T.  Computing cele mai mari cercuri goale cu constrângeri de locație // International Journal of Computer and Information Sciences. - 1983. - Vol. 12, nr. 5. - P. 347-358.

Link -uri

• INFORMS secțiunea privind analiza locației , o societate profesională pentru studiul problemelor de locație.
• Bibliografie privind problemele de plasare , compilată de Trevor Hale și care conține peste 3400 de articole.
• Biblioteca de algoritmi de plasare
• Utilitar de plasare a producției în versiunea web)
• Placement Production Optimizer , un solutor de probleme de plasare a producției bazat pe MATLAB .