Проблем паковања у простору

Проблем паковања у простору подразумева паковање објеката различитих запремина у коначно много контејнера са циљем да се минимизује број потребних контејнера за складиштење датих објеката. У теорији сложености овај проблем се класификује као NP-тежак проблем. Постоје различите варијације овог проблема, 2Д Паковање, Линеарно паковање, Паковање у односу на тежину, Паковање у односу на цену итд. Области у којима се примењује решење овог проблема су: Попуњавање контејнера, Утовар у камион са задатим тежинским ограничењем, Проналажење оптималног распореда предмета у простору са задатим условима баланса итд.

Иако је проблем класификован као NP-тежак (што значи да за велике инстанце проблема не постоји егзактни алгоритам полиномијалне сложености који даје оптимално решење, осим ако P = NP) развијено је мноштво хеуристика које проналазе задовољавајућа решења (блиска оптималном, која задовољавају све критеријуме паковања) у полиномијалном времену. Већина описаних хеуристика користе сортирање као круцијални корак у алгоритму и тиме се постиже логаритамска сложеност у односу на број објеката ${O}(n\log n)$.

Формална дефиниција проблема

Проблем паковања у простору се дефинише на следећи начин, дато је $n$ елемената (квадрова) и неограничен број идентичних контејнера димензија $L\times W\times H$. Димензије $i$-тог објекта, $i=1\ldots n$, дефинишу се са $l_{i}\times w_{i}\times h_{i}$. Предпоставка је да се објекти не могу ротирати. Циљ је упаковати $n$ објеката тако да су испуњени следећи услови:

• Свака поставка предмета мора бити ортогонална (паралелна у односу на осу)
• Сваки објекат се мора налазити у потпуности унутар контејнера
• За свака два објекта унутар истог контејнера важи да се не секу
• Потребно је минимизовати број потребних контејнера

Приступ решавању проблема

Један од главних проблема који се јављају приликом проучавања овог проблема је како на ефикасан начин одабрати позицију објекта унутар простора (контејнера) тако да се позиционирањем објекта на одабрано место не наруше ограничења (баланса, редоследа, итд.) Перформансе као и квалитет добијеног решења алгоритама кој се користи за паковање објеката у великој мери зависи од стратегије за одабир тачака које одређују позицију објекта. Хеуристика која је у досадашњем истраживању произвела најбоље резултате, како по питању ефикасности тако и по квалитету крајњих решења, уводи концепт Екстремних тачака које представљају скуп потенцијалних позиција на које је могуће сместити текући објекат у односу на текућу конфигурацију.

Применом претходно описане стратегије добијају се квалитетна решења приближна оптималном али се такође примећују и недостаци. Наиме приликом уметања објеката долази до фрагментисања простора на испуњен простор (простор који заузима тренутна конфигурација објеката) и резидуални простор (простор који је слободан за уметање преосталих објеката). Могуће је да се приликом уметања објекта простор фрагментише тако да резидуални простор запремински може да прихвати текући објекат али не постоји ни једна екстремна тачка у резидуалном простору која задовољава услов да се након смештања објекта на њену позицију може избећи пресек са неким од објеката у тренутној конфигурацији. Што чини уметање текућег објекта немогућим.

Приликом решавања проблема паковања у простору неопходно је дакле размотрити два суштинска подпроблема:

1. Како одабрати скуп тачака које представљају потенцијалне позиције објекта који је потребно спаковати?
2. Како учинити да резидуални простор буде што боље искоришћен?

Хеуристика уметања коришћењем екстремних тачака

Хеуристика уметања коришћењем екстремних тачака је конструктивна хеуристика која умеће објекте редом, један по један у односу на задату секвенцу објеката док сви објекти нису уметнути у простор (контејнер). Ова хеуристика је тренутно најбоља у овом домену. Концепт екстремних тачака посматра простор као листу екстремних тачака, где свака тачка представља потенцијалну позицију за уметање новог објекта. Празан простор (контејнер) се посматра као листа која садржи само једну екстремну тачку $(0,0,0)$. Уметање новог објекта повлачи заузимање једне екстремне тачке из листе и увођење константног броја нових тачака. Слика 1(а) и 1(б) илуструју увођење 2 односно 6 екстремних тачака уметањем новог објекта за (редом) 2Д и 3Д случај.

За задату секвенцу објеката описана хеуристика покушава да уметне објекат на екстремну тачку у постојећем простору. Уколико не постоји екстремна тачка која задовољава критеријуме, инстанцира се нови простор (контејнер) и објекат се умеће на позицију $(0,0,0)$. Поступак се понавља док се не уметну сви објекти. Природно може постојати подскуп скупа екстремних тачака који задовољава услове уметања у том случају потребно је одабрати стратегију за одабир неке од потенцијалних тачака. Неке од стратегија су: Најмање еуклидско растојање, Одабир прве тачке која задовољава критеријуме, итд.

Хеуристика за дефрагментисање простора

Главни циљ код проблема паковања у простору је добијање густих конфигурација чиме се постиже висока искоришћеност датог простора за паковање. Конструкцијом густих конфигурација објеката природно се смањује број потребних контејнера за смештање објеката из секвенце. Хеуристика за дефрегментисање простора у суштини покушава да постави објекат $i$ на позицију $p$, уколико је позиција $p$ заузета (на позицији $p$ се налази неки од објеката из тренутне конфигурације) хеуристика транслира све објекте максимално у односу на координатни почетак како би се направило место за нови објекат. Приликом имплементирања овог поступка прво је потребно утврдити да ли овјекат и може да се постави на позицију а затим и мора бити постављен на позицију $p$.

Да би се наведени поступак спровео посматрају се геометријска својства објеката, за сваки објекат се посматра нјегова пројекција на $x$ $y$ и $z$ осу. Поступак је довољно описати за једну од оса за преостале се поступак спроводи аналогно. За сбаки објекат $i$ посматра се нјегова пројекција на $x$ осу означена са $[{\underline {x}}_{i},{\overline {x}}_{i}]$, скуп пројекција називаће се скуп крајњих тачака. Поступак се може дефинисати на следећи начин замишљајући вертикалну линију која се креће са десна у лево:

1. Сортирати скуп од $2n$ крајњих тачака, леви крајеви се пореде уколико су десни једнаки.
2. Вертикална линија у сваком тренутку дефинише скуп интервала који се налазе потпуно лево од објекта $i$, $L_{x}=\left\{i|{\overline {x}}_{i}<x\right\}$ где је $x$ позиција вертикалне линије.
3. Вертикална линија ажурира граничну вредност $x0$ која представља највећу вредност десног краја за све интервале из $L_{x}$
4. Када вертикална линија скенира ${\overline {x}}_{i}$ ажурира се $\Delta X_{i}=x0-{\overline {x}}_{i}$
5. Када вертикална линија скенира ${\underline {x}}_{i}$ ажурира се $x0=\min(x0,{\underline {x}}_{i}+\Delta X_{i})$

Види још

• Проблеми паковања
• Проблем ранца
• Оптимизациони проблеми

Референце

1. Vazirani, Vijay V. (2003), Approximation Algorithms, Berlin: Springer, ISBN 3-540-65367-8 
2. Yue, Minyi (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, doi:10.1007/BF02009683 
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”, Ур.: Chen, Bo; Paterson, Mike; Zhang, Guochuan, Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, 4614/2007, Springer Berlin / Heidelberg, стр. 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 (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, doi:10.1007/BF02011198 
7. Fernandez de la Vega, W.; Lueker, G. S. (1981), „Bin packing can be solved within 1 + ε in linear time”, Combinatorica, Springer Berlin / Heidelberg, 1 (4): 349—355, ISSN 0209-9683, doi:10.1007/BF02579456 
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”, Computers and Operations Research, 36 (7): 2295—2310, doi:10.1016/j.cor.2008.09.004 
9. Silvano Martello and Paolo Toth (1990), Knapsack Problems Algorithms and Computer Implementations.
10. Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.
11. 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.
12. 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, p. 107-129
13. Dósa G., Sgall J. (2013) First Fit bin packing: A tight analysis. To appear in STACS 2013.
14. 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