Das Traveling Salesman Problem mit Permutierten Verteilungsmatrizen und Quasi-2-Konvexität

Betrachtet wird das Traveling Salesman Problem (TSP; Rundreiseproblem) von einer speziellen Klasse von Matrizen, den sogenannten permutierten Verteilungsmatrizen. C = [c_ij] wird Verteilungsmatrix genannt, wenn für alle i<p, j<q: c_ij + c_pq ≤ c_iq + c_pj, (i,j = 1,…,m) gilt. C erfüllt die sogenannte “Monge”-Bedingung. C wird permutierte Verteilungsmatrix genannt, wenn eine Permutation p so existiert, daß Cp = [c_ip<j<] eine Verteilungsmatrix ist. Die zulässige Lösungsmenge des TSP wird in einen Graphen (Strukturgraphen) so eingebettet, daß die Zielfunktion die Eigenschaft der Quasi-2-Ronvexität hat. Auf Grund der so eingeführten Struktur können effiziente (polynomiale) Lösungsmöglichkeiten für zugrundegelegte spezielle Problemklassen abgeleitet werden. Abschließend wird die Klasse der symmetrischen Produktmatrizen betrachtet, bei denen c_ij = a_i.b_j gilt.