Rundreiseproblem

Gegeben sind n Orte . Um von O_i nach O_j zu gelangen, muß ein Reisender die Entfernung c_ij zurücklegen. Dabei kann möglich sein.
Es ist eine kürzeste Reiseroute so zu wählen, daß ein Reisender jeden Ort genau einmal besucht und am Ende zum Ausgangsort zurückkehrt.

Wie beim Zuordnungsproblem ist wiederum in jeder Zeile und jeder Spalte der Entfernungsmatrix genau ein Element auszuwählen, so daß die Gesamtsumme der ausgewählten Elemente minimal wird. Allerdings wird die numerische Lösung des Rundreiseproblems beträchtlich durch die Einschränkung erschwert, daß eine Anordnung der markierten Elemente c_ij in folgender Form möglich sein muß:

Das Rundreiseproblem kann durch die Anwendung von Verzweigungsverfahren (branch and bound) gelöst werden.