TSP mit Start- und Zielknoten lösen

Wissenschaft Informatik
#1

Hallo Leute,

ich suche einen Lösungsansatz für das Traveling Salesman Problem unter folgender Zusatzbedingung: Sämtliche Knoten sind entweder Start- oder Zielknoten. Während Startknoten immer angefahren werden können, dürfen Zielknoten erst angefahren werden, wenn der zugeordnete Startknoten VORHER angefahren wurde. Ansonsten handelt es sich um ein symmetrisches und metrisches TSP. Die analytisch optimale Lösung muss nicht gefunden werden, es reicht eine Näherung.

Mein Ansatz war folgender:

  1. Optimiere die Menge der Startknoten über den MST Algorithmus
  2. Damit ist der erste Knoten gesetzt
  3. Optimiere die Menge der verbleibenden Startknoten und den ersten Zielknoten (MST)
  4. Damit ist der zweite anzufahrende Knoten gesetzt
  5. Wiederhole 3. und 4. bis nur noch ein Knoten übrig ist

Nach etwas überlegen scheint mir dieser Ansatz allerdings dazu zu führen, dass zwar Zielknoten erst angefahren werden, wenn ihre Startknoten angefahren wurden, allerdings wird einfach immer nur der nächstgelegene gültige Knoten angefahren. Das ist natürlich nicht besonders optimiert… Hat jemand Vorschläge?

Danke,
Daniel

#2

Ich frage mich, wie die identifizierten Startknoten nachher wieder mit der in der nächsten Runde ohne sie ermittelten Tour verbunden werden.

Die Distanzen des aus der Menge genommenen Knotens fallen komplett aus der Optimierung und die Resttour kann an einer völlig anderen Stelle beginnen, zu deren beiden Enden große Distanzen zu überbrücken wären.

Ciao, Allesquatsch

#3

Hallo,

würde zu einem Evolutionären Algorithmus greifen, dort lassen sich zusätzliche Nebenbedingungen leicht einbauen.

Ansatz: Die Städte werden als Permutation p verwaltet, d.h die Städte werden in dieser Reihenfolge besucht.

Definition einer Fitness-Funktion f§ = Länge der Strecke + (Anzahl der verletzten Start-Ziel Bedingunen) * C.
C ist ein großer Wert, z.B. Summe aller Kanten.

  1. Initalisierung mit einer Zufälligen Permutation p (oder mittels MST)
  2. Mutation von p: man erhält p2 durch eine der folgenden Operationen:
    2a. Wähle zwei Städte zufällig und invertiere die Permation zwischen beiden Städten
    2b. Wähle eine verletze Start-Ziel Bedingung und vertausche beide Städte
    2c. …
  3. Selektion: Wenn f(p2) besser als f§ dann p = p2
  4. Goto 2, Abbruch wenn 1000 mal keine verbesserung (oder ähnlich)

Für eine effiziente Implementierung ist es wichtig, die Funktion f so zu implementieren, das in konstanter Zeit f(p2) aus f§ berechnet wird.

Viele Grüße
McGee

#4

Ansatz: Die Städte werden als Permutation p verwaltet, d.h die
Städte werden in dieser Reihenfolge besucht.
2. Mutation von p: man erhält p2 durch eine der folgenden
Operationen:
2a. Wähle zwei Städte zufällig und invertiere die Permation
zwischen beiden Städten
2b. Wähle eine verletze Start-Ziel Bedingung und vertausche
beide Städte
2c. …

Hallo,

diesen Schritt kann man bzgl. Performance verbessern, indem man ihn vor die Schleife zieht; ich würde topologisch sortieren, also Schubladen bilden, so dass Zielknoten in spätere Schubladen als ihre Startknoten kommen und dann nur innerhalb der Schubladen permutieren, so entstehen nur „gültige“ Permutationen.

Grüße, guidot