• +49 431 239710
  • info@fastleansmart.com
    MENUMENU
    • SOLUTIONS
          • PRODUKTE



          • FLS VISITOUR
          • FLS PORTAL
          • FLS MOBILE
          • DISPATCH NOW
          • TECHNOLOGIEN



          • PowerOpt
          • Künstliche Intelligenz
          • BPMN
          • Integration
          • ANWENDUNGEN



          • Field Service Management
          • Mobile Workforce
          • Terminplanung
          • Tourenplanung
          • Mobile Lösungen
          • Wartung und Instandhaltung
          • Auslieferung
    • ÜBER FLS
          • ÜBER FLS



          • Unternehmen
          • Jobs
          • Standorte
          • Blog
          • Warum FLS?
          • FAQ
          • KUNDEN



          • Kunden
          • Branchen
          • Case Studies
          • Kundenstimmen
          • PARTNER



          • Überblick Partner-Programm
          • Business Process Consulting
          • Managed Service Provider
          • System Integrator
          • Value Added Reseller
          • OEM
          • PARTNER PORTAL



          • Registrierung
          • Log-In
    • KARRIERE
    • KONTAKT

          • SIE ERREICHEN UNS




            Telefon: +49 431 239710


            E-Mail: info@fastleansmart.com


          • NEWSLETTER




            Gratis FLS ECHTZEIT-NEWS in Ihr Postfach

            Stets optimal informiert. News abonnieren  ›


          • UNVERBINDLICH TESTEN




            FLS-DE-Demo-Buchen-banner
    • DE
    • EN
    • NL
    DEMO BUCHEN
    ✕

    BLOG / RESEARCH · RUCKSACKPROBLEM

    DAS RUCKSACKPROBLEM



    Beitrag teilen
    6 Min. Lesezeit

      20. Oktober 2017, aktualisiert am 13.01.2022  ·   Dr. Florian Diedrich


    I mmer wenn irgendwo etwas quanti­fiziert wird und auf beste­henden Daten eine Entschei­dung getrof­fen werden soll, ist irgendwo ein Opti­mierungs­problem aufge­treten. Da dieses dann oft wiederholt mit jeweils verschie­denen Daten gelöst werden muss, stellt sich natürlich die Frage nach einem Algo­rithmus. Man möchte dann auch wissen, wie gut dieser zur Lösung des Problems geeig­net ist.

    In diesem Artikel stellen wir ein grundle­gendes Opti­mierungs­problem vor: das Rucksackproblem. Zuerst defi­nieren wir kurz das Problem und nehmen ein paar Eigen­schaften zur Kenntnis. Dann stellen wir einen nahelie­genden Algorithmus zur Lösung dar.

    Achtung: Trotz seines intui­tiven Charak­ters kann der Algorith­mus aber nicht nur sub­optimale, sondern über­raschender­weise sogar beliebig schlechte Lösungen liefern!

    Schließlich stellen wir eine einfache Verbes­serung dieses Algo­rithmus vor, die eine beweis­bare Güte­garantie hat und somit ein Approxi­mations­algorith­mus1 ist.

    DAS RUCKSACKPROBLEM: EINFÜHRUNG


    Beim Rucksackproblem2 sind eine Menge von n Items („Gegenstände“) und ein Rucksack vorge­geben. Dabei hat jedes Item sowohl ein Gewicht als auch einen Profit und der Rucksack hat eine vorge­gebene Kapazi­tät; alle diese Werte sind positiv und ganz­zahlig.

    Das Ziel ist, eine Auswahl von Items zu finden, die zuläs­sig ist (d.h. die Summe ihrer Gewichte übersteigt die Kapa­zität des Rucksacks nicht) und einen maximalen Gesamt­profit hat (d.h. die Summe der Profite ist so groß wie möglich). Ein konkreter Datensatz des Problems wird als Instanz bezeichnet.

    Instanz:
    • Item 1: Gewicht 188, Profit 635
    • Item 2: Gewicht 250, Profit 108
    • Item 3: Gewicht 2100, Profit 545
    • Rucksack mit Kapazität 2500

    Eine optimale Lösung besteht dabei aus den Items 1 und 3 und hat den Profit 1180.

    Ein Bezug zum Field Service Management und zur Logistik ist klar vorhanden, da dort beispiels­weise ein Transport­fahrzeug unter Berück­sichtigung seiner Kapazität profit­maximie­rend mit Gütern beladen werden soll.

    Obwohl dieses Beispiel die Auswahl von phy­sischen Objekten behandelt, kann man ebenso das Gewicht als Zeit interpre­tieren; statt des Rucksacks steht dann zu verpla­nende Arbeits­zeit zur Ver­fügung, wobei die Items zur Auswahl stehende Aufträge sind, deren Profit ein zu erwar­tender wirtschaft­licher Nutzen ist. Ferner kann das Rucksackproblem auch als Teilpro­blem in komplexeren Opti­mierungs­szenarien auftreten.


    DAS RUCKSACKPROBLEM
    Rucksäcke gibt es schon sehr lange. Ebenso alt ist das Problem, sie sinnvoll zu packen. Quelle: FLS GmbH

    Es ist einsichtig, dass man eine optimale Lösung erhalten kann, indem man alle Auswahl­möglich­keiten erzeugt, auf Zuläs­sigkeit überprüft und die Gesamt­profite aller zuläs­sigen Lösungen vergleicht. Da allerdings für n Items die Anzahl der Teilmengen 2n ist, wächst die Anzahl der zu betrach­tenden potenziel­len Lösungen stark in der Anzahl der Items an; dieses Vorgehen ist als nicht praktikabel3 anzusehen. Da das Rucksackproblem gleich­zeitig NP-schwer4 ist, ist die Existenz eines wesentlich besseren exakten Lösungs­algorithmus eher unwahr­scheinlich.

    In jedem Fall kann aber die Instanz ausge­schöpft werden, d.h. wir modifi­zieren die Eingabe so, dass relativ uninte­ressante Randfälle ausge­schlossen werden, das Optimum jedoch nicht verändert wird. Wenn ein Item größeres Gewicht hat als die Kapazi­tät des Rucksacks, kann es in keiner Lösung vorkommen und wird entfernt. Weiter kann geprüft werden, ob alle Items zusammen in den Rucksack passen; falls ja, ist ebenfalls eine optimale Lösung gefunden5.

    EIN GREEDY-ANSATZ


    Eine naheliegende Idee ist, die Items nach ihrer Effizienz zu bewerten und auszu­wählen; intuitiv soll dadurch die zur Verfü­gung stehende Kapazität möglichst gut ausge­nutzt werden. Für jedes Item wird also seine Effizienz (das ist der Quotient aus Profit und Gewicht) berechnet. Dann werden die Items in abstei­gender6 Reihenfolge ihrer Effi­zienz in den Rucksack gepackt, bis kein Item mehr passt.

    Diese Heuristik wird als greedy („gierig“) bezeichnet, da sie versucht, jeweils best­mögliche Einzel­schritte auszu­wählen, aber getrof­fene Entschei­dungen nicht revidieren kann.

    Dieser Algorithmus ist wesentlich schneller als die Bewertung aller potenziel­len Lösungen; allerdings erzeugt sie nicht nur nicht immer eine optimale Lösung, sondern sie kann verglichen mit dem jewei­ligen Optimum sogar beliebig schlecht sein! Dies kann man über­raschender­weise an einer an k parame­trisierten Menge von Instanzen mit nur 2 Items erkennen.

    Instanz:
    • Item 1: Gewicht 1, Profit 1 („schlechtes Item“)
    • Item 2: Gewicht k, Profit k-1 („gutes Item“)
    • Rucksack mit Kapazität k

    Da die Kapazität k ist, die Summe der Gewichte aber k+1, passen nicht beide Items in den Rucksack. Da beide Items alleine aber in den Rucksack passen, kommen nur 2 Lösungen in Frage.

    Weil Item 2 einen größeren Profit hat als Item 1, ist Item 2 die optimale Wahl. Allerdings hat Item 1 eine Effizienz von (k-1)/k, was kleiner als 1 ist; da Item 1 die Effizienz 1/1=1 hat, würde durch die oben erwähnte Heuristik die Wahl auf Item 1 fallen. Weil dies nicht optimal ist, wir aber den optimalen Profit kennen, können wir ausrechnen, welchen Anteil am Optimum unsere Heuristik sicher­gestellt hätte - nämlich den Quotienten aus dem Profit von Item 1 und Item 2. Da dieser 1/(k-1) ist, können wir durch eine geeig­nete Wahl von k die Lösung unserer Heuristik (verglichen mit dem jeweiligen Optimum) beliebig schlecht werden lassen.

    EIN APPROXIMATIONSALGORITHMUS


    Hat unsere Intuition uns etwa getäuscht? Das Auswählen der Items nach Effizienz kann doch nicht völlig falsch sein.

    Nun, das ist es auch nicht. Der Greedy-Ansatz würde optimale Lösungen berechnen, wenn alle Items die gleiche Größe (z. B. 1) hätten, weil dann jede zur Verfügung stehende Einheit der Kapa­zität optimal ausgenutzt wäre; Entweder ist der Rucksack dann immer komplett gefüllt oder die restliche Kapazität kann auch durch gar kein Item genutzt werden.

    Wir stellen uns vor, dass wir unsere Items in Stücke der Größe 1 zer­schneiden, deren Profit jeweils anteilig aus dem Original-Item hervorgeht; somit haben alle diese kleinen Items die gleiche Effizienz wie das Item, aus dem sie entstanden sind und in der Summe auch den Original­profit. Aus jeder zulässigen Lösung der Original­instanz wird durch Zerschneiden der Items eine Lösung der zerschnit­tenen Instanz; da wir also die Lösungs­menge vergrößert haben7, ist das Optimum P2 der zerschnit­tenen Instanz höchstens größer als das Optimum P1 der Original­instanz.

    Weitere Artikel:
    ➡ TOPOLOGISCHE SORTIERUNG
    ➡ TRAVELING SALESPERSON PROBLEM
    ➡ DYNAMISCHE PROGRAMMIERUNG
    ➡ GANTT CHARTS IN DER TOURENPLANUNG

    In der Sortierung unterstellen wir, dass wir bei der Auswahl der kleinen Stücke nicht zwischen verschie­denen Original-Items hin- und herspringen. Führen wir dann unseren Greedy-Algorith­mus aus, wählen wir also zuerst die einzelnen Stücke ganzer Items; das letzte Item passt dann möglicher­weise nicht mehr komplett in den Rucksack. Den Rest dieses Items (nennen wir seinen Index j) heben wir auf. Da unser Rucksack keine freie Kapazität mehr hat und jede Kapazitäts­einheit optimal ausgenutzt ist, ist sein Gesamt­profit das Optimum P2 der zer­schnittenen Instanz.

    Leider ist die erzeugte Lösung nicht zulässig für die Original­instanz, weil das letzte Item j ja zer­schnitten wurde. Die ausge­wählten nicht zerschnit­tenen Items passen zusammen in den Rucksack; nehmen wir Item j komplett dazu, haben wir eine Menge von Items, die zwar zusam­men nicht mehr in den Rucksack passt, deren Gesamt­profit aber insgesamt mindestens das Optimum der Original­instanz ist!

    Wir vergleichen nun den Profit von Item j und den Gesamt­profit der ausge­wählten nicht zer­schnittenen Items und nehmen die bessere der beiden Lösungen. Da die Summe dieser Profite mindestens das Optimum der Original­instanz ist, haben wir somit durch einen effizienten Algo­rithmus beweisbar mindestens die Hälfte des optimalen Profits gesichert.

    Die Gütegarantie von Algorith­men wird üblicher­weise so angegeben, dass sie nicht kleiner als 1 ist (ggf. wird zum Kehrwert überge­gangen). Unser modifizierter Greedy-Algo­rithmus ist somit ein Approxi­mations­algorithmus mit Güte­garantie 2.

    Es ist weiter eine nahelie­gende Frage, ob der oben vorge­stellte Approxima­tionsalgo­rithmus nicht eine bessere Güte­garantie als 2 hat; vielleicht haben wir ja nur dafür keine passenden Argumente gefunden? Leider ist das aber nicht der Fall, wie man an der folgenden, an k parametri­sierten Menge von Instanzen mit jeweils 3 Items sieht.

    Instanz:
    • Item 1: Gewicht 1, Profit 2
    • Item 2: Gewicht k, Profit k
    • Item 3: Gewicht k, Profit k
    • Rucksack mit Kapazität 2k

    Der optimale Profit ist 2k durch Auswahl von Item 2 und Item 3. Der Approxi­mations­algorithmus erreicht durch die Auswahl von Item 1 und Item 2 (oder 3) allerdings nur einen Profit von 2+k. Somit ist also für diese Menge von Instanzen der Anteil des algo­rithmisch gene­rierten Profits am optimalen Profit immer mindestens (2+k)/(2k)=1/k+1/2. Da sich dieser Quotient für größer werdende Werte von k an 1/2 annähert, ist die Güte­garantie von 2 für unseren Algo­rithmus exakt.

    AUSBLICK


    Obwohl das Rucksackproblem selbst relativ einfach zu verstehen ist, gibt es erstaun­lich umfang­reiche Literatur8, in der für die oben vorgestellte Version und andere Formu­lierungen Ergebnisse aus verschie­denen Bereichen (exakte Algorith­men, Approxi­mations­algorithmen, Heuristiken) vorge­stellt werden. Natürlich sind die hier vorge­stellten Inhalte ebenfalls dort zu finden.


    Karriere & Jobs:

    Du bist Student*in oder Absol­vent*in und interes­sierst dich für logistische Problem­stellungen oder für die Software­ent­wicklung?
    Dann warten bei FLS spannende Aufgaben auf dich. Schau dich auf unserem Karriere­portal nach aktuellen Stellen­angeboten um oder bewirb dich einfach ini­tiativ:

    FLS-WEB-Karriere-BG-3

    GEMEINSAM ETWAS BEWEGEN

    Moin-Kultur meets Morgen-Technologie. Jetzt aktuelle Jobangebote entdecken.
    ZUM KARRIERE-PORTAL


    Anmerkungen:

    1 Vijay Vazirani: Approximation Algorithms, Springer, 2003; Klaus Jansen & Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.

    2 Robert Sedgewick: Algorithmen, Addison-Wesley, 1991.

    3 Für 32 Items sind das über 4 Milliarden Teilmengen; falls ein Mensch pro Sekunde eine Teilmenge bewerten könnte, wäre er damit mehr als 135 schlaflose Jahre beschäftigt.

    4 Michael R. Garey & David S. Johnson: Computers and Intractability – A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.

    5 Das ist insbesondere dann so, wenn nach Ausführung der erwähnten Schritte gar kein Item mehr vorhanden ist. Der optimale Zielfunktionswert ist dann 0.

    6 Es ist „monoton fallend“ gemeint.

    7 Die Ersetzung von diskreten Nebenbedingungen (ein Item wird entweder komplett oder gar nicht ausgewählt) durch kontinuierliche Nebenbedingungen (ein Item wird anteilig ausgewählt) wird als Relaxierung bezeichnet; dadurch wird zu einer Obermenge der zulässigen Lösungen übergegangen. Die Zielfunktion bleibt im Wesentlichen gleich; durch den Übergang zu einer Obermenge kann aber das Optimum der Instanz größer werden, weil die Zielfunktion maximiert werden soll.

    8 Silvano Martello & Paolo Toth: Knapsack Problems, John Wiley & Sons, 1990; Hans Kellerer, Ulrich Pferschy & David Pisinger: Knapsack Problems, Springer, 2004; Eugene Lawler: Fast Approximation Algorithms for Knapsack Problems, Mathematics of Operations Research 4(4), 1979.






    ‹  Zurück zur Übersicht


    ‹  Zurück zur Übersicht

    FLS_FlorianDiedrich1_circle
    DR. FLORIAN DIEDRICH
    Software-Entwickler

    +49 431 239710
    E-Mail schreiben

    NOCH EINEN MOMENT ZEIT?

    27. Oktober 2022
    FLS European Field Service Awards

    DOPPELTER ERFOLG FÜR FLS BEI DEN EUROPEAN FIELD SERVICE AWARDS

    27.10.2022 BLOG / COMPANY – Bettina Marksteiner: FLS und sein Kunde Amey haben bei den European Field Service Awards zwei […]
    8. August 2022

    WELCHE BRANCHEN NUTZEN FIELD SERVICE MANAGEMENT SOFTWARE?

    08.08.2022 BLOG / SOLUTIONS – Christoph Bertram: Gutes Außendienstmanagement ist vielerorts gefragt. Welche Branchen Field Service Management einsetzen. – Leistungsfähige […]
    26. Oktober 2022

    30 JAHRE FLS – SEIT 30 JAHREN FÜHRENDE LÖSUNGEN FÜR DIE TERMIN- UND TOURENPLANUNG

    26.10.2022 BLOG / SOLUTIONS – Christoph Bertram: 30 Jahre FLS – FAST LEAN SMART. Aus der WG-Küche zum weltweit erfolgreichen […]



    ZU DEN BLOG-KATEGORIEN

    CUSTOMERS

    RESEARCH

    COMPANY

    EVENTS

    SOLUTIONS

    MEDIA


      Start  ›  DAS RUCKSACKPROBLEM



    PRODUKTE

    FLS VISITOUR

    FLS PORTAL

    FLS MOBILE

    DISPATCH NOW


    WARUM FLS?

    TECHNOLOGIEN

    PowerOpt

    Künstliche Intelligenz

    BPMN

    Integration


    PowerOpt – live?

    JETZT TESTEN  ›

    ANWENDUNGEN

    Field Service Management

    Mobile Workforce

    Terminplanung

    Tourenplanung

    Mobile Lösungen

    Wartung & Instandhaltung

    Auslieferung

    KUNDEN

    Kundenstimmen

    Case Studies

    Branchen


    SERVICES

    Consulting

    Projekt

    Customer Services

    UNTERNEHMEN

    Karriere

    Standorte

    FAQ

    Code of Conduct


    NEWS

    Blog

    Webinare

    Events

    Newsletter

    PARTNER

    Partner-Programm

    BPC

    Managed Service Provider

    System Integrator

    Value Added Reseller

    OEM


    Registrierung

    Partner-Portal Log-In


    Folgen Sie uns

       FLS-social-media-icon-linkedIn    FLS-social-media-icon-xing    FLS-social-media-icon-youtube



    Sicherheit und Qualität nach höchsten Standards. Unsere Stand­orte in Deutsch­land, den Nieder­landen und Groß­britannien sind im Bereich Infor­mations­sicher­heits-Manage­ment (ISO 27001) ISO-zertifi­ziert. Zudem können die deutschen Standorte und die in Groß­britannien ISO-Zertifi­zierungen in den Bereichen Qualitäts­management (ISO 9001) und Umwelt­management (ISO 14001) vorweisen. Mehr Infos ›

    © FLS – FAST LEAN SMART   ·   Datenschutzerklärung   ·   AGB  ·   Impressum
      DEMO BUCHEN
      DE
      • DE
      • EN
      • NL
      • +49 431 239710
      • info@fastleansmart.com

        ECHTZEIT-NEWS-titel


        STETS BESTENS INFORMIERT

        Gratis in Ihr Postfach.
        Jederzeit widerrufbar.


        Keine News mehr verpassen.
        Der E-Mail-Newsletter von FLS.


        NEWS ABONNIEREN