Problem pakovanja u prostoru

Problem pakovanja u prostoru podrazumeva pakovanje objekata različitih zapremina u konačno mnogo kontejnera sa ciljem da se minimizuje broj potrebnih kontejnera za skladištenje datih objekata. U teoriji složenosti ovaj problem se klasifikuje kao NP-težak problem. Postoje različite varijacije ovog problema, 2D Pakovanje, Linearno pakovanje, Pakovanje u odnosu na težinu, Pakovanje u odnosu na cenu itd. Oblasti u kojima se primenjuje rešenje ovog problema su: Popunjavanje kontejnera, Utovar u kamion sa zadatim težinskim ograničenjem, Pronalaženje optimalnog rasporeda predmeta u prostoru sa zadatim uslovima balansa itd.

Iako je problem klasifikovan kao NP-težak (što znači da za velike instance problema ne postoji egzaktni algoritam polinomijalne složenosti koji daje optimalno rešenje, osim ako P = NP) razvijeno je mnoštvo heuristika koje pronalaze zadovoljavajuća rešenja (bliska optimalnom, koja zadovoljavaju sve kriterijume pakovanja) u polinomijalnom vremenu. Većina opisanih heuristika koriste sortiranje kao krucijalni korak u algoritmu i time se postiže logaritamska složenost u odnosu na broj objekata ${O}(n\log n)$.

Formalna definicija problema

Problem pakovanja u prostoru se definiše na sledeći način, dato je $n$ elemenata (kvadrova) i neograničen broj identičnih kontejnera dimenzija $L\times W\times H$. Dimenzije $i$-tog objekta, $i=1\ldots n$, definišu se sa $l_{i}\times w_{i}\times h_{i}$. Pretpostavka je da se objekti ne mogu rotirati. Cilj je upakovati $n$ objekata tako da su ispunjeni sledeći uslovi:

• Svaka postavka predmeta mora biti ortogonalna (paralelna u odnosu na osu)
• Svaki objekat se mora nalaziti u potpunosti unutar kontejnera
• Za svaka dva objekta unutar istog kontejnera važi da se ne seku
• Potrebno je minimizovati broj potrebnih kontejnera

Pristup rešavanju problema

Jedan od glavnih problema koji se javljaju prilikom proučavanja ovog problema je kako na efikasan način odabrati poziciju objekta unutar prostora (kontejnera) tako da se pozicioniranjem objekta na odabrano mesto ne naruše ograničenja (balansa, redosleda, itd.) Performanse kao i kvalitet dobijenog rešenja algoritama koj se koristi za pakovanje objekata u velikoj meri zavisi od strategije za odabir tačaka koje određuju poziciju objekta. Heuristika koja je u dosadašnjem istraživanju proizvela najbolje rezultate, kako po pitanju efikasnosti tako i po kvalitetu krajnjih rešenja, uvodi koncept Ekstremnih tačaka koje predstavljaju skup potencijalnih pozicija na koje je moguće smestiti tekući objekat u odnosu na tekuću konfiguraciju.

Primenom prethodno opisane strategije dobijaju se kvalitetna rešenja približna optimalnom ali se takođe primećuju i nedostaci. Naime prilikom umetanja objekata dolazi do fragmentisanja prostora na ispunjen prostor (prostor koji zauzima trenutna konfiguracija objekata) i rezidualni prostor (prostor koji je slobodan za umetanje preostalih objekata). Moguće je da se prilikom umetanja objekta prostor fragmentiše tako da rezidualni prostor zapreminski može da prihvati tekući objekat ali ne postoji ni jedna ekstremna tačka u rezidualnom prostoru koja zadovoljava uslov da se nakon smeštanja objekta na njenu poziciju može izbeći presek sa nekim od objekata u trenutnoj konfiguraciji. Što čini umetanje tekućeg objekta nemogućim.

Prilikom rešavanja problema pakovanja u prostoru neophodno je dakle razmotriti dva suštinska podproblema:

1. Kako odabrati skup tačaka koje predstavljaju potencijalne pozicije objekta koji je potrebno spakovati?
2. Kako učiniti da rezidualni prostor bude što bolje iskorišćen?

Heuristika umetanja korišćenjem ekstremnih tačaka

Heuristika umetanja korišćenjem ekstremnih tačaka je konstruktivna heuristika koja umeće objekte redom, jedan po jedan u odnosu na zadatu sekvencu objekata dok svi objekti nisu umetnuti u prostor (kontejner). Ova heuristika je trenutno najbolja u ovom domenu. Koncept ekstremnih tačaka posmatra prostor kao listu ekstremnih tačaka, gde svaka tačka predstavlja potencijalnu poziciju za umetanje novog objekta. Prazan prostor (kontejner) se posmatra kao lista koja sadrži samo jednu ekstremnu tačku $(0,0,0)$. Umetanje novog objekta povlači zauzimanje jedne ekstremne tačke iz liste i uvođenje konstantnog broja novih tačaka. Slika 1(a) i 1(b) ilustruju uvođenje 2 odnosno 6 ekstremnih tačaka umetanjem novog objekta za (redom) 2D i 3D slučaj.

Za zadatu sekvencu objekata opisana heuristika pokušava da umetne objekat na ekstremnu tačku u postojećem prostoru. Ukoliko ne postoji ekstremna tačka koja zadovoljava kriterijume, instancira se novi prostor (kontejner) i objekat se umeće na poziciju $(0,0,0)$. Postupak se ponavlja dok se ne umetnu svi objekti. Prirodno može postojati podskup skupa ekstremnih tačaka koji zadovoljava uslove umetanja u tom slučaju potrebno je odabrati strategiju za odabir neke od potencijalnih tačaka. Neke od strategija su: Najmanje euklidsko rastojanje, Odabir prve tačke koja zadovoljava kriterijume, itd.

Heuristika za defragmentisanje prostora

Glavni cilj kod problema pakovanja u prostoru je dobijanje gustih konfiguracija čime se postiže visoka iskorišćenost datog prostora za pakovanje. Konstrukcijom gustih konfiguracija objekata prirodno se smanjuje broj potrebnih kontejnera za smeštanje objekata iz sekvence. Heuristika za defregmentisanje prostora u suštini pokušava da postavi objekat $i$ na poziciju $p$, ukoliko je pozicija $p$ zauzeta (na poziciji $p$ se nalazi neki od objekata iz trenutne konfiguracije) heuristika translira sve objekte maksimalno u odnosu na koordinatni početak kako bi se napravilo mesto za novi objekat. Prilikom implementiranja ovog postupka prvo je potrebno utvrditi da li ovjekat i može da se postavi na poziciju a zatim i mora biti postavljen na poziciju $p$.

Da bi se navedeni postupak sproveo posmatraju se geometrijska svojstva objekata, za svaki objekat se posmatra njegova projekcija na $x$ $y$ i $z$ osu. Postupak je dovoljno opisati za jednu od osa za preostale se postupak sprovodi analogno. Za sbaki objekat $i$ posmatra se njegova projekcija na $x$ osu označena sa $[{\underline {x}}_{i},{\overline {x}}_{i}]$, skup projekcija nazivaće se skup krajnjih tačaka. Postupak se može definisati na sledeći način zamišljajući vertikalnu liniju koja se kreće zdesna ulevo:

1. Sortirati skup od $2n$ krajnjih tačaka, levi krajevi se porede ukoliko su desni jednaki.
2. Vertikalna linija u svakom trenutku definiše skup intervala koji se nalaze potpuno levo od objekta $i$, $L_{x}=\left\{i|{\overline {x}}_{i}<x\right\}$ gde je $x$ pozicija vertikalne linije.
3. Vertikalna linija ažurira graničnu vrednost $x0$ koja predstavlja najveću vrednost desnog kraja za sve intervale iz $L_{x}$
4. Kada vertikalna linija skenira ${\overline {x}}_{i}$ ažurira se $\Delta X_{i}=x0-{\overline {x}}_{i}$
5. Kada vertikalna linija skenira ${\underline {x}}_{i}$ ažurira se $x0=\min(x0,{\underline {x}}_{i}+\Delta X_{i})$

Vidi još

• Problemi pakovanja
• Problem ranca
• Optimizacioni problemi

Reference

1. Vazirani, Vijay V. (2003), Approximation Algorithms, Berlin: Springer, ISBN 978-3-540-65367-7 
2. Yue, Minyi (oktobar 1991), „A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm”, Acta Mathematicae Applicatae Sinica, 7 (4): 321—331, ISSN 0168-9673, S2CID 189915733, doi:10.1007/BF02009683  CS1 održavanje: Datum i godina (veza)CS1 održavanje: Format datuma (veza)
3. Dósa, György (2007), „The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9”, Ur.: Chen, Bo; Paterson, Mike; Zhang, Guochuan, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science, 4614/2007, Springer Berlin / Heidelberg, str. 1—11, ISBN 978-3-540-74449-8, ISSN 0302-9743, doi:10.1007/978-3-540-74450-4 
4. Xia, Binzhou; Tan, Zhiyi (2010), „Tighter bounds of the First Fit algorithm for the bin-packing problem”, Discrete Applied Mathematics, 158 (15): 1668—1675, ISSN 0166-218X, doi:10.1016/j.dam.2010.05.026 
5. Garey, Michael R.; Johnson, David S. (1985), „A 71/60 theorem for bin packing*1”, Journal of Complexity, 1: 65—106, doi:10.1016/0885-064X(85)90022-6 
6. Yue, Minyi; Zhang, Lei (jul 1995), „A simple proof of the inequality MFFD(L)≤71/60 OPT(L) + 1,L for the MFFD bin-packing algorithm”, Acta Mathematicae Applicatae Sinica, 11 (3): 318—330, ISSN 0168-9673, S2CID 118263129, doi:10.1007/BF02011198  CS1 održavanje: Datum i godina (veza)CS1 održavanje: Format datuma (veza)
7. Fernandez de la Vega, W.; Lueker, G. S. (decembar 1981), „Bin packing can be solved within 1 + ε in linear time”, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, ISSN 0209-9683, S2CID 10519631, doi:10.1007/BF02579456  CS1 održavanje: Datum i godina (veza)CS1 održavanje: Format datuma (veza)
8. Lewis, R. (2009), „A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing” (PDF), Computers and Operations Research, 36 (7): 2295—2310, S2CID 1577334, doi:10.1016/j.cor.2008.09.004 
9. Silvano Martello and Paolo Toth (1990), Knapsack Problems Algorithms and Computer Implementations.

• Michael R. Garey and David S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. . 1979. ISBN 978-0-7167-1045-5.  A4.1: SR1. str. 226.

1. David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms. SICOMP, Volume 3, Issue 4. 1974.
2. Lodi A., Martello S., Monaci, M., Vigo, D. (2010) Two-Dimensional Bin Packing Problems. In V.Th. Paschos (Ed.), “Paradigms of Combinatorial Optimization”, Wiley/ISTE. str. 107-129
3. Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
4. Sindelar, Michael; Sitaraman, Ramesh; Shenoy, Prashant (2011), „Sharing-Aware Algorithms for Virtual Machine Colocation”, Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Jose, CA, June 2011: 367—378