Suche "Optimierungsalgorithmus"



  • Ich suche für folgendes Szenario eine Algorithmus (Wikipedia, Links, ...) oder Idee wie man das möglichst "optimal" lösen könnte

    Hintergrund: ich hab mal vor Jahren an einem Problem dieser Art gesessen und wollte mir das nochmal anschauen - aber nicht ohne zu Prüfen ob es schon Ansätze für sowas gibt 🙂

    Gegeben:

    1. ich habe viele kleine Pakete die in große Säcke gepackt werden sollen
    2. die großen Säcke haben ein max. Gewicht das nicht überschritten werden darf
    (das Volumen des Sacks reicht immer aus - vorher wird er zu schwer)
    3. die Gewichte sind immer durch 2 ohne Rest teilbar (falls das was bringt)
    4. es sollen so wenig große Säcke wie nötig verbraucht werden
    5. ein kleines Pakete überschreitet nicht das max eines große Sacks

    Tips?



  • Das ist doch im Groben das Rucksackproblem, nur daß du dann iterativ mehrere Säcke füllst (bis kein Paket mehr übrig ist).





  • Danke euch beiden

    @Th69

    ja sieht sehr passend aus

    Ist es bei dem Rucksackproblem unrelevant das alle meine Pakete die gleiche Wertigkeit haben (nur unterschiedliche Gewichte) - oder führt das zu schlechteren Ergebnissen? - ich denke nicht

    @audacia

    kann man da noch weiter Eingrenzen - ich finde da jetzt nicht so wirklich einen passenden Ansatz



  • Das beschriebene Problem ist nicht das Rucksack-Problem (bei dem man einen CORE-Algorithmus verwenden könnte), sondern das Bin-Packing-Problem. Hier liefern bereits sehr einfache Heuristiken sehr brauchbare Ergebnisse. Die Laufzeiten der Algorithmen, die die theoretisch besten Ergebnisse liefern, sind jenseits von Gut und Böse. Also schnapp dir einfach First Fit oder was Ähnliches.



  • Gast3 schrieb:

    @audacia

    kann man da noch weiter Eingrenzen - ich finde da jetzt nicht so wirklich einen passenden Ansatz

    Auf der englischen Wiki-Seite zum Bin-Packing-Problem (wußte ich auch nicht, daß das so heißt) findest du eine ILP-Formulierung des Problems:
    https://en.wikipedia.org/wiki/Bin_packing_problem#Formal_statement
    Ich würde erwarten, daß für eine überschaubare Behältermenge ein generischer ILP-Solver für deine Zwecke schnell genug ist.



  • das größte Szenario das ich damals (in einer Simulation) hatte waren um die 3500 kleine Pakete, das konnte aber schon mit entsprechend langer Vorplanung passieren


Log in to reply