MathePrisma Logo

Dynamisches Programmieren

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 \(\text{G}_1\), ..., \(\text{G}_{\text{n}}\) (das Lager)
und ein Auftrag mit Picks in bestimmten dieser Gassen, bezeichnet mit \(\text{G}_{\text{i}(1)}\), ..., \(\text{G}_{\text{i}(\text{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 \(\text{G}_{\text{i(1)}}\), ..., \(\text{G}_{\text{i(j)}}\)
  • bis zur Ausfahrt am Nord-Ende oder am Süd-Ende der Gasse \(\text{G}_{\text{i(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 \(\text{G}_{\text{i(j)}}\) ist einer der folgenden vier:



der kürzeste Weg mit Ausfahrt am Nord-Ende von Gasse \(\text{G}_{\text{i(j-1)}}\), ergänzt um

  • entweder

    • den Weg von dort zum Nord-Ende von \(\text{G}_{\text{i(j)}}\) (Einfahrt),
    • picken in \(\text{G}_{\text{i(j)}}\), wenden und dann
    • Ausfahrt am Nord-Ende (Typ NNN)

  • oder

    • den Weg von dort zum Süd-Ende von \(\text{G}_{\text{i(j)}}\) (Einfahrt),
    • picken in \(\text{G}_{\text{i(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 \(\text{G}_{\text{i(j-1)}}\), ergänzt um

  • entweder

    • den Weg von dort zum Süd-Ende von \(\text{G}_{\text{i(j)}}\) (Einfahrt),
    • picken in \(\text{G}_{\text{i(j)}}\), durchfahren und dann
    • Ausfahrt am Nord-Ende (Typ SSN)

  • oder

    • den Weg von dort zum Nord-Ende von \(\text{G}_{\text{i(j)}}\) (Einfahrt),
    • picken in \(\text{G}_{\text{i(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 \(\text{G}_{\text{i(j)}}\).

zweites Problem der Größe j

Analoges gilt für den kürzesten Weg mit Ausfahrt am Süd-Ende von Gasse \(\text{G}_{\text{i(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.