hier mal ein Aufruf zum kollektiven Brainstorming :
ich will für ein Versandsystem eine Routine entwickeln, die mir für eine Menge von Produkten vorschlägt, in wie viele Kartons welcher Grösse die am günstigsten verpackt werden sollen (wobei nach geringster Anzahl Kartons optimiert werden soll) .
Gegeben ist also
für jedes Produkt Länge, Breite, Höhe, Stückzahl
für jeden Kartontyp Länge, Breite, Höhe
beliebige Stückzahlen verschiedener Produkte dürfen in einen Karton
Produkte dürfen längs oder quer, stehend oder liegend verpackt werden
Und nun suche ich nach einem Algorythmus der mir ausgibt, wieviel Stück welches Produktes ich in welcher Position in einen Karton welchen Typs packen muss, um
mit so wenig wie möglich Kartons auszukommen.
Dabei ist ein grösserer Karton zwei kleineren vorzuziehen, da die Fracht von der Anzahl der Kartons abhängt, nicht von deren Grösse oder Gewicht .
Habt Ihr da irgenwelche Ideen dazu ?
Ein Packer nannte mir als Strategie „Augenmass und Erfahrung“, aber das kann ich nicht programmieren …
Also vornweg eine Anmerkung : So einen Algorithmus zu entwickeln, ist richtige Arbeit und üblicherweise nicht umsonst zu haben … weil nämlich der Entwickler auch Zeit und Geld genau für dieses know-how ausgegeben hat, der Böse …
aber einen kleinen Tip will ich Dir geben : es handelt sich um ein typisches Problem der Linearen Optimierung. Guckst Du am besten google.
Es gibt Strategien, welche evolutive Konzepte benutzen. Die konvergieren recht schnell gegen eine gute Lösung, wobei aber unklar bleibt, ob die gefundene beste Lösung die best mögliche ist.
wie werden die einzelnen blöche auf der festplatte gespeichert?
die problemstellung ist ähnlich, es gibt verschiedene lösungsansätze … best-in/worst-out, worst-in/worst-out … lineare optimierung hört sich zwar auch gut an, nur fällt mir dazu auf die schnelle kein richtiger ansatz ein … ein algorithmus, die - wie ein poster schon vor mir schrieb - bereits ziemlich ins kommerzielle abdriftet …
Sieht ja irgendwie aus, wie (für mich zu) hohe Mathematik,
allein die Konzepte die Ihr gennannt habt, sind ja schon griechische Bahnhöfe … Lineare Optimierung und so’n Zeug .
Unterm Strich heisst das also, dass ich da mit einer wie auch immer pfiffigen Abfrage oder ein paar UND/ODER-Bedingungen in ein Paar Schleifen nicht hinkomme, gelle ?
Kann ich also meinem Chef ruhigen Gewissens sagen, dass dieses Thema nix für 'ne Eigenentwicklung im Hause ist und er da die Finger von weg lassen soll . Besser iss das .
Unterm Strich heisst das also, dass ich da mit einer wie auch
immer pfiffigen Abfrage oder ein paar UND/ODER-Bedingungen in
ein Paar Schleifen nicht hinkomme, gelle ?
im prinzip ist ja das ganze zeugs ein bißchen und/oder und schleifen und verzweigungen … nur der algorithmus, worauf das ganze aufbaut, muß halt erstmal durchdacht werden …
Kann ich also meinem Chef ruhigen Gewissens sagen, dass dieses
Thema nix für 'ne Eigenentwicklung im Hause ist und er da die
Finger von weg lassen soll . Besser iss das .
naja, wenn ihr genügend resourcen habt und vor allem eine menge zeit zum nachdenken und herumtüfteln, dann geht das schon … nur genau diese 2 punkte sind meist die hindernisse …
ich kann nur raten:
Spart euch die Zeit, die ihr bräuchtet, um euch in solch ein Thema einzuarbeiten und einzulesen.
Dies sollte z.B. ein Informatiker oder Mathematiker in Angriff nehmen, weil man das eigentlich in seinem Studium oft genug durchkaut.
Für einen Mathematiker ist es ein Klacks, so einen Algorithmus zu produzieren. Man spart so am meisten Zeit und Geld.
Und: Der Mathematiker produziert einen Algorithmus, der alle möglichen Fälle abdeckt. Ein Laie wird garantiert an gewisse möglichen Fälle nicht denken…
… nicht unbedingt!
Gib doch mal bei Google folgenden Suchbegriff ein:
„Genetischer Algorithmus Packproblem“.
Beim 1. Treffer ist ein Java-Applet-Beispiel dabei, allerdings nur 2 dimensional.
Sicherlich muß man sich in die Thematik ‚Genetischer Algorithmus‘ einarbeiten, aber die Umsetzung sollte nicht so schwierg sein.
Übrigens handelt es sich dabei um ein kombinatorisches Optimierungsproblem. Also nichts mit linearer Optimierung, meine ich!
Übrigens handelt es sich dabei um ein kombinatorisches
Optimierungsproblem. Also nichts mit linearer Optimierung,
meine ich!
Und ich behaupte, dass das Problem linear zu lösen ist. Es gibt immer mehrere Ansatzmöglichkeiten für Algorithmen; für mich ist entscheidend, welcher der leichter zu verifizierende ist, und da steigt beim nichtlinearen Ansatz der Aufwand mit der Zahl der Kombinationsmöglichkeiten auch nicht mehr linear …
Übrigens handelt es sich dabei um ein kombinatorisches
Optimierungsproblem. Also nichts mit linearer Optimierung,
meine ich!
Und ich behaupte, dass das Problem linear zu lösen ist.
Was zu beweisen wäre!
Um das Problem linear lösen zu können muss es doch erstmal linear sein und das sehe ich beim besten Willen nicht! So wie ich das sehe ist jede Packung-Position eine Funktion der jeweiligen anderen Packung-Positionen.
Was zu beweisen wäre!
