Zur MathePrisma-Startseite
Zur Modul-Startseite  


Dynamisches Programmieren (konkreter Fall )
 

  
 
  
 
 Jetzt wenden wir das Prinzip des dynamischen Programmierens auf unsere Kommissionierungsaufgabe an.
Aufgabe: kürzester Weg beim Kommissionieren
Gegeben ist eine Menge von Gassen G1, ..., Gn (das Lager)
und ein Auftrag mit Picks in bestimmten dieser Gassen, bezeichnet mit Gi(1), ..., Gi(m).
Gesucht ist der kürzeste Weg
  • von der Verpackungsstation
  • über alle Picks
  • zurück zur Verpackungsstation.
Dabei soll der Weg die Gassen nach aufsteigenden Nummern durchlaufen, d.h. i(1) < i(2) < .... < i(m).
 
 Mehr dazu?
 
  
Voraussetzungen für dynamisches Programmieren
 Die Problemgröße ist m, die Anzahl der Gassen in denen gepickt wird.

Als verwandte Teilprobleme kleinerer Größe j betrachten wir alle Aufgaben, den kürzesten Weg zu finden

  • von der Verpackungsstation
  • über alle Picks der Gassen Gi(1), ..., Gi(j)
  • bis zur Ausfahrt am Nord-Ende oder am Süd-Ende der Gasse Gi(j), jedoch ohne Rückfahrt zur Verpackungsstation.
Für jede Problemgröße j sind dies zwei Aufgaben (Nord-Ende und Süd-Ende).
Warum ist dies sinnvoll?
 Die Lösung zu einem der beiden Probleme der Größe j lässt sich durch Erweiterung der Lösungen zu den beiden Problemen der Größe j-1 gewinnen:
erstes Problem der Größe j
 Der kürzeste Weg mit Ausfahrt am Nord-Ende von Gasse Gi(j) ist einer der folgenden vier:

der kürzeste Weg mit Ausfahrt am Nord-Ende von Gasse Gi(j-1), ergänzt um 
  • entweder 

    • den Weg von dort zum Nord-Ende von Gi(j) (Einfahrt), 
    • picken in Gi(j), wenden und dann 
    • Ausfahrt am Nord-Ende     (Typ NNN)

  • oder 

    • den Weg von dort zum Süd-Ende von Gi(j) (Einfahrt), 
    • picken in Gi(j), durchfahren und
    • Ausfahrt am Nord-Ende     (Typ NSN)

      (Im Beispiellager ist dieser Typ NSN immer länger als Typ NNN)


der kürzeste Weg mit Ausfahrt am Süd-Ende von Gi(j-1), ergänzt um 

  • entweder

    • den Weg von dort zum Süd-Ende von Gi(j) (Einfahrt), 
    • picken in Gi(j), durchfahren und dann 
    • Ausfahrt am Nord-Ende     (Typ SSN)

  • oder

    • den Weg von dort zum Nord-Ende von Gi(j) (Einfahrt), 
    • picken in Gi(j), wenden und dann 
    • Ausfahrt am Nord-Ende     (Typ SNN)

      (Im Beispiellager ist dieser Typ SNN immer länger als Typ SSN)

nicht optimale Erweiterungen ausschließen
 Von allen Wegen können wir jeweils die Länge berechnen. Der kürzeste davon ist der gesuchte kürzeste Weg mit Ausfahrt am Nord-Ende von Gasse Gi(j).
zweites Problem der Größe j
 Analoges gilt für den kürzesten Weg mit Ausfahrt am Süd-Ende von Gasse Gi(j) mit den vier Typen SSS, SNS, NNS, NSS.
 
 Und die Rückfahrt zur Verpackungsstation?
Beim Ausgangsproblem war der Weg durch das Lager an der Verpackungsstation zu beenden. Diese Aufgabenstellung passt in unser soeben entwickeltes Schema, wenn wir die Verpackungsstation einfach als letzte anzufahrende Gasse betrachten, mit der Besonderheit, dass die Gassenlänge Null ist und Nord- und Süd-Ende identisch sind.
 
  
Seite 4/5