Forschungsinstitut für Diskrete Mathematik

Thema: Das Handlungsreisendenproblem

Das Traveling Salesman Problem (TSP) ist eines der zentralen kombinatorischen Optimierungsprobleme. Gegeben ist eine Menge von Knoten (die z.B. als Städte interpretiert werden können) mit einer Distanz zwischen jedem Knotenpaar. Gesucht ist eine Tour minimaler Länge, die jeden Knoten genau einmal besucht und dann wieder zum ersten Knoten zurückkehrt. Anwendungen hat das TSP als Teilproblem z.B. in der Logistik, dem Chipdesign und der DNA-Sequenzierung. Das TSP ist NP-schwer, und polynomielle Algorithmen, die das Problem exakt lösen, sind nicht bekannt. In diesem Praktikum sollen verschiedene Algorithmen implementiert werden, die das Problem (auf kleinen Instanzen) exakt, approximativ oder heuristisch lösen.

Einen ersten Überblick über das TSP und einige der Algorithmen finden Sie in Kapitel 21 aus "B. Korte, J. Vygen : Combinatorial Optimization: Theory and Algorithms. Springer, Vierte Auflage 2008".

Testinstanzen