| Summary: | The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are <i>k</i> salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances.
|
|---|