[Algemeen] 3D Bin Packing algorithme (inpakken in dozen)

[Roel Broersma]

Met het volgende zit ik al een tijdje: 3D Bin Packing.

Ik heb een onbeperkt aantal (lege) dozen van verschillende afmetingen, ik stel dat mijn dozen allemaal rechthoekig zijn en dus 3 maten hebben (HxBxD). Stel dat ik bijv. 3 type dozen heb: Small, Medium en Large.

Vervolgens heb ik een X aantal voorwerpen, tevens zijn deze allemaal rechthoekig en hebben dus ook 3 maten (HxBxD).


Nu moet een algoritme voor mij uitrekenen op welke manier ik de MINSTE dozen nodig heb.

Ik heb overal op internet gezocht, google, etc. Ook verschillende boeken en PDF doorgelezen. Dit is een soort infinite, een onoplosbaar probleem. Je kan het namelijk niet berekenen maar slechts benaderen. Nu ben ik toch al een eindje;

Een paar gedachtes:
1) Ik heb bereken alle mogelijke opties, geef al deze opties een soort benchmark cijfer en kies vervolgens degene met het beste cijfer.
2) Ik ga alleen maar van rechthoekige dozen EN voorwerpen uit, dus heb ik hooguit te maken met 3 maten.
3) Een voorwerp kan ik ook kantelen. Wanneer ik een voorwep kan kantelen/roteren zal ik nooit de doos hoeven kantelen, dit is dus een vast gegeven.
4) De maten van de dozen zijn bekend, de maten van de voorwerpen zijn ook bekend. Hiermee is dus tevens het volume bekend van elk bekend. Met het volume alleen kan ik niet rekenen (een lange stok heeft weinig volume maar past niet in een kleine doos). Wel is het zo dat het totaal volume van al mijn (lege) dozen MINSTENS zo groot moet zijn als het totaal volume van al mijn voorwerpen.
5) Wanneer je een onbeperkt aantal dozen hebt (bijv. 3 verschillende type), dan zul je altijd de GROOTSTE (lege) dozen gebruiken, en alleen de laatste doos kan kleiner zijn. Vervolgens kan kijken of ik de andere dozen kan verkleinen. Voorbeeld: Ik heb 70 voorwerpen (alle even groot), dan pak ik in eerste instantie de grootste doos, stop er daar 20 in,. etc..etc.. Vervolgens heb ik er nog 10 over en stop deze in een kleinere doos. Tevens kan ik dan nog kijken of ik i.p.v. de grootste doos (waar ik er dan dus 3 van heb, met elk 20 stuks erin) een kleinere had kunnen gebruiken. (Dit kan ik natuurlijk ook al gelijk bekijken).

Ik heb een me laatst gebogen over een paar For loops die in elkaar zijn gestoken.

Hier heb ik een dergelijk algoritme gevonden: http://www.diku.dk/~pisinger/3dbpp.c, het kan alleen geen voorwerpen kantelen en heeft nog een aantal limitaties.

Mijn doel is: Gebruik zo min mogelijk dozen.

[4VAlien]

In principe is dit een uitbreiding van het 'bagpack' probleem naar de derde dimensie. Dit is niet zozeer een oneindig probleem als wel een non deterministisch probleem, wat wel betekent dat je al vrij snel ontzettende veel mogelijkheden krijgt.


Je wil bijvoorbeeld het algoritme http://www.edm2.com/0601/backpack.html per doos gebruiken. Als je dan stelt Value = Volume^2 dan pak je eerst de grootste objecten in, en dan steeds kleinere wat dus gunstig zou moeten zijn bij de laatste doos.

Probleem is dat dit probleem in principe voor 1 ruimte geldt, en dus niet voor meerdere dozen maar ik zie niet hoe je het algoritme dan aan moet passen.

[ Voor 102% gewijzigd door 4VAlien op 19-04-2005 16:49 ]

[.oisyn]

Roel Broersma schreef op dinsdag 19 april 2005 @ 16:39:
Hier heb ik een dergelijk algoritme gevonden: http://www.diku.dk/~pisinger/3dbpp.c, het kan alleen geen voorwerpen kantelen en heeft nog een aantal limitaties.

Mijn doel is: Gebruik zo min mogelijk dozen.

Ok, en wat wil je nou precies met je topic?

[Soultaker]

Roel Broersma schreef op dinsdag 19 april 2005 @ 16:39:
5) Wanneer je een onbeperkt aantal dozen hebt (bijv. 3 verschillende type), dan zul je altijd de GROOTSTE (lege) dozen gebruiken, en alleen de laatste doos kan kleiner zijn. Vervolgens kan kijken of ik de andere dozen kan verkleinen.

Volgens mij klopt dit al niet, tenzij de dozen gelijkvormig zijn (ie. de verhouding dus lengte, hoogte en diepte is hetzelfde). Het kan dus zijn dat je in een medium-doos meer kwijt kunt dan in een large-doos, ook al is de inhoud van de large doos groter. (Voorbeeld: in een 2x2x4 doos kun je wel twee 2x2x2 objecten kwijt, terwijl dat in de grotere 3x3x3 doos niet kan.)

Als de dozen gelijkvorming zijn hoef je die kleinere dozen inderdaad nooit te gebruiken, als je alleen het totale aantal gebruikte dozen minimaliseert. Maar dan hoef je ook niet moeilijk te doen met als laatste doos een kleinere kiezen of naderhand gebruikte dozen vervangen door kleinere.

[Soultaker]

4VAlien schreef op dinsdag 19 april 2005 @ 16:43:
In principe is dit een uitbreiding van het 'bagpack' probleem naar de derde dimensie. Dit is niet zozeer een oneindig probleem als wel een non deterministisch probleem, wat wel betekent dat je al vrij snel ontzettende veel mogelijkheden krijgt.

Dat 'bagpacking' wat je noemt wordt meestal het 'knapsack problem' (NIST, MathWorld) genoemd en het is fundamenteel anders (en simpeler) dan bin packing. Het kan dan ook opgelost worden met dynamisch programmeren. Er zijn verder legio verschillen tussen bin packing en het knapsack probleem (bij bin packing heb je in het basisgeval geen keuze uit de producten die je meeneemt bijvoorbeeld, noch hebben die producten een waarde).

Je wil bijvoorbeeld het [knapsack] algoritme per doos gebruiken. Als je dan stelt Value = Volume^2 dan pak je eerst de grootste objecten in, en dan steeds kleinere wat dus gunstig zou moeten zijn bij de laatste doos.

Dat is dus een fundamenteel verschil en daarom is het algoritme niet van toepassing op deze situatie. Bovendien is het niet optimaal om elke doos afzonderlijk zo vol mogelijk in te pakken; je moet het totale aantal dozen optimaliseren (en dat is niet hetzelfde!)

[ Voor 9% gewijzigd door Soultaker op 19-04-2005 17:14 ]

[Zoijar]

Soultaker schreef op dinsdag 19 april 2005 @ 17:13:
Dat 'bagpacking' wat je noemt wordt meestal het 'knapsack problem' (NIST, MathWorld) genoemd en het is fundamenteel anders (en simpeler) dan bin packing. Het kan dan ook opgelost worden met dynamisch programmeren.

Knapsack is een NPC probleem hoor. En dat greedy algoritme met steeds de grootste is niet optimaal; maar in zo'n speciaal geval van oplopende waardes, dan is knapsack niet npc. Daar berust ook de knapsack encryptie op (die overigens kraakbaar is)

[Tomatoman]

4VAlien schreef op dinsdag 19 april 2005 @ 16:43:
[verhaal]

Soultaker schreef op dinsdag 19 april 2005 @ 17:04:
[verhaal]

Soultaker schreef op dinsdag 19 april 2005 @ 17:13:
[verhaal]

Zoijar schreef op dinsdag 19 april 2005 @ 19:29:
[verhaal]

Zoals .oisyn al aangaf heeft Roel Broersma helemaal niet aangegeven wat zijn vraag of probleem is. Het lijkt me dan ook nutteloos om lukraak te posten.

[Roel Broersma]

.oisyn schreef op dinsdag 19 april 2005 @ 16:49:
[...]


Ok, en wat wil je nou precies met je topic?

Iemand die een dergelijke oplossing heeft of een algorithme, danwel hulp/advies m.b.t. het aanpassen van een bestaand algorithme.

[Soultaker]

Zoijar schreef op dinsdag 19 april 2005 @ 19:29:
Knapsack is een NPC probleem hoor. En dat greedy algoritme met steeds de grootste is niet optimaal; maar in zo'n speciaal geval van oplopende waardes, dan is knapsack niet npc. Daar berust ook de knapsack encryptie op (die overigens kraakbaar is)

Het hangt een beetje van de variant af. Als je N items hebt, gewicht per item W, en waarde per item V en je wil een functie f(n,w) maken die de maximale waarde geeft die te maken is met de eerste n items en een maximumgewicht w, dan is die te implementeren met de recurrente betrekking:
• f(0,w) = 0
• f(n,w) = max( f(n-1, w), f(n-1, w - W_n) + V_n )
(Lees: de maximale waarde voor de eerste n items met een knapzak met een limiet w is ofwel de waarde voor de eerste n-1 items in dezelfde knapzak (en dan neem je item n dus niet mee) ofwel de waarde van item n plus de waarde voor de eerste n-1 items in een knapzak die het gewicht van item n lichter is (dan neem je n wel mee en is er dus minder ruimte voor de rest).

Dit algoritme (mits goed geïmplementeert: dynamisch of recursief met memoization) kost O(NX) tijd, waarbij die X het aantal verschillende mogelijke gewichten aanduid. Daar zit 'm ook de crux: dit werkt alleen als het gewicht is uit te drukken in een 'eindig' getal (zoals gehele getallen, maar ook breuken) en het werkt dus specifiek niet als de gewichten reëele getallen zijn (tenzij je genoegen neemt met fixed point precisie, dan werkt het weer wel).

Als het aantal verschillende gewichten beperkt is, is er dus wel een efficiënte oplossing voor handen.

tomatoman schreef op dinsdag 19 april 2005 @ 19:41:
Zoals .oisyn al aangaf heeft Roel Broersma helemaal niet aangegeven wat zijn vraag of probleem is. Het lijkt me dan ook nutteloos om lukraak te posten.

Klopt ja, maar mijn eerst reactie was wel degelijk een reactie op zijn topic start (waarin een aantal aannamen gedaan werden). De rest is inderdaad wat lukraak gepost.

[ Voor 27% gewijzigd door Soultaker op 19-04-2005 19:56 ]

[Roel Broersma]

Ik wil geen onmogelijke dingen oplossen, daarom leek het benaderen van het minimaal aantal dozen mij ook beter dan koste wat kost proberen uit te rekenen hoe ik de minste dozen nodig heb.

Hier een paar mogelijkheden: (met dank aan Andreas Gammel met wie ik Email contact heb gehad), dit is toch meer de kant die ik op wil. Als iemand een verbetering, voorstel, algorithme of idee heeft hoor ik het graag.


First Fit
Loop vanaf bin 1 tot bin N en kies de eerste ‘bin’ waarin je pakket past en plaats binnen deze bin het pakket op de eerste plek waar hij past. In jou geval krijg je zoiets als:

code:

for b = 0 to numberofbins
  for x = 0 to bins[b].sizeX step stepX
    for y = 0 to bins[b].sizeY step stepY
      for z = 0 to bins[b].sizeZ step stepZ
          if 'pakket p past in bin b op positie x,y,z'
          then 'pak hem in op deze plek'
      next
    next
  next
next

makkelijk te implementeren maar vrij slecht resultaat.
Het ‘resultaat’ kun je meten als de hoeveelheid vrije ruimte die in een bin overblijft.


RandomFit
Gooi pakket in random bin. Blijkt beter te werken dan FirstFit.


BestFit
Dit is een verbetering op FirstFit, waarbij je niet de eerste, maar de beste bin kiest. De beste is hier: de minst volle bin.


DecreasingFit
Gooi product in een bin waarvan het vorige product zwaarder was. M.a.w., zorg dat de gewichten afnemen. Deze laatste is nog het beste.

[ Voor 3% gewijzigd door Roel Broersma op 19-04-2005 19:59 ]

[joepP]

Misschien moet je eerst eens op 2D bin-packing zoeken? Het lijkt me dat daar toch wel eea over gepubliceerd is. Anders kan je ook overwegen de 2D knapzak te bestuderen, dit is dan wel een ander probleem maar ik denk dat het bestuderen van de generalisatie naar meerdere dimensies wel tot inzichten zal leiden.

[Tomatoman]

In je topic Functie voor berekenen verzendkosten met gewicht &afmetingen van een jaar geleden is ook al een discussie over dit probleem geweest (alleen heb je je toen zelf niet in de discussie gemengd). Wat heb je gedaan met de suggesties die toen zijn gegeven?

[Roel Broersma]

tomatoman schreef op dinsdag 19 april 2005 @ 20:05:
In je topic Functie voor berekenen verzendkosten met gewicht &afmetingen van een jaar geleden is ook al een discussie over dit probleem geweest (alleen heb je je toen zelf niet in de discussie gemengd). Wat heb je gedaan met de suggesties die toen zijn gegeven?

Tsja, er is weer een jaar voorbij en ik heb het toch nog is opgepakt.

Zoals je ziet gaat dit topic al een stuk dieper dan het vorige waar we het meer over volume hadden etc. Gelukkig maar..
Ik hoop dat we dit keer echt de kant van algorithme's op gaan en er wat uit kunnen halen of aanscherpen.

[ Voor 13% gewijzigd door Roel Broersma op 19-04-2005 20:58 ]

[MisterData]

offtopic:
Het zou zo een goede opdracht voor een programmeerwedstrijd kunnen zijn: schrijf een programma om zo efficient mogelijk dozen te vullen...

[Anoniem: 118860]

Wat je kan proberen als oplossing om het probleem te benaderen is local search (net gehad in een vak, nu meteen pluggen ).

Het idee is dat je door de oplossingenruimte gaat lopen, en probeert een oplossing van zo laag mogelijke kost (of zo hoog mogelijke waarde) te vinden.

Affijn, ik weet niet of dat je iets lijkt, dus ga ik niet verder hele verhalen inbrallen als je er toch niks mee gaat doen.

Ook al is je probleem NP-volledig, als je instanties niet zo groot zijn kun je natuurlijk ook gewoon alle oplossingen checken en de goedkoopste eruit pikken.

Is het trouwens voor een praktisch probleem of een theoretische oefening?

[Roel Broersma]

OneOfBorg, het is een praktisch probleem. Er moeten voorwerpen (artikelen) worden verpakt en naar klanten worden verstuurd in dozen. Het moet in zo min mogelijk dozen, want 1 doos = 1 colli. En bij vervoers / koeriers bedrijven betaal je meestal per colli.

Heb je een voorbeeldje of wat meer info ?

Het praktische verhaaltje erachter:
Per keer moet ik minimaal 1 en maximaal 30 artikelen versturen naar een klant. Het zou dan handig zijn als ik van te voren wist (ook om de verzendkosten te berekenen) in hoeveel colli (aantal dozen) dit ging. Tevens kan ik hierop (op basis van historic averages,.etc.. en forecast) (lege)dozen inkopen bij de leverancier.

[Soultaker]

Anoniem: 118860 schreef op woensdag 20 april 2005 @ 00:28:
Wat je kan proberen als oplossing om het probleem te benaderen is local search (net gehad in een vak, nu meteen pluggen ).

Het idee is dat je door de oplossingenruimte gaat lopen, en probeert een oplossing van zo laag mogelijke kost (of zo hoog mogelijke waarde) te vinden.

Wat is die 'local search' dan? Hoe werkt dat? Dat je een oplossing met de laagste kosten zoekt is duidelijk; dat is een beetje de definitie van het probleem.

Lijkt jouw 'local search' op iets als hill climbing of best-first search (waar ik verder weinig goeds over te zeggen heb, maar dat terzijde)?

[ Voor 3% gewijzigd door Soultaker op 20-04-2005 01:05 ]

[Whiskeyjack]

voor wie het nog niet wist: dit is natuurlijk een wiskundig probleem. Het kan (denk ik) niet opgelost worden door te denken in fors en ifs.

Zoek eens op "linair programmeren" of op "simplex methode", misschien dat je er wat aan hebt. Als ik tijd heb puzzel ik er nog wel even aan .

[DaRealRenzel]

Ahum.

Als eerste stap zou ik m'n voorwerpen op grootte sorteren. Een van de maten moet je als beginpunt nemen. Neem daarvoor de grootste van de 3 maten, want die is maatgevend voor je doos. Qua datastructuur denk ik aan een lijst met drie indexes, elke index is dezelfde doos, maar met een andere beginmaat (1e index - hxbxd, 2e index is bxdxh, 3e index is dxbxh, dus elke maat is een keertje maatgevend) Als de voorwerpen op maat zijn gesorteerd, plaats je het grootste voorwerp in de kleinst mogelijke doos. Dan pas je daar het een na grootste voorwerp bij, en wel op elk van de 3 manieren. Als het past laat je het zitten. Als het niet past moet je een grotere doos hebben enz enz. tot je alles in dozen hebt zitten. Je hebt dan een eerste iteratie.
Dan stop je het grootste voowerp in een een maat grotere doos en doe hetzelfde. Uiteindelijk hou je dan ergens een iteratie over die het kleinst aantal dozen oplevert.

Vervolgens herhaal je dit alles waarbij een item in een van twee dozen gestopt kan worden, en daarna in een van drie etc etc.

Met de juiste backtracking hou je aldus een finale iteratie over waarbij alle pakketjes in het minst aantal dozen geplaatst kunnen worden.

Het is wel handig om dit eerst te ontwerpen met 1 formaat doos en 2 of 3 formaten items, qua algoritmeontwikkeling is dat eenvoudiger. Later een formaat doos erbij maken veranderd niet veel aan het zoekalgoritme.

[Soultaker]

Whiskeyjack schreef op woensdag 20 april 2005 @ 01:09:
Zoek eens op "linair programmeren" of op "simplex methode", misschien dat je er wat aan hebt. Als ik tijd heb puzzel ik er nog wel even aan .

Waarom? Hoe dacht jij het probleem te formuleren als een stelsel lineaire vergelijkingen?

Aan zomaar wat bestaande algoritmen roepen heeft de TS naar mijn mening niets. Het is altijd verstandig om een probleem als dit terug te voeren om bestaande problemen en algoritmen, maar dan is het wel een aardig om er een motivatie bij op na te houden.

[ Voor 30% gewijzigd door Soultaker op 20-04-2005 13:51 ]

[Anoniem: 118860]

Soultaker schreef op woensdag 20 april 2005 @ 00:55:
[...]

Wat is die 'local search' dan? Hoe werkt dat? Dat je een oplossing met de laagste kosten zoekt is duidelijk; dat is een beetje de definitie van het probleem.

Laten we deze open deur als ingetrapt beschouwen, hehe

Lijkt jouw 'local search' op iets als hill climbing of best-first search (waar ik verder weinig goeds over te zeggen heb, maar dat terzijde)?

Ik heb er niet echt in de praktijk mee gewerkt, dus ik kan niet uit ervaring zeggen of het al dan niet goed werkt. En ja, daar lijkt het (denk ik) op, maar best-first search is maar één van de mogelijk strategieën die je kunt gebruiken om door de oplossingenruimte te lopen.

Okee. Je definiëert een kostenfunctie op een oplossing. Uiteindelijke wil je het globale minimum van die kostenfunctie op alle oplossingen hebben.

Het basisidee is dat je met een oplossing S₀ begint - die kan bijvoorbeeld willekeurig gegenereerd zijn. Daarna ga je nieuwe oplossingen genereren die afwijken van de eerste oplossing. Dit gaat volgens een bepaalde mutatiefunctie (in dit voorbeeld zou de functie bijvoorbeeld kunnen zijn: verwissel twee objecten van doos). Je gaat daarna verder naar één van die gegenereerde oplossingen met een lagere kostenfunctie waarde (via first-improvement -- ik neem aan dat je deze bedoelde, Soultaker? -- of best-improvement of een andere selectiemethode), en daar begint het spelletje opnieuw. Dit gaat door totdat je in een minimum zit.

Het kan natuurlijk zijn dat het minimum waar je je op zo'n moment in bevindt een lokaal minimum is, en geen globaal minimum. Er zijn daarom nog een paar technieken om te voorkomen dat je vast komt te zitten in een lokaal minimum.

De makkelijkste daarvan is Random Restart: je voert niet één run uit, maar N, en neemt het minimum van alle runs als oplossing. Een andere is Simulated Annealing: daarbij hangt de kans dat een bepaalde oplossing wordt gekozen als volgende, af van hoeveel beter of slechter hij is dan de huidige (je gaat dus niet alleen naar lagere-kost oplossingen, maar eventueel ook naar hogere om uit lokale optima te ontsnappen).

Er valt nogaal veel te tweaken aan deze methode, zoals de: neighbourhood function (hoe genereer je buuroplossingen), pivoting rule (hoe kies je de volgende oplossing) en heuristieken om aan lokale optima te ontsnappen. Volgens mij verschilt het nogal van probleem tot probleem wat de beste technieken zijn om te gebruiken, en omdat ik -- zoals ik al zei -- er geen praktijkervaring mee heb kan ik je verder niet met de details helpen. Maar als je geïnteresseerd bent valt er op het Net vast wel genoeg over te vinden.

[ Voor 15% gewijzigd door Anoniem: 118860 op 20-04-2005 15:52 ]

[Whiskeyjack]

Roel Broersma schreef op dinsdag 19 april 2005 @ 16:39:
Met het volgende zit ik al een tijdje: 3D Bin Packing.

Ik heb een onbeperkt aantal (lege) dozen van verschillende afmetingen, ik stel dat mijn dozen allemaal rechthoekig zijn en dus 3 maten hebben (HxBxD). Stel dat ik bijv. 3 type dozen heb: Small, Medium en Large.

Vervolgens heb ik een X aantal voorwerpen, tevens zijn deze allemaal rechthoekig en hebben dus ook 3 maten (HxBxD).


Nu moet een algoritme voor mij uitrekenen op welke manier ik de MINSTE dozen nodig heb.

Uhm volgens mij heb je ofwel je probleem niet goed gedefinieerd ofwel dit probleem is triviaal (of ik mis iets).

Je gebruikt toch gewoon het minste aantal dozen als je de grootste doos kiest....

[Soultaker]

De vraag is dus: hoe kan 'ie de items inpakken zodat 'ie zo min mogelijk dozen nodig heeft. Dat je in principe altijd de grootste doos gebruikt is duidelijk.

[Tomatoman]

Ik denk dat je bent aangewezen op een eindige-elementenmethode. Daarbij verdeel je ieder voorwerp in een eindig aantal blokjes (elementen), bijvoorbeeld blokjes van 1 x 1 x 1 cm. Stel nu dat je een doos hebt met als afmetingen 6 x 4 x 7 cm. Dat geeft als coördinaat voor het buitenste hoekje van de doos (5, 3, 6). Nu wil je daar een blok in stoppen met als afmetingen 4 x 3 x 3. Als basis van het blok neem je het element (0, 0, 0). Zonder te draaien is het blok op de volgende manieren in de doos te stoppen:

---

(0, 0, 0)
(1, 0, 0)
(2, 0, 0)
(3, 0, 0) is niet mogelijk, want dan steekt het blok aan de X-kant uit de doos.
(0, 1, 0)
(1, 1, 0)
(2, 1, 0)

(0, 0, 1)
(1, 0, 1)
(2, 0, 1)
(0, 1, 1)
(1, 1, 1)
(2, 1, 1)

...

(0, 0, 3)
(1, 0, 3)
(2, 0, 3)
(0, 1, 3)
(1, 1, 3)
(2, 1, 3)

---

Zoals je ziet is het aantal mogelijkheden om het blok in de doos te plaatsen, namelijk 3 x 2 x 3 = 18 mogelijkheden, beperkt. Je bent er echter niet met deze mogelijkheden, je kunt het blok namelijk ook om zijn assen draaien, waardoor het bijvoorbeeld op zijn zijkant komt te staan. Elk van die draaibewegingen resulteert in ene bepaalde oriëntatie van het blok. Om het probleem binnen de perken te houden kan ieder voorwerp slechts in veelvouden van 90 graden worden gedraaid, schuin in de doos plaatsen is er niet bij. In totaal kan het voorwerp 24 oriëntaties hebben, waarbij elke afzonderlijke oriëntatie weer een aantal verschuivingsmogelijkheden binnen de doos oplevert. Aangezien een blok bepaalde symmetrieën heeft, zijn er echter een paar oriëntaties die precies hetzelfde resultaat opleveren. Zo kun je het blok op de kop leggen, maar voor de mogelijkheden om het in de doos te plaatsen maakt dat niet uit.

Samenvattend kan een voorwerp op maximaal 24 manieren georiënteerd in de doos worden geplaatst. Bij iedere oriëntatie kan het voorwerp op minstens 0 manieren worden verschoven (getransleerd) binnen de doos. Al met al is het voorwerp misschien wel op honderden manieren te plaatsen binnen de doos.

Nu kun je een truc toepassen. Geef alle 6 x 4 x 7 = 168 elementen binnen de doos een volgnummer:
(0, 0, 0) = 0
(1, 0, 0) = 1
(2, 0, 0) = 2
...
(5, 0, 0) = 5
(0, 1, 0) = 6
(1, 1, 0) = 7
...
(5, 3, 6) = 167

Nu heb je een nieuwe mogelijkheid om voor een voorwerp vast te leggen welke elementen hij in de doos vult. Geef een element dat gevuld wordt met een stukje voorwerp de binaire waarde 1 en een element dat niet gevuld wordt de waarde 0. Nu kun je met een reeks van 168 bits aangeven welke elementen bezet zijn in de doos. Voor het blok in de uitgangspositie levert dat het volgende vulpatroon op:

111100 111100 111100 000000 111100 111100 111100 000000 111100 111100 ... 000000 000000

Het aardige van dat bitpatroon is dat je het kunt vergelijken met patronen voor andere voorwerpen. Hebben twee voorwerpen nergens op dezelfde plek in het bitpatroon een 1 staan, dan passen ze op die manier samen in de doos zonder dat ze een bepaald element dubbel bezetten (wat natuurlijk niet kan). Met een logische AND-vergelijking kun je dit heel snel controleren:

IF Patroon1 AND Patroon2 = 0 THEN
; ze passen samen in de doos
ELSE
; ze zitten elkaar in de weg

Door op deze manier alle mogelijkheden te controleren, vind je vanzelf uit welke combinaties van voorwerpen mogelijk zijn (combineren doe je met OR). Uitbreiding met een derde voorwerp verloopt op dezelfde manier. Nu ga je op zoek naar de oplossing waarbij de doos zo vol mogelijk komt te zitten. Het is flink wat gepuzzel om dit in code om te zetten, maar het is best te doen. Ik spreek uit ervaring

[Roel Broersma]

Kijk tomatoman, daar heb ik inderdaad wat aan.

Ben blij dat de tegenwoordige computers lekker snel zijn voor al die xxxxxx aantal mogelijkheden
Ik heb hier nu een aantal mogelijkheden voorbij zien komen en denk dat die van jou wel een van de snelste is. En als hij te snel is dan nemen we gewoon mm i.p.v. cm als (blok)maat.

Mag ik ook nog vragen of je een kant-en-klare functie of meer/deels voorbeeld hebt ?
Ik zal inderdaad zowieso e.e.a. moeten verbouwen.

'k had eigenlijk gehoopt dat er iemand van een wiskunde opleiding of uit Delft had gezegt: "zo.,.zo,. met deze 14 for loops en if statements ben je er, vul voor X het aantal dozen in, Y een commagescheiden string van de maten,. etc.. "

Ik ben toch niet de eerste die gewoon rechthoekige artikelen in een aantal rechthoekige dozen wil verpakken ? Ik kan idd me zelf uitgebreid gaan buigen over de code e.d. maar dan kom ik vervolgens na een half jaar (of nog later) erachter dat ik altijd een bepaalde doos oversla of voor 30% minder effectief verpak (dus hogere verzendkosten reken, dus minder concurerend ben) omdat ik een if statement mis. Dan baal je... (En hoe leg je uit aan je klanten dat ze minder verzendkosten hadden betaald als jij even een efficienter (lees: andere If's) algoritme had gepakt ).
Ik bedoel dus in deze, _het is niet dat ik de code niet wil schrijven ook al ben ik lui :)_, maar het lijkt met niet handig het wiel weer opnieuw uit te vinden, zeker omdat ik al niet dagelijks (en pratisch, zoals je zelf zegt) met deze dingen bezig ben.

Aan de andere kant begrijp ik dus niet dat ik nergens op scripting forums (php, asp,. etc) of google of applicatie programmeer forums (C, Java, etc) dit soort dingen kan vinden. Van de een naar de andere programmeertaal ombouwen is nog niet zo'n probleem. Uiteindelijk zal het in ASP of PHP terechtkomen om in een internet shop (met backend voor de inpakmedewerkers) te functioneren.

Meer praktische voorbeelden/code of links naar code zijn altijd welkom!

[ Voor 11% gewijzigd door Roel Broersma op 21-04-2005 13:15 ]

[Zoijar]

Roel Broersma schreef op donderdag 21 april 2005 @ 12:59:
'k had eigenlijk gehoopt dat er iemand van een wiskunde opleiding of uit Delft had gezegt: "zo.,.zo,. met deze 14 for loops en if statements ben je er, vul voor X het aantal dozen in, Y een commagescheiden string van de maten,. etc.. "

Dat komt omdat je probleem complex is. Sommige heel simpel te beschrijven problemen, blijken zo complex te zijn dat er al jaren onderzoek naar wordt gedaan.

Ik ben toch niet de eerste die gewoon rechthoekige artikelen in een aantal rechthoekige dozen wil verpakken ?

Zeker niet; vandaar ook dat er het vakgebied operations research is uitgevonden na/tijdens WW2. Denk je maar in dat deze dozen ook nog op schepen moeten, die een bepaalde zink kans heben mbt U-boten

[joepP]

Roel Broersma schreef op donderdag 21 april 2005 @ 12:59:
Ik ben toch niet de eerste die gewoon rechthoekige artikelen in een aantal rechthoekige dozen wil verpakken ?

Dat ben je ook niet, er zijn zelfs logistieke pakketjes die dit soort dingen oplossen. En binnen de operations research is er vast ook genoeg te vinden, zoek eens op "three dimensional bin-packing" op google. Er zijn echt wel wat artikelen over geschreven. Daar wordt wel meestal uitgegaan van een enkele maat bin, ipv jouw drie bins.

Het knelpunt is dat jouw probleem "nogal" complex is. Er zijn geen methodes die altijd het optimale aantal dozen berekenen binnen fatsoenlijke rekentijd, je bent dus aangewezen op heuristieken en local-search-achtige methoden als je het probleem algemeen wilt oplossen. In jouw geval met 30 dozen denk ik dat er nog wel een exact algoritme uit te persen valt, maar dat zal niet eenvoudig zijn.

Probeer eerst eens een deelprobleem: gegeven één bin, en X dozen, bepaal of er een mogelijkheid is om de dozen in de bin te stoppen, en lever deze op. Hiervoor kan je een eindige elementen-methode gebruiken zoals hierboven uitgelegd, of misschien een branch-and-bound aanpak.

Als je dat probleem goed (en snel!) kan oplossen, dan kan je een stap verder maken, door de first-fix heuristiek te gebruiken. Sorteer de dozen wel op aflopende grootte, anders zal het resultaat niet best zijn. Ja kan ook de dozen in random volgorde aanbieden en dan proberen de dozen uit de meest-lege bin over de andere bins te verdelen.

[.oisyn]

tomatoman schreef op donderdag 21 april 2005 @ 01:58:
Zo kun je het blok op de kop leggen, maar voor de mogelijkheden om het in de doos te plaatsen maakt dat niet uit.

Het lijkt me dan ook nutteloos om uit te gaan van 24 orientaties, ipv het aantal permutaties van breedte, lengte en diepte, oftewel 6

Overigens is je voorgestelde algoritme gewoon een brute-force aanpak, niet een heel efficiente dus.

[Soultaker]

Valt nog wel mee; voor het combineren van die bitstrings zou je nog wel wat slimmigheidjes kunnen bedenken.

[.oisyn]

Dat is juist de triviaalste operatie in het hele algoritme, die optimizen lijkt me niet heel erg nuttig . Je wil eerder bepaalde combinaties op voorhand rejecten. Als een object met afmetingen (3, 4, 5) zich op punt (0, 0, 0) bevindt, dan heeft het niet echt nut om voor een ander object de ruimte tussen (0, 0, 0) en (2, 3, 4) te gaan proberen (wat al 3*4*5 = 60 combinaties zijn).

Ik zou zelf denk ik een kd-tree gebruiken om de ruimte op te delen in solid en empty deelruimtes, en als je dan een object wilt toevoegen haal je 'm gewoon door de boom heen. In feite hoef je alleen die combinaties te proberen die je lege deelruimtes beslaan, dus als je bij het wijzigen van de boom een lijstje bijhoudt met lege cellen in die boom kun je al een hoop combinaties wegstrepen.

[Soultaker]

Nou, als ik het goed begrijp krijg je voor elk product een set bitstrings die corresponderen met de mogelijke plaatsingen van het product. Voor elk product een plaatsing kiezen, zo, dat van alle gekozen bitstrings maximale aantal 1tjes op dezelfde positie minimaal is (want dat is het doel) lijkt me allesbehalve triviaal. Daar wil je dus wel iets handigs mee doen, anders schiet het niet op. (1000x1000x1000....1000 mogelijkheden proberen werkt niet).

[Whiskeyjack]

Soultaker schreef op donderdag 21 april 2005 @ 16:56:
Nou, als ik het goed begrijp krijg je voor elk product een set bitstrings die corresponderen met de mogelijke plaatsingen van het product. Voor elk product een plaatsing kiezen, zo, dat van alle gekozen bitstrings maximale aantal 1tjes op dezelfde positie minimaal is (want dat is het doel) lijkt me allesbehalve triviaal. Daar wil je dus wel iets handigs mee doen, anders schiet het niet op. (1000x1000x1000....1000 mogelijkheden proberen werkt niet).

ok jongens, ik begrijp het probleem. had iemand me kunnen vertellen dat het om voorwerpen van VERSCHILLENDE afmetingen gaat?

Das inderdaad complex. Overigens wil ik opmerken dat het gebruik van het woord "eindige elementen methode" hier niet echt op z'n plaats is.

[Roel Broersma]

Nouja, we kunnen het is proberen, die bitstring methode van Tomatoman.

Heeft Tomatoman al een stukje code ? Dan kan ik er wat mee gaan klooien en bouwen en kan ik gelijk zien of het wel/niet snel genoeg werkt.

Zoals ik al zei,, computers zijn snel genoeg,. dus minder efficiente code,. tsja.. het hoort niet. Maar je moet ergens beginnen.

...code... ?


PS. Voor de post hierboven, nog een keer:
Het gaat om het verpakken van verschillende artikelen (alle rechthoekig, met alle verschillende maten). Het assortiment aan artikelen is 1000 - 1500 stuks. Als ik een klant een pakketje (wat dus uit meerdere colli kan bestaan) stuur dan zitten er MAX. 30 artikelen in. Om mijn pakketje te versturen heb ik meerdere lege dozen tot mijn beschikking. Laten we het voor het gemak houden op een SMALL, MEDIUM en LARGE doos. En nee, een SMALL doos hoeft niet perse in een LARGE doos te passen (misschien is een SMALL doos wel een verpakking voor een lange TL-buis terwijl een LARGE doos een doos is om bijv. een computerkast/behuizing in te doen.

[Coca-Cola]

Ik zat meteen te denken aan een algoritme wat voor het inpakken zorgt en een genetic algorithm om vervolgens een bijna-optimale oplossing te vinden (ik neem aan dat je met bijna optimale oplossingen ook wel blij bent toch?) Toen ik daar op googlede kwam ik op het volgende:

Nou heb ik dus geen toegang tot de ACM digital library, maar mocht iemand dat hebben dan is:
linkje

[Roel Broersma]

Coca-Cola schreef op vrijdag 22 april 2005 @ 14:19:
Nou heb ik dus geen toegang tot de ACM digital library, maar mocht iemand dat hebben dan is:
linkje

Heb net even een gratis account'je genomen en kom nog nergens bij, zelfs niet bij 1 dimensional bin packing algorithm in PDF. Ik zie wel alles staan... En een accountje kost weer >100$.
Iemand met toegang die uberhaupt kan kijken of het iets is ?

[Soultaker]

Ik denk dat je je niet blind moet staren op dat ene artikel; er is zo veel over geschreven dat het me sterk lijkt dat alleen daar de informatie staat die je zoekt. Waarschijnlijk wordt er alleen een specialistische aanpak beschreven en wordt er verder naar allerlei andere literatuur verwezen.

[MrBucket]

Coca-Cola schreef op vrijdag 22 april 2005 @ 14:19:
Ik zat meteen te denken aan een algoritme wat voor het inpakken zorgt en een genetic algorithm om vervolgens een bijna-optimale oplossing te vinden (ik neem aan dat je met bijna optimale oplossingen ook wel blij bent toch?) Toen ik daar op googlede kwam ik op het volgende:

Nou heb ik dus geen toegang tot de ACM digital library, maar mocht iemand dat hebben dan is:
linkje

De paper die jij wil staat niet online bij acm (er is nl. geen "Full text" entry, met pdf-symbooltje). Dus zelfs met een account kan je niets.

Zoals Soultaker al zei: staar je niet blind op dit ene artikel, er moet echt veel meer over te vinden zijn.

[Anoniem: 94210]

Ook via de UvA kom ik niet aan t artikel, terwijl die tegenwoordig wel wat bronnen hebben. Een zoektocht met de woorden 'bin packing dimensional' leverde toch wel wat op (zonder enig zicht beschikbaarheid dan wel relevantie, maar het zijn meestal wel goede tijdschriften):

ARTICLES - The Three-Dimensional Bin Packing Problem
Martello, Silvano; Pisinger, David; Vigo, Daniele / In: Operations research; vol. 48 (2000), afl. 2, pag. 256-267 (12) / 2000

Guided Local Search for the Three-Dimensional Bin-Packing Problem
Faroe, Oluf; Pisinger, David; Zachariasen, Martin / In: INFORMS journal on computing; vol. 15 (2003), afl. 3, pag. 267-283 (17) / 2003

Heuristic algorithms for the three-dimensional bin packing problem
Lodi, Andrea; Martello, Silvano; Vigo, Daniele / In: European journal of operational research; vol. 141 (2002), afl. 2 (01 SEP), pag. 410-420 / 2002

TSpack : A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems
Lodi, Andrea; Martello, Silvano; Vigo, Daniele / In: Annals of operations research; vol. 131 (2004), afl. 1, pag. 203-213 (11) / 2004

On d-threshold graphs and d-dimensional bin packing
Caprara, Alberto; Lodi, Andrea; Rizzi, Romeo / In: Networks; vol. 44 (2004), afl. 4, pag. 266-280 (15) / 2004

The Three-Dimensional Bin Packing Problem and Its Practical Algorithm
Jin, Zhihong; Ito, Takahiro; Ohno, Katsuhisa / In: JSME international journal, Series C, Mechanical systems, machine elements and manufacturing; vol. 46 (2003), afl. 1, pag. 60-66 (7) / 2003

A greedy search for the three-dimensional bin packing problem: the packing static stability case
Castro Silva, J.L. de; Soma, N.Y.; Maculan, N. / In: International transactions in operational research; vol. 10 (2003), afl. 2, pag. 141-154 (14) / 2003

De meeste van deze tijdschriften zijn wel beschikbaar voor de nederlandse universiteiten...

Ik heb echter het vermoeden dat je je wel moeilijk maakt met je drie typen dozen. Maar ik heb nu even geen zin deze artikelen te bekijken.

Misschien kijk ik als ik thuis ben nog eens door een paar boeken (Ik ben bijna klaar met mijn studie operations research). Maar als ik zie wat sommige informatica studenten aan parate kennis hebben, moet ik me gaan schamen...



Edit:

Nog eentje dan om t af te leren
Eentje waarvan Lodi etc van zeiden:

Chen, Lee, and Shen (1995) gave an integer programming formulation for the case where the
bins may have different sizes.

European Journal of Operational Research
Volume 80, Issue 1 , 5 January 1995, Pages 68-76
An analytical model for the container loading problem

Abstract
This paper considers the problem of loading containers with cartons of non-uniform size and presents an analytical model to capture the mathematical essence of the problem. The container loading problem is formulated as a zero-one mixed integer programming model. It includes the consideration of multiple containers, multiple carton sizes, carton orientations, and the overlapping of cartons in a container. This model is then extended to formulate some special container loading problems. Numerical examples are used to validate the model.

Mailadres in profiel

[ Voor 18% gewijzigd door Anoniem: 94210 op 22-04-2005 23:07 ]

[joepP]

Een ILP formulering klinkt leuk, maar je mag dan eerst duizenden euro's neertellen voor een goede solver (cplex). Daarna is het nog maar de vraag of het ILP uberhaubt wel opgelost gaat worden, zeker in het geval van zo'n lastig probleem. Ik vrees dat er "nogal" wat discrete variabelen aan te pas komen, en dat is zeker geen voordeel.

Een heel ander idee: zoek een universiteit op en vraag om een afstudeerder. Dit probleem is uitstekend geschikt voor een student informatica (algoritmische-richting) om op af te studeren. Kost je bijna niets, en dan heb je wel mensen vanuit de hoek waar de kennis zit.

[Zoijar]

Je kanook citeseer even proberen, ipv acm. Bv dit?

Abstract: The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular bins. The problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 1 8 . An exact algorithm for filling a single bin is developed, leading to the definition of an exact branch-and-bound... (Update)

http://citeseer.ist.psu.edu/martello97threedimensional.html

Hier dus: http://citeseer.ist.psu.edu/

(zoals ik al dacht is het dus idd een ontzettend complex probleem...grappig, niet? Zo simpel te formuleren, zo moeilijk op te lossen)

[ Voor 10% gewijzigd door Zoijar op 23-04-2005 12:35 ]

[Anoniem: 118860]

Dit ziet er ook uit als een goeie:

Heuristics for the Container Loading Problem