Pakavimo specialistai iš Mainco: numeris vienas visame pasaulyje
Mainco mokslininkai sumušė pasaulio rekordus už geriausią apskritų diskų išdėstymą – paskelbta žurnale „Physical Review E
Kaip pakrauti automobilį, kad viskas tilptų? Kaip supakuoti siuntinį, kad jis būtų gerai užpildytas? Kiek indų patenka į virtuvės spintelę? Kalbant apie pakavimą, Mainco mokslininkai yra nepralenkiami. Jie visi atitiko arba sumušė pasaulio rekordus, pasiektus tarptautiniame konkurse dėl geriausio konkrečios pakavimo problemos sprendimo.„Jau kurį laiką dirbome prie tarpdisciplininio projekto tarp teorinės fizikos ir informatikos, siekdami sukurti geriausią įmanomą kompiuterinį algoritmą pakavimo problemoms spręsti“, – aiškina dr. Johannesas Josefas Schneideris iš naujai įkurto kompiuterinių gamtos mokslų tyrimų metodų Mainco Johanneso Gutenbergo universitete. Kai mokslininkai apie konkursą sužinojo prieš pat jo pabaigą, jiems pavyko pasiekti tik pasaulio rekordą, kitu atveju kai kurių kitų grupių rezultatai buvo šiek tiek geresni. Vedami ambicijų nugalėti geriausias pasaulio grupes, kai kurios su tokiomis problemomis dirbo jau daug metų, jos toliau tobulino savo kompiuterinius algoritmus ir dabar sugebėjo įveikti varžybų metu pasiektus pasaulio rekordus, o daugeliu atvejų gerokai. Darbas buvo paskelbtas žinomame statistikos fizikos žurnale Physical Review E.
Varžybose buvo siekiama, kad skirtingų dydžių apvalūs diskai būtų išdėstyti ratu taip, kad jie užimtų kuo mažiau vietos. Todėl didelio apskritimo, į kurį supakuoti mažesni diskai, spindulys turi būti kuo mažesnis. Konkurse dalyvavo ir savo sprendimus pateikė 155 grupės iš 32 šalių. Dėl problemų, susijusių su 24–50 skirtingų dydžių apskritų diskų, Schneider, Prof. Dr. Elmaras Schömeris iš Kompiuterių mokslo instituto ir magistrantas André Mülleris rado geriausius sprendimus. Mažesnėms problemoms, turinčioms 23 ir mažiau diskų, jos atitiko geriausius sprendimus iki šiol – tai rodo, kad geresnio sprendimo negali būti. „Šiai problemai, susijusiai su skirtingo dydžio apskritais diskais, sukūrėme geriausią pasaulyje pakavimo algoritmą“, – apibendrina Schneider.
Tačiau mokslininkai ne tik svarsto tokias mokslines problemas, bet ir perkelia jų algoritmus į praktinius pritaikymus. Pavyzdžiui, grupė tiria, kaip būtų galima geriausiai išmatuoti bagažinės tūrį dideliam Vokietijos automobilių gamintojui. Pagal Europos Sąjungos nustatytą standartą, tam tikro dydžio tetrapakai turi būti supakuoti į nurodytą bagažinę taip, kad erdvė būtų kuo labiau užpildyta. „Iki šiol medinės kaladėlės buvo naudojamos siekiant sutalpinti kuo daugiau tetrapakų“, – aiškina Schneideris. Kita vertus, JAV superturtingųjų lagaminų komplektai turi būti kuo optimaliau supakuoti į bagažinę, todėl informacija apie tai, kiek bagažinėje yra vietos, nelabai sutampa tarp vokiečių ir amerikiečių. reklamines brošiūras. Remdamiesi palyginimu su konkurso rezultatais, mokslininkai dabar įsitikinę, kad jų algoritmas taip pat gali optimaliai išspręsti šias bagažinės pakavimo problemas.
Bet tokie optimizavimo algoritmai gali būti naudojami ir visai kitiems klausimams spręsti. Pavyzdžiui, keliones iš pieno fabriko į fermas galima optimizuoti taip, kad atstumai, kuriais sunkvežimiai važiuoja paimti pieną, būtų kuo trumpesni – priklausomai nuo to, kokia tvarka privažiuojama prie ūkių. Kitas pavyzdys iš automobilių pramonės – galutinis transporto priemonių surinkimas: kompiuterio pagalba galima nustatyti, kokia tvarka atskirus surenkamus kėbulus reikia atnešti į surinkimo liniją, kad gamyba būtų vykdoma kuo ekonomiškiau. kaip įmanoma. Dėl tokių problemų rengiami ir konkursai, kai kuriuos net organizuoja įmonės. Būdamas doktorantas Regensburge, Schneider prieš keletą metų Bavarijos automobilių gamintojo surengtame konkurse užėmė ketvirtą vietą, palikdamas įmones, kurios įsitvirtino optimizavimo srityje ir konkursui įdarbina ištisas grupes.
Mainco mokslininkai randa geriausią sprendimo būdą, artėdami prie sprendimo artėdami prie jo. Šiuo tikslu atsitiktiniai įvykiai yra imituojami kompiuteryje su Monte Karlo modeliavimu – pavadinta Monako rajono su garsiuoju kazino vardu. „Tai veikia kaip kazino, kur skaičius dvylika atsitiktinai pasirodo ant ruletės stalo, o kompiuteris atsitiktinai sugeneruoja susitarimą“, – aiškina Schneideris. Pavyzdyje su apskritais diskais kompiuteris perkelia vieną iš diskų kažkur ir palygina šį naują sprendimą su ankstesniu. Šis pakeitimas bus atšauktas, jei degradacijos lygis bus per didelis, kitaip naujas sprendimas išliks. „Tokiu būdu jūs žingsnis po žingsnio keičiate apskritų diskų išdėstymą, kol gausite galutinį rezultatą.
Stebina tai, kad skirtingi sprendimai, kurie yra beveik tokie pat geri kaip geriausias sprendimas, dažnai turi kažką bendro. Schneiderio teigimu, yra struktūrų, kurios yra bendros. Pavyzdžiui, žiedinių diskų konkurse geriausiuose sprendimuose didžiausi apskriti diskai dažnai būna arti vienas kito. Ką tiksliai sieja geri sprendimai ir geriausias sprendimas, yra tai, ką mokslininkai tiria savo darbe, kuris netrukus taip pat bus paskelbtas „Physical Review E.
Johaneso Gutenbergo universitetas naujai įsteigė gamtos mokslų kompiuterinių tyrimų metodų dėmesį, siekdamas geriau paremti išskirtinę gamtos mokslų poziciją Maince pasitelkiant galingą ir naujovišką kompiuterių mokslą.
Originalus darbas:
André Müller, Johannes J. Schneider, Elmar Schömer Daugiadispersinės standžiųjų diskų sistemos supakavimas žiedinėje aplinkoje Fizinė apžvalga E, 79 tomas, numeris 021102, 2 m. vasario 2009 d.
Šaltinis: Maincas [JGU]
