Functie voor berekenen verzendkosten met gewicht &afmetingen

[Roel Broersma]

Al een tijdje ben ik bezig geweest en heb ik ook al rondgezocht (hier op GOT is al helemaal niets te vindern erover).
Ik ben op zoek naar een functie (liefst in ASP, maar PHP mag ook of iets anders, dan vertaal ik hem wel) die de verzendkosten berekend voor een bestelling.

Een bestelling kan bestaan uit meerdere artikelen, elk artikel heeft een eigen afmeting (hxbxd) en een gewicht (in gram), deze heb ik inmidels al allemaal in de database staan.

Nu zou je kunnen zeggen: doe HxBxD, dan weet je het volume, tel dat van alle artikelen bij elkaar op en kijk of het in een doos van formaat X past, zo niet, pak er dan een tweede doos bij. In zekere zin klopt dit, echter heb ik natuurlijk vaak dathet volume wel zal passen alleen de afmetingen niet, (een projectie scherm heeft bijv. het volume zodat het makkelijk in een doos past, het is alleen wel 2meter lang dus past het niet).

Verzendkosten zijn afhankelijk van: Aantal Colli (aantal dozen) en gewicht (aantal Kilo)

Nu ben ik al wel op het volgende gekomen:

Een product kan altijd op MAXIMAAL 6 manieren in een doos worden gestapeld (denk aan een kubus), het aantal mogelijkheden neemt toe naarmate het aantal producten toeneemt met een MACHT. (Hoe meer producten, hoe meer mogelijkheden er afvallen).

Nu dacht ik simpelweg aan een soort Brute Force scriptje wat gewoon alle mogelijke combinaties berekend en per combinatie een 'benchmark' cijfer geeft, het laagste benchmark cijfer is de winnende oplossing (kost het minste verpakkingsmateriaal).

Ook is het zo dat ik de verpakkingsdozen variabel heb. De ene dag heb ik bijvoorbeeld allemaal dozen van 500x400x300 (mm) en de andere dag een aantal van 300x300x300 en een aantal van 400x400x400.

Heeft iemand endig idee of al een dergelijk script ooit gebouwd of ergens in zijn bedrijf werkend ?

[Gomez12]

Roel Broersma schreef op 19 mei 2004 @ 22:38:
Een bestelling kan bestaan uit meerdere artikelen, elk artikel heeft een eigen afmeting (hxbxd) en een gewicht (in gram), deze heb ik inmidels al allemaal in de database staan.

Nu zou je kunnen zeggen: doe HxBxD, dan weet je het volume, tel dat van alle artikelen bij elkaar op en kijk of het in een doos van formaat X past, zo niet, pak er dan een tweede doos bij.

En als je nu doet :
als (H<Hdoos) and
(B<Bdoos) and
(D<Ddoos)
then if
HXDXB < HdoosXDdoosXBdoos

oftewel, kijk eerst eens of de maten van een gewoon produkt wel in een standaard doos passen, dan pas kijken of er nog een 2e produkt bijpast, dus h1+h2 or d2+d1 or b1+b2.

Tot je op een gegeven moment een produkt hebt wat groter is dan de doos.
Weet niet om hoeveel dozen dit gaat, maar voor <5 dozen volstaat dit over het algemeen perfect. Daarna wordt het een stukje ingewikkelder ( ik zou het niet waarderen als een tft van 2m samen met een voeding in een doos thuisbezorgd zou worden door PTT breekkans etc. )

Verzendkosten zijn afhankelijk van: Aantal Colli (aantal dozen) en gewicht (aantal Kilo)

standaard

Nu ben ik al wel op het volgende gekomen:

Een product kan altijd op MAXIMAAL 6 manieren in een doos worden gestapeld (denk aan een kubus), het aantal mogelijkheden neemt toe naarmate het aantal producten toeneemt met een MACHT. (Hoe meer producten, hoe meer mogelijkheden er afvallen).

Dit snap ik niet helemaal meer, ik kan toch echt honderd producten van ,1x,1 cm in een beetje doos stoppen. Dus het afvallen van mogelijkheden zie ik niet helemaal.

Nu dacht ik simpelweg aan een soort Brute Force scriptje wat gewoon alle mogelijke combinaties berekend en per combinatie een 'benchmark' cijfer geeft, het laagste benchmark cijfer is de winnende oplossing (kost het minste verpakkingsmateriaal).

Minste verpakkingsmateriaal is leuk, maar zoals eerder gezegd wordt ik er niet vrolijk van als ik breekbare en zware spullen in 1 doos bezorgd krijg.

Ook is het zo dat ik de verpakkingsdozen variabel heb. De ene dag heb ik bijvoorbeeld allemaal dozen van 500x400x300 (mm) en de andere dag een aantal van 300x300x300 en een aantal van 400x400x400.

Bedoel je hiermee dat je per dag maar een maat hebt, want dan is het simpel gewoon je basismaat veranderen. Anders gewoon alle maten in een dbase zetten en er gelijk een voorraad van bijhouden.

[.oisyn]

Roel Broersma schreef op 19 mei 2004 @ 22:38:
Ik ben op zoek naar een functie (liefst in ASP, maar PHP mag ook of iets anders, dan vertaal ik hem wel) die de verzendkosten berekend voor een bestelling.

Sorry, maar dat is een scriptrequest. In Programming & Webscripting programmeren we onze dingen zelf, je kunt hier niet verwachten dat anderen dat even voor je gaan doen, of hier even de code neerzetten.

Discussies over je probleem mogen natuurlijk wel, maar dan moet je wel even aangeven wat je zoal uitgezocht hebt, en waarom dat niet goed is / het niet lukt

[ Voor 16% gewijzigd door .oisyn op 19-05-2004 23:14 ]

[Tomatoman]

Leuk, optimalisatieprobleem

Roel Broersma schreef op 19 mei 2004 @ 22:38:
Heeft iemand endig idee of al een dergelijk script ooit gebouwd of ergens in zijn bedrijf werkend ?

Ik gok dat er vast weleens iemand zo'n script heeft gemaakt. Aangezien script requests in P&W niet zijn toegestaan is dat het enige wat ik erover ga zeggen

Dit is een lastig probleem dat je niet zomaar even oplost. Wat misschien handig is, is beginnen met een paar eenvoudige checks.
[list]• Op basis van volume valt er al het een en ander te concluderen. Heb je bijvoorbeeld een doos van 5x3x2, dan is het volume 30. Als je nu drie pakjes hebt met de afmetingen 4x1x2, 3x3x2 en 1x5x1, dan is het totaalvolume van die pakjes 8 + 18 + 5 = 31. Dat gaat dus nooit in die ene doos passen.
• Als je een pakje van 6x2x2 hebt, past dat nooit in een doos van 5x3x2. Het pakje is immers te lang. Je kunt dus een check op basis van afmetingen uitvoeren.
• Wat is het totaalgewicht van de pakjes? Wordt de doos niet te zwaar?
Nu je een paar eenvoudige checks hebt, kun je er een optimalisatieprobleem van maken. Dit is wat mij als eerste gedachte te binnen schiet. Je stelt bijvoorbeeld als eis dat een doos minimaal voor 70% gevuld moet zijn. Verder kan een doos natuurlijk nooit meer dan 100% vol zijn. Aangezien het echter wel heel toevallig is dat je een doos precies helemaal vol krijgt, zorg je ervoor dat je de dozen nooit meer dan 90% vult. Als aanname doe je dan dat bij minder dan 90% vulling de pakjes altijd in de doos passen. Dan doorloop je het volgende schema.

1. Doe een nieuw pakje in de doos.
2. Totaalvolume van alle pakjes kleiner dan 70% -> ga naar 1.
   Totaalvolume van alle pakjes tussen 70% en 90% -> klaar, volgende doos.
   Totaalvolume van alle pakjes groter dan 90% -> doos leeggooien en bij 1 beginnen met een ander pakje.

Op basis van deze eenvoudige regels kom je al een heel eind. Door de regels stap voor stap ingewikkelder te maken, kom je tot steeds betere resultaten. Zo kun je bijvoorbeeld de maximale vulgraad van een doos verlagen als er een paar lange pakjes tussen zitten of juist verhogen als je heel veel kleine pakjes hebt.

De garantie dat het altijd gaat passen heb je natuurlijk niet op deze manier, maar als je het goed aanpakt kun je vast wel een score van 95% correct halen. Deze aanpak is de beste als de rekentijd (= kosten) die je ten opzichte van een brute force aanpak bespaart, meer oplevert dan de 5% verkeerd ingeschatte dozen kosten.

[Anoniem: 3057]

Ten eerste: je topic grenst aan een script request, en je topic titel voldoet ook niet aan de regels. Als ik jou was zou ik je topic start even wijzigen in een topic report een mod vragen de titel aan te passen voordat die gesloten wordt.

Ik kan me voorstellen dat je inderdaad een scriptje schrijft om een optimale verpakkingsmanier te bedenken, maar da's behoorlijk lastig.

Je kan bijvoorbeeld best uitvinden wat de optimale verpakkingswijze is, uitgaande van verpakkingen die ofwel een kubus of balkvorm hebben. Met andersoortige verpakkingen wordt het al lastiger, om het heel voorzichtig uit te drukken. Maar dit alleen is niet genoeg. Ik kan me bijvoorbeeld voorstellen dat het soms goedkoper is om 2 kleine ipv 1 grote doos te versturen, ondanks het volume van de 2 kleine dozen groter is dan de grote doos. Daarbij spelen ook andere factoren mee, zoals extra benodigd beschermingsmateriaal voor bepaalde dingen, zoals die styrofoam wokkels die je in pakjes weleens tegen komt, of het maximale gewicht wat in een doos van een bepaalde grootte mag.

Ik vraag me af of je de tijd en moeite erin wil steken om dit te bouwen als het gaat om een relatief klein aantal zendingen. Vaak kan je met menselijk inschattingsvermogen een behoorlijk goede verpakkingsoplossing zien die dicht bij het optimale zit. Die paar euro die je uitspaart zijn dan het aantal uren scripten X je uurloon niet waard.

Als je dit toch wil maken, kom dan met wat code .... want he is niet de bedoeling dat mensen je kant-en-klare scripts gaan aanleveren.

Succes

[Soultaker]

Je hebt een klassiek optimalisatieprobleem geformuleerd, dat ook wel bekend staat als bin packing; jouw geval wordt wel beschreven als 3D bin packing. Net als voor veel andere optimalisatieproblemen zijn er voor bin packing problemen geen efficiente standaardoplossingen. Er zijn wel een heleboel praktische algoritmen beschikbaar (en ook in gebruik, voor het inrichten van de lading van containers en vrachtwagens enzo) maar echt eenvoudig zijn die doorgaans niet. Een voorbeeld is deze 3D Load Packer (de demo is wel leuk om mee te spelen).

In jouw geval zou ik gewoon voor een brute force oplossing gaan. Slim optimaliseren is erg ingewikkeld en als je minder dan, zeg, 100 producten in een bestelling hebt niet strict noodzakelijk.

[ Voor 6% gewijzigd door Soultaker op 19-05-2004 23:32 ]

[Glimi]

Je kunt even kijken naar deze collegesheets over benaderingsalgoritmes wat een mogelijke oplossing kan zijn.
Als je dat te ingewikkeld vind, dan kun je altijd aan de slag met een greedy algoritme. Dat geeft je echter geen optimale oplossing. De vraag is sowieso of je een optimale oplossing kunt vinden in een redelijke tijd

[Jelmer]

Nav Soultaker's post: [google=3d bin packing php]

Some random items that might help...

An algorithm in C:
http://www.diku.dk/~pisinger/3dbpp.c

Code and research papers:
http://www.or.deis.unibo....pages/ORcodes/TSpack.html

Paper discussing the problem with code examples:
http://archive.cs.uu.nl/p...hreps/CS-1996/1996-39.pdf

US Air Force paper with flow chart, diagrams and an algorithm:
http://www.au.af.mil/au/d...t/afit-gor-ens-01m-02.pdf

offtopic:
BTW, tnx Soultaker voor het naamgeven van het beestje! Kan ik mooi in mn scriptie gebruiken

[samo]

Je zou ook kunnen kijken naar de maximum afmetingen... Een pakket van 10*10*200 past nooit in een doos van 100*100*100, dus daar is het niet voor nodig. Scheelt je ook weer wat berekeningen

[Tomatoman]

samo-arne schreef op 20 mei 2004 @ 00:07:
Je zou ook kunnen kijken naar de maximum afmetingen... Een pakket van 10*10*200 past nooit in een doos van 100*100*100, dus daar is het niet voor nodig. Scheelt je ook weer wat berekeningen

Ahum...

tomatoman schreef op 19 mei 2004 @ 23:25:

• Als je een pakje van 6x2x2 hebt, past dat nooit in een doos van 5x3x2. Het pakje is immers te lang. Je kunt dus een check op basis van afmetingen uitvoeren.

Lezen is een kunst