De meest efficiënte manier om een doos in te pakken?

Wiskunde is niet alleen een vak op school. Kom je ergens in de praktijk (bijvoorbeeld tijdens je werk) een wiskundig probleem tegen dan kun je hier om hulp vragen.
Plaats reactie
wfelmigo
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 09 mar 2023, 22:45

De meest efficiënte manier om een doos in te pakken?

Bericht door wfelmigo » 10 mar 2023, 21:43

Hoi!

Wie kan mij helpen met deze hersenkraker?

Eerst een voorbeeld:
Ik heb een doos van 10x10x10 cm, ook wel 1000 cm³.
Ik heb twee items:
Item A is 8x7x6 cm, ook wel 336 cm³.
Item B is 6x6x5 cm, ook wel 180 cm³.

Het totale volume van beide items is dus 516 cm³, wat makkelijk in de doos van 1000 cm³ zou moeten passen. Alleen hoe je de items ook in de doos probeert te stoppen -op of naast elkaar- de lengte, breedte en hoogte zijn altijd groter dan die van de doos. Het past dus niet in de doos, ook al past het volume wel.

Hier ben ik naar opzoek:
Nu probeer ik een methode of formule te vinden waarmee ik kan berekenen of items in een doos passen. Het doel is dus om te achterhalen of een set met items wel/niet in een doos past, of hoe groot een doos minimaal moet zijn om een set items zo efficiënt mogelijk in te pakken. Alle items hebben slechts één lengte, breedte en hoogte.

Zo ver ben ik gekomen:
Het enige dat ik zelf heb kunnen bedenken is dit:

De lengte, breedte en hoogte van een item trek ik af van de lengte, breedte en hoogte van een doos. Dit doe ik drie keer (voor iedere as: X, Y en Z) want je kunt een item liggend, staand of in de diepte in een doos leggen. Wat steeds overblijft is lege ruimte, die ruwweg te verdelen is in 3 nieuwe (kleinere) dozen. Vervolgens doe ik dezelfde berekening met de andere items, maar dan op deze kleinere doosvormen, de lege ruimte die steeds overblijft dus.

Nu moet je met deze berekeningen -lijkt mij- ergens op een punt komen waarbij je weet: Als je item A in de lengte legt, item B en C in de breedte, en item D in de hoogte, dan is dat de meest efficiënte manier en heb je een doos met de afmetingen X*Y*Z nodig.

Klopt dit? Kan je dat op deze manier berekenen?
Of denk ik nu veel te moeilijk?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: De meest efficiënte manier om een doos in te pakken?

Bericht door arie » 11 mar 2023, 14:28

Dit is het Bin-packing-probleem, en daarvoor bestaat geen eenvoudige oplossing/algoritme.
Zie bijvoorbeeld https://en.wikipedia.org/wiki/Bin_packing_problem.
Op die pagina worden ook een aantal zoekmethoden gegeven waarmee je een zo optimaal mogelijke oplossing kan vinden.
Kom je daarmee verder?

wfelmigo
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 09 mar 2023, 22:45

Re: De meest efficiënte manier om een doos in te pakken?

Bericht door wfelmigo » 11 mar 2023, 17:46

Het Bin-Packing probleem, zo heet het dus. Ik denk dat ik hier inderdaad verder mee kan. Bedankt!

Plaats reactie