Das bipartite Travelling-Salesman-Problem


Leitung: Prof. Dr. A. Srivastav
Mitarbeiter: Dr. Andreas Baltz, Dr. Tomasz Schoen, Sören Werth

Aufgabe:

Finde ein effizientes Verfahren zur Konstruktion einer möglichst kurzen Rundtour durch n rote und n blaue Punkte, die abwechselnd besucht werden müssen.

Anwendung: Pick&Place-Roboter und automatische Bestückung von Leiterplatinen (Tour alterniert zwischen Bauelementen und Positionen auf der Platine)

Wir untersuchen:

  • Effiziente Approximationsalgorithmen für Instanzen in der euklidischen Ebene,
  • die typische Tourlängen zufälliger, asymmetrischer Instanzen.

    • Effiziente Approximationsalgorithmen

    a) Die B2-Baum-Strategie

  • Berechne gradbeschränkten minimalspannenden Baum, in dem jeder rote Knoten höchstens zwei Nachbarn hat.


  • Verdopple Kanten und durchlaufe Baum mittels Tiefensuche.


  • Erhalte bipartite TSP-Tour durch Abkürzungstechnik.
    		•

    Experimentell:

  • Implementierung mit Matroid-Schnitt-Algorithmus hat hohe Laufzeit.
  • Tourlänge liegt im Mittel nur wenige Prozent über optimaler Tourlänge, OPT.


    • Theoretische Analyse:
  • Tour der Länge $\le 2\cdot$OPT läßt sich in Zeit $c\cdot n^7$ berechnen.
  • Es gibt Beispiele, für die diese Güteabschätzung scharf ist.

    • b) Die Matching-Methode

  • Bestimme Tour durch blaue Punkte mit Approximationsschema von Arora.


  • Füge perfektes Matching minimaler Gesamtlänge zwischen roten und blauen Punkten in Arora-Tour ein.
    		•

    Experimentell:

  • Implementierungen mit sehr geringen Laufzeit durch Austausch-Heuristiken und LP-Formulierung des Matchingproblems
  • Tourlänge ist deutlich kürzer als B2-Tour


    • Theoretische Analyse:
  • Tour der Länge $\le(2+\varepsilon) \cdot$OPT benötigt Laufzeit $C_\varepsilon+c\cdot n^3$, wobei $C_\varepsilon \to\infty$ für $\varepsilon\to 0$.
  • Für bestimmte Punktkonfigurationen wird $(2+\varepsilon)\cdot$OPT-Schranke angenommen.

    • c) Das Kreiszerlegungsverfahren

  • Bestimme eine optimale Kreiszerlegung mittels linearer Programmierung oder durch einen kombinatorischen 2-Matching-Algorithmus.


  • Konstruiere Tour durch sukzessives Verbinden von Kreisen mit kürzestem Abstand.
    		•
    Experimentell:
  • LP-Formulierung erlaubt Implementierungen mit geringer Laufzeit.
  • Abweichung der Tourlänge vom Optimum ist im Mittel halb so groß wie bei Matching-Methode


    • Theoretische Analyse:
  • Tour der Länge $\le 3\cdot$OPT benötigt Laufzeit $c\cdot n^3\cdot\ln n$
  • Schranke $3\cdot$OPT kann erreicht werden

    • Asymmetrisches Bipartites TSP

    Frieze, Karp und Reed zeigen:
  • Für TSP-Instanzen mit zufälligen Distanzmatrizen M, deren Anzahl von Nulleinträgen mit n gegen unendlich geht, stimmen die Längen von optimaler Kreiszerlegung, AP(M), und optimaler TSP-Tour, ATSP(M), überein.

    Dieses Resultat lässt sich für den bipartite Fall verallgemeinern.

    Frieze und Sorkin beweisen:
  • Für zufällige Distanzmatrizen $M$ gilt ATSP(M)-AP(M) $\le c_1\frac {(\ln n)^2}{n}$ und $\mathbbm{E}[\mbox{ATSP}(M)-\mbox{AP}(M)]\ge\frac{c_0}{n}$.

    • Offene Fragen

  • Gibt es ein effizientes Verfahren, um Touren zu finden, die kürzer sind als das doppelte der optimalen Tourläge?
  • Was sind obere und untere Schranken für ATSP(M)-AP(M) im bipartiten Fall?
    • Literatur
  • A. Baltz, T. Schoen, A. Srivastav; On the b-partite Random Asymmetric Traveling Salesman Problem and its Assignment Relaxation. Preprint, 2001.
  • A. Baltz, A. Srivastav; Approximation Algorithms for the Euclidean Bipartite TSP. Preprint, 2001.
  • A. Frieze, M. Karp, B. Reed; When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? SIAM Journal on Computing 24 (1995), 484-493.
  • A. Frieze, G.B. Sorkin; The probabilistic relationship between the assignment and asymmetric traveling salesman problems. Proceedings of SODA 2001, 652-660.
    • Weitere Informationen: TSP home page