Tourenplanugs-Verfahren (B&B)

Wissenschaft Informatik
#1

Hallo zusammen,

ich schreibe gerade eine Abschlussarbeit über den Einsatz von Tourenplanungstools in einem Logistikunternehmen. Im Theorie-Teil hänge ich gerade etwas, weil sich die Literatur widerspricht.

Das Branch & Bound Verfahren wird einerseits als exaktes Lösungsverfahren, andererseits als Heuristik bezeichnet.

Wie kann ich dies am ehesten einordnen?
Ziel der Geschichte ist nur eine Übersicht über verschiedene Lösungsverfahren und deren Kategorisierung. Aber gerade B&B scheint mein betreuender Prof. ganz gut zu kennen und dann wäre ein Ausrutscher peinlich.

THx for Help!

#2

Moien

ich schreibe gerade eine Abschlussarbeit über den Einsatz von
Tourenplanungstools in einem Logistikunternehmen. Im
Theorie-Teil hänge ich gerade etwas, weil sich die Literatur
widerspricht.

Die Theorie dürfte doch auf TSP (Traveling Salesman Problem) rauslaufen, oder ?

Das Branch & Bound Verfahren wird einerseits als exaktes
Lösungsverfahren, andererseits als Heuristik bezeichnet.

B&B rät an gewissen Stellen, ist also heuristisch.

Die Reihenfolge in der mögliche Branches ausgewertet werden ist nicht zufällig, sondern man nimmt den Teil mit den besten Chancen zuerst (also nachdem man die Teile ohne Chance weggeschmissen hat). Die besten Chancen führen aber nicht zwangsläufig zum besten Resultat, die Entscheidung war also nicht unbedingt richtig. (Aus Sicht der Laufzeit, nicht aus Sicht des Resultates, falsche Entscheidungen werde ja später ausgebügelt)

Trotzdem kommt immer das beste Resultat raus, die Optimierung führt also zur besten Lösung. Der heuristische Teil beeinflusst nur die Geschwindigkeit des Algo, nicht aber seine Korrektheit.

cu

#3

ich schreibe gerade eine Abschlussarbeit über den Einsatz von
Tourenplanungstools in einem Logistikunternehmen. Im
Theorie-Teil hänge ich gerade etwas, weil sich die Literatur
widerspricht.

Die Theorie dürfte doch auf TSP (Traveling Salesman Problem)
rauslaufen, oder ?

rrrichtig!

Das Branch & Bound Verfahren wird einerseits als exaktes
Lösungsverfahren, andererseits als Heuristik bezeichnet.

B&B rät an gewissen Stellen, ist also heuristisch.

eben so was hab ich gelesen und mir dann gedacht, dass meine Einordnung unter exakten Verfahren aus Buch X doch Schwachsinn ist…
Danke!

#4

Moien

B&B rät an gewissen Stellen, ist also heuristisch.

eben so was hab ich gelesen und mir dann gedacht, dass meine
Einordnung unter exakten Verfahren aus Buch X doch Schwachsinn
ist…

Naja, er ist auch exakt, denn er liefert (irgendwann) das exakte Resultat. Er ist auch deterministisch, denn jeder Durchlauf erzeugt die gleiche Sequenz von Tests/Auswertungen.

Es hängt also von deiner Definition von Exakt ab …

(An sich ist das Ding eine Abart von Dynamischer Programmierung angewendet auf klassiches, O(2^n) TSP lösen)

cu