ISSN:
1436-5057
Keywords:
90C27
;
90C35
;
15A57
;
05C45
;
Traveling salesman problem
;
subtour patching
;
Monge matrix
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Es sieA=(a ij ) die Entfernungsmatrix eines (asymmetrischen) Rundreiseproblems und τ=τ1τ2...τ m die Optimallösung des zugehörigen Zuordnungsproblems mit den Teilzyklen τ=τ1τ2...τ m . Wählt man (m−1) Transpositionen (k, l) mitk ∈ τ i−1,l ∈ τ i (i=2, ...,m) und verknüpft man die Teilzyklen unter Zuhilfenahme dieser Transpositionen in beliebiger Ordnung, so erhält man eine Menge zyklischer Permutationen. Es wird gezeigt, daß man die kürzeste Tour in dieser Menge von Rundreisen mit einem Rechenaufwand von O(n 2|τ|* Operationen bestimmen kann, wobei |τ|* die maximale Anzahl von Städten in einem Teilzyklus von τ ist. Im Falle, daß die EntfernungsmatrixA=(a ij ) eine permutierte Verteilungsmatrix (Monge-Matrix) und der VerknüpfungsgraphG τ ein mehrfacher Weg ist, kann ein Resultat von Gaikov verbessert werden. In Verbindung mit einem Resultat von Park führt die oben entwickelte Theorie in diesem Fall zu einemlinearen Verfahren zur Bestimmung einer optimalen Rundreise.
Notes:
Abstract LetA=(a ij ) be the distance matrix of an arbitrary (asymmetric) traveling salesman problem and let τ=τ1τ2...τ m be the optimal solution of the corresponding assignment problem with the subtours τ=τ1τ2...τ m . By choosing (m−1) transpositions (k, l) withk ∈ τ i−1,l ∈ τ i (i=2, ...,m) and patching the subtours by using these transpositions in any order, we get a set of cyclic permutations. It will be shown that within this set of cyclic permutations a tour with minimum distance can be found by O(n 2|τ|* operations, where |τ|* is the maximum number of nodes in a subtour of τ. Moreover, applying this result to the case whenA=(a ij ) is a permuted distribution matrix (Monge-matrix) and thepatching graph G τ is a multipath, a result of Gaikov can be improved: By combining the above theory with a result of Park alinear algorithm for finding an optimal TSP solution can be derived, provided τ is already known.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02253612
Permalink
