Paketinhalte berechnen |
| 26.10.2004, 20:31 | Torsten Sentz | Auf diesen Beitrag antworten » | ||
| Paketinhalte berechnen ich habe folgendes Problem. Kann mir dabei eventuell einer helfen. Ich habe Pakte in der Grösse L 600 x B 220 x H 270. Nun kann man aus einem Programm einzelne Produkte mit Längen, Breiten und Höhen Angaben auswäheln. Beispiel: 10 Kataloge mit den Massen 297 x 210 x 20 pro Stück. 5 Kataloge mit den Massen 150 x 105 x 20 pro Stück. Das Programm soll nun melden, ob die bestellten Artikel in ein Paket passen oder ein weiteres Paket gepackt werden muss. Ich komme da nicht so richtig auf eine Lösung. Danke, Torsten |
||||
| 26.10.2004, 21:53 | Hartmann | Auf diesen Beitrag antworten » | ||
| RE: Paketinhalte berechnen Hallo Torsten, eine Lösung kann ich Dir zwar nicht anbieten, aber es handelt sich hier um das "Rucksackproblem". Leicht zu formulieren und schwer zu lösen, ähnlich dem Problem des Handlungsreisenden. Wenn die Größe der Packstücke nicht SEHR viel kleiner ist als das Paket (um das 5 bis 10-fache), lohnt sich das Ausprobieren (also eigentlich die Kisten zu basteln). Wenn Du im Web nach "Rucksackproblem" suchst, wirst Du dessen Tiefe schnell erkennen. (Ich hoffe sehr, daß Du kein Mathestudent mit dem Hauptfach "Optimierungstheorie!" bist, und ich Dir was Neues sagen konnte) Grüße, Hartmann |
||||
| 27.10.2004, 01:20 | Ben Sisko | Auf diesen Beitrag antworten » | ||
| RE: Paketinhalte berechnen Hallo Hartmann, dies ist kein "Rucksackproblem", denn Torsten will nicht die Anzahl/das Volumen o.ä. maximieren, was in ein Paket passt, sondern er will auf jeden Fall alle Packstücke verschicken und nachschauen, wie viele Pakete er dazu braucht. Stimmt doch? @Torsten Gruß vom Ben |
||||
| 27.10.2004, 01:32 | pumuckl | Auf diesen Beitrag antworten » | ||
Das Beispiel sieht recht einfach zu lösen aus: Die 10 Kataloge mit 297 x 210 x 20 müssen mit der langen kante längs des Pakets ausgerichtet werden, da die 297 für alle anderen richtungen zu lang sind. Also packt man je zwei Kataloge aneinander so dass dann die maße 594 x 210 x 20 je 2 kataloge oder 594 x 20 x 210 je 2 kataloge (also hochkant) entstehen. alle 10 zusammen ergeben dann 594 x 210 x 100 von den 5 anderen packst du 4 in eine ebene, macht dann 600 x 210 x 20 für 4 Stück - den letzten oben drauf macht insgesamt grob 600 x 210 x 120 plus den losen kleinen katalog - in die kiste passt also weit mehr als das doppelte... |
||||
| 27.10.2004, 09:38 | Torsten Sentz | Auf diesen Beitrag antworten » | ||
| RE: Paketinhalte berechnen Hallo, Ben hat recht mit seiner Aussage. Hier noch mal als weitere Info. Ich schreibe eine Software. Kunden könne Online aus verschiedenen Produkten auswählen und diese bestellen. Ein Mitarbeiter holt sich dann diese Bestellungen aus einer Datenbank. Nun soll das Programm je nach dem wieviel und was bestellt wurde entweder 1 oder n Versandaufkleber ausdrucken. Deshalb muss die Software erkennen, wenn ein Paket voll ist und ein zweites virtuell packen. pumuckl: Mit den beiden Produkten gebe ich Dir recht. Es gibt aber noch weitere Produkte mit unterschiedlichen Grössen :-( Und ausserdem muss das ganze noch in eine Software gebaut werden. :-( Gruss Torsten |
||||
| 27.10.2004, 09:46 | Tobias | Auf diesen Beitrag antworten » | ||
Guck mal hier wie kompliziert die Materie ist: http://www.innovations-report.de/html/be...icht-28036.html Wenn deine Produkte jedoch alle kubisch sind (Länge, Höhe, Breite), dann lässt es sich evt. vereinfachen. Trotzdem bleibt es ein Problem der dynamische Programmierung (was dem Rucksackproblem sehr nahe kommt). Dynamische Programmierung ist so zu verstehen, dass man zuerst das Optimum für kleine Probleme sucht und danach induktiv das große Problem zusammensetzt. |
||||
| Anzeige | ||||
|
|
||||
| 27.10.2004, 10:03 | Joerghamster | Auf diesen Beitrag antworten » | ||
das problem sollte recht leicht zu lösen sein, indem man für alle produkte die maximalen kantenlängen dem programm angibt, sie also als quader berachtet. dann brauchst du 3 werte zum vergleich. du baust dir im prinzip aus den Produkten die du hast im programm ein großes zusammen, indem du die höhe aufaddierst und jeweils die größte länge und breite nimmst. du kannst so lange dazupacken, wie die aktuelle höhe + der dazuzupackenden höhe die gesammthöhe des pakets nciht übersteigt. damit weißt du sehr schnell wie viele pakete du brauchst. is ein ganz simples programm ohne etwas zu optimieren. wenn du ausrechnen möchest wie viel maximal in die kiste geht wird es etwas komplitzierter |
||||
| 27.10.2004, 12:18 | Tobias | Auf diesen Beitrag antworten » | ||
Ich kann dir nicht ganz folgen, wie du das meinst.
Ist nicht genau hier die Schwierigkeit? Kannst du das mal weiter ausführen? |
||||
| 27.10.2004, 12:30 | Joerghamster | Auf diesen Beitrag antworten » | ||
ich würde 3 variablen nehmen, eine die aktuelle länge, eine die aktuelle höhe und eine die aktuelle breite. jedesmal wenn nun ein artikel hinzugefügt wird, wird als erstes geprüft ob die maximale höhe des kartons minus die aktuelle höhe größer ist als die höhe des artikels. ( wenn nein neuer karton, eventuell noch prüfen ob er hochkant reingeht ) wenn ja wird geprüft ob die breite des artikels größer ist als die aktuelle breite und die länge des artikels größer als die aktuelle länge und wenn ja die werte aktualisiert. ich hab ja schon geschrieben das dabei keinerlei optimierung dabei ist. wird ein artikel hinzugefügt wird er einfach oben drauf gepackt. als überprüfung ob das letzte noch hochkant passt, kann geprüft werden ob die max breite des kartons mius die aktuele breite größer ist als die höhe des artikels und die breite des artikels nicht größer als die max höhe. |
||||
| 27.10.2004, 13:31 | Tobias | Auf diesen Beitrag antworten » | ||
Achso. Aber ich glaube, dass gerade für kleine Artikel diese Approximation zu schlecht ist um praxistauglich zu sein. Ich hab aber auch keinen optimierten Lösungsvorschlag, sondern auch wieder eine Annäherung an das Problem. So wie ich das mitbekommen habe stehen folgende Dinge fest: 1.) Das zu packende Paket ist immer gleich groß. 2.) Die Objekte sind Quader Man könnte also verschiedenen Schachtelgrößen A1, ..., An vordefinieren, von denen man weiß, dass sie in Konstellation miteinander genau in die große Kiste passen. (indem man wie beim DinA jeweils halbiert) Ich hab da mal eine Skizze gemacht. (Von oben betrachtet). Jetzt ordnet man die Objekte, die man einpacken soll, bestimmten Schachteln zu. Prinzip: So klein wie möglich, so groß wie nötig. Dann hat viele Schachteln A1, ..., An die man nun bequemer in ein Packet aufteilen kann. Da kommt dann aber blöderweise noch ne dritte Dimension dazu. Nur mal so eine (ausbaufähige) Idee. |
||||
| 27.10.2004, 13:57 | Joerghamster | Auf diesen Beitrag antworten » | ||
die idee is auch nicht schlecht, es bleibt nur bei deiner überlegung 1 problem . . . du hast viele verschiedene schachteln. wie merkst du dir wieviel plaz schon belegt ist ?? man könnte theoretisch den karton auch als ein 3 dimensionales array ansehen. nun bräuchte man nur noch einen algorythmus, um zu prüfen, ob der nächste artikel noch rein passt und wie. alledings dürfte es doch recht komplitzert werden |
||||
| 27.10.2004, 14:07 | Tobias | Auf diesen Beitrag antworten » | ||
Nun, die Kategorisierung der Schachteln muss ja dreidimensional verlaufen. Dann reicht A1 als Angabe nicht aus. Man benötigt eher . x ist die Einheit der Grundfläche, y die der Höhe. Wenn ich nun alle meine Objekte zugeordnet habe sage ich ganz schelmisch: Für zwei Kisten brauche ich einen halben Karton, für 15 Kisten brauche ich 15/8 Kartons, etc. Dann addier ich und hoffe, dass was gutes rauskommt. 
Die Frage ist ja, wieiviel Aufwand man in solch eine Software stecken will und ob sie 3 Tage oder 3 Sekunden für die berechnung brauchen soll. |
||||
| 27.10.2004, 14:16 | Joerghamster | Auf diesen Beitrag antworten » | ||
hmm ich hab gerade ne eigentlich recht gute idee dazu muß ich aber noch durchdenken, sonst schreib ich sicher was anderes als ich mein. werde es morgen mal posten. is ein einfacher algoryxthmus der aber denkeich recht hohe packraten ermöglicht ^^ |
||||
| 28.10.2004, 01:09 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Wenn ich recht verstehe, packst du hier aber immer einfach oben drauf. Dabei sind leicht Situationen vorzustellen, wo mehr Pakete herauskommen als eigentlich notwendig sind. Oder wie bewerkstelligst du es hier, dass ein kleines Paket noch neben ein anderes kleines gepackt wird? |
||||
| 28.10.2004, 09:15 | Joerghamster | Auf diesen Beitrag antworten » | ||
Das war nur ne ganz grobe überlegung. ich hab ja selbst dazugeschrieben das es einfach oben drauf gepackt wird. um es effektiv zu machen müßte mann das programm denke ich schichtweise packen lassen. also z.b. erste schicht der boden. als nächstes müßten die ganzen produkte größenmäßig in verschiedene kategorien eingeordnet werden. Berechnen tut man ganz am ende, also wenn alle artikel drinnen sind. dann gehts los. man nehme das größte produkt, lege es unten rein. dann schauen wieviel platz noch frei ist und das nächstgrößte produkt nehmen das reinpasst. das ganze so lange wiederholen, bis kein platz mehr ist. dann die nächste lage ( boden + größte höhe der ersten laage ) und das selbe wieder. Als nächstes problem bleibt noch, das die produkte nciht alle gleich hoch sind. das löst man, indem man schaut, wie hoch das höchste der ersten laage ist. Dann rechnet man, wie oft jedes andere produkt in das höchste geht und fasst soviel zu einem zusammen zur berechnung. damit sollten die hohlräume im paket minimal werden bei recht geringem aufwandt |
||||
| 29.10.2004, 01:58 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Genau das ist ja das Problem, schauen, ob "nebendran" noch Platz ist usw. |
||||
| 29.10.2004, 02:13 | Tobias | Auf diesen Beitrag antworten » | ||
Das Problem ist mehr oder weniger gelöst, wenn man die Produkte wie in meinem Beitrag zuvor beschrieben kategorisiert hat. Bei A1 weiß du, dass die Hälfte belegt ist, etc. Man könnte z.B. die Grundfläche als Matrix Boole'scher Werte auffassen, wobei die kleinste Schachtel-Kategorie die Auflösung des Rasters bestimmt. Dann kann man entsprechend viele Werte auf true setzen, wenn eine Schachtel hinzugefügt wird. Das Auffinden von freien Flächen in solch einer Struktur ist auch nichtmehr problematisch. Benutzt man zusätzlich einige Packregeln" wie z.B. "die Schachtel wird immer sowei wie möglich links und dann soweit wie möglich vorne eingefügt", dann lässt sich der Algortihmus gescheit formuliern. Man muss sich immer im Hinterkopf behalten, dass hier keine Packstrategie ausgegeben werden soll sondern nur die Anzahl der benötigten Pakete. |
||||
| 29.10.2004, 02:24 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Dabei machst du es dann aber auch nur zweidimensional, oder? Wie bringst du verschiedene Höhen rein? |
||||
| 29.10.2004, 02:34 | Tobias | Auf diesen Beitrag antworten » | ||
Auch hier haben wir Ansätze: Der Erste ist nur brauchbar, wenn die zu packenden Objekte keine allzu großen Höhendifferenzen aufweisen. In diesem Fall hat man ein quasie-zweidimensionales Problem, indem man ein Paket virtuell in Schichten packt. Die zweite ist die Ausweitung der Kategorien auf zwei Dimensionen. Eine Schachtel hat dann die Kategorie , wobei sich y an der Gesamthöhe des Pakets ausrichtet und jeweils auch halbiert wird. Entsprechend arbeitet man dann intern auch mit dreidimensionalen Strukturen. Wichtig ist hier, dass man seinen Programmcode unabhängig vom Raster programmiert um das Raster evt. dynamisch an die Objekte anzupassen. Aber das kann man leicht daherreden. Sowas zu implementieren erfordert schon einiges an Gehirnaktivität. |
||||
| 29.10.2004, 08:52 | Joerghamster | Auf diesen Beitrag antworten » | ||
die freie fläche hatte ich mir auch mit einer matrize vorgestellt. die höhe allerdings soltle leichter machbar sein packe die erste ebene ohne auf die höhe zu achten. schaue dann wie hoch das höchste ist und wie oft die höhen der anderen dann hineinpassen. wenn ein anderes produkt weniger als halb so hoch ist, und es 2 mal existiert wird das zweite virtuell auch noch dazugepackt. wenn kein zweites existiert kann man immer noch alle produkte kleiner gleich der grundfläche anschauen ob es eines gibt das höhenmäßig reinpasst. das meiste implementierst du über abfrageschleifen die immer gleich sind. das einzige mit etwas hirnakrobatik wird sein, die matrize richtig zu füllen und auszuwerten, da man ja die zusammenhängenden punkte zählen muß und nciht die allgemein noch freien. Gruß |
||||
| 06.09.2023, 12:11 | nikk | Auf diesen Beitrag antworten » | ||
| RE: Paketinhalte berechnen und gelöst? |
||||
| 06.09.2023, 15:22 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Kannst ja dem Joerghamster eine email schreiben - mit viel Glück stimmt seine email-Adresse nach 19 Jahren noch.
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
