[WI] Berekeningen

[kokkie 20]

Hey mensen
Ik moet nu opdracht maken op school dat ik een applicatie moet bouwen om berekeningen te maken voor een bedrijf dat bakjes maakt.
Maar ik ben echt bagger met wiskunde en heb geen flauw idee hoe ik al die stuff moet uitrekenen dus vraag ik jullie om hulp (A)

Wat basis informatie:

De bedoeling is dat de applicatie uitrekent hoeveel dozen hij nodigt heeft om een X aantal bakjes in dozen te plaatsen (de bakjes gaan per 10,000)

De afmetingen van de bakje:
hoogte (max 32 cm)
breedte (max 32 cm
lengte (max 45 cm)

De bakjes kunnen dus alle maten hebben, maar het gaat mij meer om de formule dan de maten
Maar de bakjes moeten dus ook weer in dozen geplaatst worden...

afhankelijk van te verpakken bakjes
afhankelijk van pallet
maximale grootte: 110 cm x 55 cm x 55 cm

Dus to zover kunnen de bakjes en de dozen variabele afmetingen hebben.

Maar we hebben ook nog 2 dingen die gewoon een constante waarde hebben.

constante binnenafmeting zeecontainer
lengte = 590 cm
hoogte = 235 cm
breedte = 235 cm

constante afmeting pallet
lengte =114 cm
breedte = 114 cm
hoogte = 20 cm

bij het inpakken moet rekening gehouden worden met 2 á 3% pakruimte, dan wel verpakkingsmateriaal

Als iemand mij hiermee kan helpen heel graag.
Thanks

[ILUsion]

Gewoon logisch nadenken: als eerste check kijk je na of het volume van de bakjes passen in een doos (min verpakkingsmateriaal!!); is dat niet het geval, dan moet je de order in meerdere stukjes splitten. Als je weet dat het volume van de bakjes in de doos of container of whatever past, kan je proberen om alle bakjes zo te stapelen dat het past.

Dat kan brute-force (gewoon alles uitproberen, een computer kan daar wel tegen), maar net iets slimmer is een backtracking-algoritme gebruiken. Dat houdt in dat je je programma laat proberen alles te stapelen, lukt het niet meer, dan haal je de laatste doos weer uit de stapeling, probeert in een andere oriëntatie tot het lukt of begint aan een nieuwe doos. Je weet daarmee niet of dat de meest optimale stapeling is; maar wel dat het lukt om die bakjes zo te versturen.

Nu, het kan wel zijn dat het totaal volume van je bakjes kleiner is dan het volume van je doos of container: om het maar heel extreem te nemer: als je doos 50cm*50cm*50cm is en je product 1m*1cm*1cm; dan is het volume van je product wel kleiner, maar zal het nooit kunnen passen. Je moet als je die weg volgt, dus ook nog een weg inbouwen dat als er geen oplossing gevonden wordt, je een groot pak verplaatst naar een andere doos.

Gelukkig zijn er al heel veel toepassingen die gaan rond gelijkaardige problemen; waarschijnlijk ook zelfs heel dicht bij wat je nodig hebt. Maar om maar een gedacht te geven, in 1D (jouw probleem is 3D), komt dat probleem neer op "ik heb een bepaalde hoeveelheid bestanden die ik op cd's of dvd's wil branden; hoe verdeel je de bestanden zodat elke cd zo vol mogelijk staat (dus zo weinig mogelijk cd's verbruikt". Daarvoor bestaat o.a. het programma Burn to the Brim (vrij vertaald is dat "tot de nok volbranden"). In 2D worden gelijkaardige dingen gedaan, om bv. zaagplannen te maken: stel je hebt een grote plaat MDF, metaal, spaanplaat, ... waaruit je enkele stukken wilt zagen (met elk een eigen vorm en eigen afmetingen), met natuurlijk zo weinig mogelijk verlies van materiaal. Dergelijke software houdt er bovendien ook rekening mee dat je door het zagen materiaal verliest (in jouw geval verpakking- en beschermingsmateriaal dat erbij komt). Een voorbeeld van dergelijke software is Saw Optimizer of CutLogic.

Om je maar een idee te geven van wat er op de markt bestaat, waarnaar je kan zoeken om optimalisatie-algoritmes te vinden. Jouw geval is 3D, dus dat houdt in dat je zoekruimte heel wat groter is. In 1D is het relatief makkelijk te doen allemaal: beginnen met de grote blokken, afvullen met steeds kleinere blokken. In 2D en 3D gaat dat principe ook nog steeds wel op, maar in 1D kan je geen rotaties hebben (een bestand neemt steeds even veel plaats in). In 2D kan je nog draaien: in de ene richting past het misschien wel en in de andere niet. In 3D heb je niet 2 oriëntaties maar 6 mogelijke oriëntaties die je kan uitproberen.

Moest ik het zelf moeten schrijven, ik zou proberen het algoritme dat in BTTB gebruikt wordt te schrijven voor 3D; gelukkig is BTTB open-source, zodat je steeds zelf eens een kijkje kan nemen hoe zij het doen. Als je wat rondkijkt op WikiPedia kan je ook interessante dingen vinden, maar sommige van die technieken zijn niet zo simpel (zonder wiskundige achtergrond). In ieder geval kan het je wel op weg helpen om bv. bestaande software te vinden of zelfs hulpsoftware te vinden voor je probleem (bv. in MATLAB bestaat er een optimalisatie-toolbox).