Alkalmazott Matematikai Lapok 31 (2014),

Alkalmazott Matematikai Lapok 31 (2014), 99-108.

´ ´ ¨ ¨ OPTIMALIS VODR OK PAKOLASA RAKLAPOKRA ´ KOZMA ATTILA1 CSENDES TIBOR ES

Egy nyomdaipari sz´ all´ıt´ asi probl´em´ ab´ ol kiindulva a raklapra val´ o k¨ orpakol´ as feladat´ ara olyan elj´ ar´ ast mutatunk be, amely k´epes re´ alis sz´ am´ıt´ asi id˝ o felhaszn´ al´ as´ aval k¨ ozel optim´ alis megold´ asokat adni. Megadjuk a tal´ alt pakol´ asokat a 80 × 120 ar´ any´ u t´eglalapba n = 1 − 50 k¨ orre, ´es ´ attekintj¨ uk a kapott megold´ asok tulajdons´ agait. T´ argyaljuk az eredm´enyek lehets´eges alkalmaz´ asai felt´eteleit ´es eredm´enyess´eg´et.

A feladat A n´egyzetbe val´ o k¨ orpakol´ asi feladatok megold´as´aban el´ert eredm´enyeink [3, 4, 5, 7, 8, 9] alapj´ an megkeresett benn¨ unket egy nyomdai fest´ekeket forgalmaz´o belga c´eg a k¨ ovetkez˝ o probl´em´ aval. A fest´ekeiket v¨odr¨okben ´arulj´ak, azokat raklapokra (l´asd az 1. ´abr´ at), nyilv´ an ´atlapol´as n´elk¨ ul ´es a kil´og´ast ker¨ ulve rakodt´ak. M´egis azt tapasztalt´ ak, hogy a minim´ alis kil´og´as a kamionra val´o pakol´as sor´an azt eredm´enyezte, hogy a v¨ odr¨ ok teteje felny´ılt, ´es a fest´ek egyr´eszt k´arba veszett, m´ asr´eszt a tiszt´ıt´ as miatt extra k¨ olts´egek ´alltak el˝o. T˝ol¨ unk azt k´erdezt´ek, hogy adott m´eret˝ u v¨ odr¨ okb˝ ol mennyi helyezhet˝ o el a 80×120 centim´eteres Euro-raklapra, illetve hogy adott darabsz´ am´ u v¨ odr¨ ot el˝ o´ırva raklaponk´ent mi a maxim´alis ´atm´er˝oje azoknak a v¨ odr¨ oknek, amivel azok m´eg megfelel˝oen elhelyezhet˝ok. A probl´ema teh´ at az, hogy egy 80 × 120 oldalar´any´ u t´eglalap alak´ u ter¨ uleten hogyan helyezz¨ unk el azonos m´eret˝ u, adott sz´am´ u k¨or¨oket u ´gy, hogy azok ne fedj´ek ´at egym´ ast, ´es ne is l´ogjanak t´ ul a t´eglalap oldalain – ´es a k¨or¨ok ´altal lefedett ter¨ ulet maxim´ alis legyen.

Az algoritmus A megold´ ashoz Eckard Specht n´egyzetbe val´o k¨orpakol´asra kifejlesztett programj´ at [6, 10] igaz´ıtottuk ´at. Megjegyezz¨ uk, hogy a feltett k´erd´esek megv´alaszol´ asa m´eg nem elegend˝ o az optim´alis rakod´ashoz, mert a kapott optim´ alis elhelyez´es a legt¨ obb esetben nagyon szab´alytalan. Emiatt azok rutinszer˝ u kirak´asa nem 1 K¨ osz¨ onetnyilv´ an´ıt´ as: A kutat´ ast t´ amogatta a Telemedic´ına f´ okusz´ u kutat´ asok Orvosi, ´ Matematikai ´ es Informatikai tudom´ anyter¨ uleteken (TOMI) c´ım˝ u p´ aly´ azat: TAMOP-4.2.2.A11/1/KONV-2012-0073.

Alkalmazott Matematikai Lapok (2014)

100

´ KOZMA ATTILA CSENDES TIBOR ES

v´arhat´ o el a rakod´ okt´ ol. Az optim´alis elhelyez´esek megad´asa m´ar seg´ıthet, de a val´ odi megold´ ast val´ osz´ın˝ uleg az u ´n. r´acspakol´asok jelentik, amelyek szab´alyoss´aguk miatt k¨ onnyen alkalmazhat´ok. Az eredm´enyeink persze b´armilyen k¨or alap´ u ´aru eset´en haszn´ alhat´ ok. Algoritmus. PDS-algoritmus (Pulsating Disk Shaking) ´ ıtsunk el˝ 0. l´ep´es: All´ o egy lehets´eges megold´ast random m´odon. Legyen az aktu´ alis sug´ ar r, epszilon pozit´ıv sz´am, egy kis konstans ´ert´ek, tov´abb´a M := 0 az ´atfed´es ´es a t´ ulny´ ul´as m´ert´eke. k := 0. 1. l´ep´es: k := k + 1, r := r + ǫ. Ha k > MAXIT, vagy a pulz´al´as amplit´ ud´oja megfelel˝ oen kicsi, akkor STOP. 2. l´ep´es: R´ azzuk ¨ ossze az aktu´alis konfigur´aci´ot. Ha az M ´atfed´es nem n˝ott az el˝ oz˝ o iter´ aci´ ohoz k´epest, akkor folytassuk az 1. l´ep´essel. 3. l´ep´es: r := r − ǫ. Folytassuk az 1. l´ep´essel.

1. ´ abra. Az EUR raklap. Az algoritmus el˝ onye, hogy a fut´asi id˝o nagy r´esz´eben lehets´eges megold´asok k¨oz¨ ott v´ alogat, ´ıgy a felt´eteleknek val´o megfelel´es megteremt´ese viszonylag kev´es id˝ ot visz el - szemben m´ as elj´ ar´asokkal. Maga a program sztochasztikus jelleg˝ u, teh´ at k¨ ozel´ıt˝ o megold´ as szolg´altat´as´ara k´epes. Emiatt bizony´ıtottan optim´alis elhelyez´est puszt´ an erre t´ amaszkodva nem kaphatunk. M´asr´eszt sz´amos neh´ez probl´em´ ara kaptuk m´ar meg ezzel az optim´alis megold´ast r¨ovid id˝o alatt, amit azt´ an egy megb´ızhat´ o sz´ am´ıt´ og´epes elj´ar´assal k¨onnyebb volt verifik´alni, mint az ut´ obbival azt el˝ o is ´all´ıtani (v¨ o. [9]). Alkalmazott Matematikai Lapok (2014)

´ ´ ¨ ¨ OPTIMALIS VODR OK PAKOLASA RAKLAPOKRA

101

Az egyszer˝ u algoritmusunk m´ar sikeresnek bizonyult sz´amos k¨orpakol´asi feladat megold´ as´ ara. Megvizsg´ altuk a feladatunkat Jozef Kallrath u ´j, GAMS ´es Baron alap´ u elj´ ar´ as´ aval is [1, 2], de az azzal kapott eredm´enyek egyr´eszt nem voltak megb´ızhat´ ok, m´asr´eszt szinte mindig gyeng´ebb k¨ozel´ıt´eseket kaptunk csak.

Eredm´ enyek Az elj´ ar´ ast N = 1 − 50 darab k¨orre futtattuk le. A kapott eredm´enyek csak j´o lehets´eges megold´ asok, de ezek optimalit´asa m´ar nem garant´alt. Persze az optimumt´ ol val´ o kis elt´er´es a gyakorlati alkalmaz´asban ´altal´aban elfogadhat´o. M´asr´eszt t´enyleges rakod´ ashoz csak az olyan konfigur´aci´ok haszn´alhat´ok, melyek valamilyen k¨ onnyen ´erv´enyes´ıthet˝ o szab´alyszer˝ us´eget tartalmaznak. A kapott eredm´enyek egy r´esz´et a 2–4. ´abr´ ak mutatj´ak. Nem szimmetrikus konfigur´aci´ok tartoznak ezekb˝ol az n = 7, 10, 14, 17, 19, 21, ´ 22, 23, 26, 27, 29 ´ert´ekekhez (30-ig, l´asd az 1. t´abl´azatot). Erdekes, hogy viszonylag milyen sok szimmetrikus elhelyez´est tal´altunk, b´ar a nagyobb k¨orsz´amok eset´en egyre kevesebb van. Ez ¨ osszhangban van a s´ıkon val´o optim´alis k¨orpakol´asra vonatkoz´ o elm´eleti eredm´ennyel. N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

r 40.000 30.718 24.0408 22.005 20.3992 20.000 17.1786 16.3175 15.2646 14.8085 14.721 13.8538 13.3348 12.806 12.3107

szimmetria X X X X X X

r´acs

X X

X X

X X X

X X X

X

X

X X X X X

N 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

r 11.7294 11.4808 11.3291 11.0779 10.9677 10.5439 10.2746 10.1396 10.000 9.77135 9.45412 9.29373 9.2196 9.06494 9.02455

szimmetria X

r´acs

X

X

X

X

X X

X

X X

1. t´ abl´ azat. Az N darab k¨ or elhelyez´es´enek adatai: a tal´alt legnagyobb sug´ar, ´es annak megjel¨ ol´ese, hogy az adott pakol´as szimmetrikus-e, illetve r´acspakol´as-e. Alkalmazott Matematikai Lapok (2014)

102

´ KOZMA ATTILA CSENDES TIBOR ES

A t´ abl´ azatban megadott kapott sug´ar´ert´ekek j´ol t¨ ukr¨ozik azokat a helyzeteket, amikor v´ arhat´ o megold´ as sz¨ uletett (mint p´eld´aul az n = 1, 6 ´es 24 k¨or eset´en). Megjegyzend˝ o az is, hogy a 6 ´es 24 k¨or optim´alis pakol´asa egyben az ipari standarddal is egyezik, ugyanis eszerint csomagolj´ak a k¨ ul¨onf´ele italokat. Az ´abr´ akon az adott pontoss´aggal egym´assal ´erintkez˝o k¨or¨oket szaggatott vonalak jelzik. Az egyes k¨ or¨ ok sz´ıne a k¨or tulajdons´ag´at t¨ ukr¨ozi: a szabad k¨or¨ok (amelyek mozgathat´ ok kicsit, ´es a pakol´as s˝ ur˝ us´ege emiatt nem v´altozik, az els˝o p´elda a 7 k¨ or pakol´ as´ at mutat´ o rajzon l´athat´o a 2. ´abr´an) a legs¨ot´etebbek. Az egyes pakol´ asok felirat´ at a program maga gener´alta, ez´ert azok angolul vannak. Az ´abrafeliratok megadj´ ak a k¨ or¨ ok sugar´at (angolul radius), a pontpakol´asi feladat alakra vonatkoz´ oan a pontok t´ avols´ againak minimum´at (distance), a k¨orpakol´as s˝ ur˝ us´eg´et (density), valamint az eml´ıtett ´ertelemben vett ´erintkez´esek, kapcsolatok sz´am´at (contacts). A 45 k¨ or eset´en l´ athat´olag m´eg el´erhet˝o s˝ ur˝ ubb pakol´as is. A teljes s´ıkon optim´ alis k¨ orpakol´asi minta, a m´ehsejt szerkezet˝ u, hexagon´alis pakol´ as el˝ osz¨ or a 31 k¨ ornek a 80 × 120 ar´any´ u t´eglalapba val´o elhelyez´ese sor´an jelentkezik. Ez ¨ osszhangban van azzal az ´eszrev´etellel, amit a n´egyzetbe val´o pakol´ as sor´ an tett¨ unk ([9]): a k¨orsz´am n¨oveked´es´evel a hexagon´alis t´abl´akb´ol ´all´o r´eszstrukt´ ur´ ak uralj´ ak el fokozatosan a v´eges tartom´anyon vett pakol´asokat, ´es ezeket a t´ abl´ akat eg´esz´ıtik ki ezekhez illeszked˝o k¨or¨ok. A kapott eredm´enyek optimalit´asa nem igazolt, teh´at ezt intervallum aritmetik´ara ´ep¨ ul˝ o elj´ ar´ asokkal kell verifik´alni, mint amilyen elj´ar´asokat a n´egyzetbe val´o pakol´ asok egyes egyszer˝ ubb eseteiben meg tett¨ unk (l´asd [4, 5, 7, 8]). Ebb˝ol a szempontb´ ol tanuls´ agos, hogy a k¨ ul¨onben elfogadott GAMS–Baron m´odszertan (amilyent az [1, 2] k¨ ozlem´enyek alkalmaztak) milyen gyakran adott nem optim´alis, ´es az optimalit´ asi r´est illet˝ oen f´elrevezet˝o eredm´enyt. A sug´ar ´ert´ekek szigor´ uan monoton m´odon cs¨ okkennek a n¨ovekv˝o k¨orsz´ammal. Ez a tulajdons´ag ´altal´aban term´eszetesnek mondhat´ o, b´ar van ezen szab´aly al´ol kiv´etel, p´eld´aul a k¨orbe k¨orpakol´ as n = 6 ´es 7 esetei azonos sug´arral adj´ak az optim´alis elhelyez´est. Ezzel egy¨ utt ez ut´ obbi jelens´eg kiv´etelesnek sz´am´ıt.

Alkalmaz´ as 1. Megjegyzend˝ o, hogy a gyakorlati alkalmaz´ast tov´abbi t´enyez˝ok is befoly´asolj´ak. ´Igy a hasonl´ o rakod´ as sor´ an haszn´alt zsugorf´olia vagy p´ant a helyesen lerakott elhelyez´est elronthatja. Ezek a hat´asok az adott szerkezetet nyilv´anval´oan a k¨orbe ´ırt pakol´ asok ir´ any´ aban torz´ıtj´ ak. Emiatt a helyesen elhelyezett v¨odr¨ok vagy hord´ok a raklapr´ ol lel´ oghatnak, ´es ´epp a megb´ız´o ´altal kifog´asolt jelens´eg jelentkezik, az ´aru s´er¨ ul, ´es ar´anytalanul nagy k¨olts´egn¨oveked´est okozhat. Az al´abb mutatott optim´ alis elhelyez´esek r¨ ogz´ıt´es´et u ´gy kell megoldani, hogy az a fentieknek megfelel˝ oen ne torzuljon olyann´ a, ami megs´erti a befoglal´o t´eglalap hat´ar´at. A tal´ alt el˝ ony¨ os pakol´ asi mint´ak sokszor nehezen szerkeszthet˝ok, emiatt a pakol´ as kialak´ıt´ asa neh´ezs´eget jelenthet. Az ´altal´aban nem racion´ alis sz´ammal adott Alkalmazott Matematikai Lapok (2014)

´ ´ ¨ ¨ OPTIMALIS VODR OK PAKOLASA RAKLAPOKRA

103

2. ´ abra. A raklap pakol´ asra kapott k¨ozel optim´alis megold´asok az n = 3 − 10 esetekre. A r´esz´ abr´ akon szerepel a sug´ar, a s˝ ur˝ us´eg, a pont pakol´asi t´avols´ag ´es az ´erint´esek sz´ ama. Alkalmazott Matematikai Lapok (2014)

104

´ KOZMA ATTILA CSENDES TIBOR ES

3. ´ abra. A raklap pakol´ asra kapott k¨ozel optim´alis megold´asok az n = 11 − 18 esetekre. Alkalmazott Matematikai Lapok (2014)

´ ´ ¨ ¨ OPTIMALIS VODR OK PAKOLASA RAKLAPOKRA

105

4. ´ abra. A raklap pakol´ asra kapott k¨ozel optim´alis megold´asok az n = 19 − 26 esetekre. Alkalmazott Matematikai Lapok (2014)

106

´ KOZMA ATTILA CSENDES TIBOR ES

koordin´ at´ ak, valamint a t´enyleges elhelyez´es technikai gondjai miatt a pakol´asok megval´ os´ıt´ as´ ara k¨ ul¨ on gondot kell ford´ıtani. E c´elb´ol el˝ore nyomott pap´ırt vagy vet´ıt´est lehet alkalmazni. 2. A gyakorlati hasznos´ıt´ as szempontj´ab´ol kit˝ untetett jelent˝os´eg˝ uek az u ´gy nevezett r´ acspakol´ asok [9], amelyekben a k¨or¨ok k¨oz´eppontjai egy a t´eglalapra fektetett r´ acs egyes szab´ alyosan elhelyezked˝o r´acspontjai. A jelen k¨ozlem´enyben megadottak nem mind ilyenek (jellemz˝o ilyen p´elda az itt ´altalunk megadott pakol´as a 11, illetve a 12 k¨ orre). Amennyiben minden k¨orsz´amra ilyeneket akarunk megadni, akkor az ennek megfelel˝ o tov´abbi felt´eteleket be kell ´ep´ıteni a matematikai modellbe, ´es az optimaliz´ al´ ast ennek megfelel˝oen v´egrehajtani. Ezt a most alkalmazott elj´ ar´ as nem t´ amogatja, de bizonyos szempontb´ol egyszer˝ ubb az optim´alis r´acspakol´ asok meghat´ aroz´ asa, mint az ´altal´anos alak´ uak´e. A r´ acspakol´ asok lerak´ asa egyszer˝ u: a v¨odr¨oket vagy hord´okat soronk´ent lehet elhelyezni, ´es az egym´ ast k¨ ovet˝ o sorokat szabad az ´erintkez´esig elcs´ usztatni. Ez az elj´ ar´ as a pakol´ as szerkezete miatt nem okozhatja azt´an a t´arol´oed´enyek t´ ull´og´as´at a raklap hat´ arain. Ennek ellen´ere az 1. pontban eml´ıtett technikai seg´edeszk¨oz¨ok itt is seg´ıthetnek az optim´ alis pakol´asnak megfelel˝o elhelyez´es megtal´al´as´aban. 3. A bemutatott k¨ orpakol´ asokkal el´erhet˝o megtakar´ıt´as ¨onmag´aban nem felt´etlen jelent˝ os, mind¨ ossze p´ ar sz´azal´ekos lehet. Ennek ellen´ere egyes esetekben ez azt eredm´enyezheti, hogy kevesebb sz´all´ıt´oeszk¨ozzel lehet megoldani az adott ´aru megrendel˝ oh¨ oz val´ o tov´ abb´ıt´ as´ at. M´asr´eszt ezek haszn´alata nyilv´an ´esszer˝ u, ´es k¨ ul¨on k¨ olts´eget nem jelent, m´ıg k¨ ozben megtakar´ıt´ast ´erhet¨ unk el vel¨ uk. Eml´ıt´esre m´elt´o itt az a megjegyz´es, ami hasonl´o logisztikai feladatok megold´as´aban ´altal´anosan elfogadott szakmai tervez´esi elv, miszerint sokszor ´erdemes a sz´ all´ıt´oeszk¨oz¨ok minimaliz´ al´ as´ ara t¨ orekedni az egy´eb ´esszer˝ u szempontok helyett (a lehet˝o legkisebb szem´elyi kiad´ asok, minim´ alis k¨olts´eg, legr¨ovidebb teljes rakod´asi id˝otartam stb.). 4. Felmer¨ ulhet, hogy az ´altalunk is t´argyalt k¨or darabsz´amok t´ ul nagyok, ennyi hengeres dobozt, v¨ odr¨ ot vagy hord´ot nem szok´as ebben a form´aban csomagolni. Ez jogos, k¨ ul¨ on¨ osen nagy k¨ orsz´ amra ´es abban az esetben, ha nincsenek olyan eszk¨ozeink, amivel biztos´ıtani tudjuk, hogy a raklap hat´arain ne cs´ usszanak k´ıv¨ ul a t´ arol´ oed´enyek. Term´eszetesen a t´eglalapba val´o k¨orpakol´as m´as alkalmaz´asai eset´en, amit a k¨ ovetkez˝ o pontban t´argyalunk r¨oviden, ezek az ´ervek kev´esb´e hatnak. Az a gy´ art´ asi elj´ ar´ as, amely a g´epsorokr´ol lej¨ov˝o k¨or alap´ u csomagol´as´ u term´ekeket kis darabsz´ amban a raklapn´al l´enyegesen kisebb egys´egekbe csomagolja, majd ezeket rendezi a raklapra, k¨ozvetve szint´en t´amaszkodik a t´eglalapba val´o k¨orpakol´ asra. A raklapn´ al kisebb m´eret˝ u csomagok kialak´ıt´asa mellett sz´ol az, hogy ezek k´ezzel jobban rakodhat´ok. Term´eszetesen ezek a kisebb m´eret˝ u pakol´asi feladatok is megoldhat´ ok az ismertetett m´odszerrel, s˝ot adott esetben a t´eglalap oldalai hossza ar´ any´ anak egyez´ese eset´en az eredm´enyeink k¨ozvetlen¨ ul is haszn´alhat´ ok erre az esetre is. 5. M´as alkalmaz´ asok is vannak a t´eglalapba val´o k¨orpakol´as eredm´enyeinek hasznos´ıt´ as´ ara. A pakol´ asi feladatoknak megfeleltethet˝ok a szab´asi feladatok, ameAlkalmazott Matematikai Lapok (2014)

´ ´ ¨ ¨ OPTIMALIS VODR OK PAKOLASA RAKLAPOKRA

107

lyek adott nyersanyagb´ ol a lehet˝o legnagyobb m´eret˝ u v´egterm´ekek kiv´ag´as´at, vagy ennek megfelel˝ o m´odon adott t´eglalap alak´ u nyersanyagb´ol a legt¨obb adott m´eret˝ u ´ ekes nyersanyag eset´en az ´ıgy el´erhet˝o megtav´egterm´ek leszab´ as´ at c´elozz´ ak. Ert´ kar´ıt´ as tetemes lehet. A bemutatott m´odszertan az ´altalunk t´argyaltt´ol elt´er˝o esetekben is alkalmazhat´ o. Bolyai Farkas is t´ argyalta a k¨orpakol´asi feladatok olyan alkalmaz´as´at, amelyek adott k´etdimenzi´ os alakzatba (n´egyzetbe, t´eglalapba vagy h´aromsz¨ogbe) egybev´ ag´ o k¨ or¨ ok olyan nem ´atlapol´ o elhelyez´es´et kereste, hogy a k¨or¨ok sugara maxim´alis ˝ ezt egy tervezett erd´eszi ´all´as p´aly´azat´ahoz vizsg´alta. A k¨or¨ok szerep´et legyen. O az indokolja, hogy ezek adj´ ak meg az egyes f´ak ´eletter´et. Az adott ter¨ ulet legjobb kihaszn´ al´ as´ at pedig ´epp az optim´alis k¨orpakol´asi megold´as tudja biztos´ıtani. A pakol´ asi feladatok mellett a lefed´esi probl´em´ak is ide kapcsol´odnak. Ezek bizonyos ´ertelemben du´ alisai a pakol´asi feladatoknak. El˝obbi eset´en az a c´elkit˝ uz´es, hogy adott korl´ atos tartom´ anyt (esetleg ´atlapol´assal) teljes m´ert´ekben lefedj¨ unk minim´ alis darabsz´ am´ u egybev´ ag´o adott alakzattal. Ebben az ´ertelemben egy adott ter¨ ulet, p´eld´ aul egy orsz´ ag minim´alis sz´am´ u telekommunik´aci´os ad´otoronnyal val´o lefed´ese (felt´etelezve, hogy adott megk¨ovetelt t´erer˝o eset´en az ad´otorony hat´ok¨ore k¨ or alak´ u), k¨ or¨ okkel val´ o lefed´esi feladatra vezet. M´asr´eszt interferencia ´es egy´eb technikai jelens´egek miatt az elhelyezend˝o objektumok egym´ast´ ol egy minim´alis t´avols´ agot kell hogy tartsanak. Ez viszont ism´et a k¨orpakol´asi feladatot jelenti. Kicsit t´ avolabbr´ ol, de ide k¨ot˝odik a Latin hiperkocka tervez´es [11], amely adott t´err´esz koordin´ at´ ank´ent k¨ ul¨ onb¨oz˝o koordin´at´aj´ u, min´el t´avolabbi pontok kijel¨ol´es´ere t¨ orekszik. Ez sz´ amos alkalmaz´assal rendelkezik, a k´odtervez´est˝ ol a m´er´esi mintav´etelez´es ilyen szempontb´ol optim´alis meghat´aroz´as´aig. Tov´ abbi kutat´ asokat kell ezt k¨ovet˝oen v´egezni a matematikai ´ertelemben vett optimalit´ as igazol´ as´ ara, ´es az optim´alis r´acspakol´asok numerikus meghat´aroz´as´ara.

Hivatkoz´ asok [1] J. Kallrath, S. Rebennack, and P. Pardalos: Column Enumeration based Decomposition Techniques for a Class of Non-Convex MINLP Problems. J. of Global Optimization 43 (2009), 277–297 [2] J. Kallrath, S. Rebennack, and P. Pardalos: Cutting Circles and Polygons from AreaMinimizing Rectangles. J. of Global Optimization 43 (2009), 299–328 ´ t: An Interval Method to Validate Optimal Solutions of the Packing [3] M. CS. Marko ” Circles in a Unit Square” Problems, Central European Journal of Operational Research 8 (2000) 63–78 ´ t and T. Csendes: A new verified optimization technique for the ”packing [4] M. CS. Marko circles in a unit square” problems. SIAM J. on Optimization 16 (2005), 193–219 ´ t and T. Csendes: A reliable area reduction technique for solving circle [5] M. CS. Marko packing problems. Computing 77 (2006), 147–162

Alkalmazott Matematikai Lapok (2014)

´ KOZMA ATTILA CSENDES TIBOR ES

108

[6] E. Specht: Circles In ReCtangle (crc.c) algoritmus. ´ : Some New Structures for the Equal Circles Packing in a Square” Problem. [7] P. G. Szabo ” Central European Journal of Operations Research 8 (2000), 79–91 ´ : Optimal substructures in optimal and approximate circle packings. Beitr¨ [8] P. G. Szabo age zur Algebra und Geometrie 46 (2005), 103–118 ´ , M. CS. Marko ´ t, T. Csendes, E. Specht, L. G. Casado, and I. Garc´ıa: [9] P. G. Szabo New Approaches to Circle Packing in a Square – With Program Codes. Springer, Berlin, 2007 [10] Packomania vend´ egoldal: http://www.packomania.com [11] E. R. Van Dam, B. Husslage, D. Den Hertog, and Hand Melissen: Maximin Latin Hypercube Designs in Two Dimensions. Operations Research 55 (2007), 158–169

(Be´ erkezett: 2014. j´ unius 5.)

CSENDES TIBOR SZTE Sz´ am´ıt´ og´ epes Optimaliz´ al´ as Tansz´ ek ´ ad t´ 6720 Szeged, Arp´ er 2. [email protected] KOZMA ATTILA StreamNovation Kft. 1083 Budapest, Pr´ ater utca 50/a. [email protected]

OPTIMAL PACKING OF BUCKETS ON EUR-PALETTE Tibor Csendes and Attila Kozma A Belgian firm selling printing color asked us to help their delivery services with providing optimal number of buckets or barrels that can be positioned on a standard size eur-palette (80 × 120 cm). The reason why they were interested was that the earlier ad hoc packing resulted in a not exact fit, and during the loading of the lorries the lids of the bins containing the printing colors opened and the material was wasted causing substantial losses both expressed in money and time of the delivery. We used the Pulsating Disk Shaking algorithm of Eckard Specht, and here we report the best approximative solutions obtained with some discussion on the quality of these.

Alkalmazott Matematikai Lapok (2014)