A Comparative Study on Algorithms for Solving Generalized Traveling Salesman Problem

The Generalized Traveling Salesman problem (GTSP) is an expansion of classical well-known Traveling Salesman problem. In Generalized Traveling Salesman Problem towns (represented as vertices) are divided on groups (clusters). The main goal is to find route with minimal weight, which traverse each cluster exactly once. It should be mentioned, that the above-defined problem is a classic version of GTSP. There are different variants of the problem, where each city can belong to different clusters; the route can pass through several cities in the cluster; several traveling salesmen can be specified, for each of which it is needed to find the route and etc. For the classical version of GTSP there are several approaches to solving the problems: the transformation of the original problem into another routing problem; reduction algorithms; exact and heuristic algorithms. The main goal of work is studying the GTSP, investigating time and accuracy characteristics of different approaches to solving GTSP. The tasks of the work are: ⎼ Study of different variants of GTSP; ⎼ Study of different approaches to solving GTSP; ⎼ Study of time and accuracy characteristics of algorithms for transformation the original problem into related routing problems, reduction algorithms and heuristic algorithms. As a result of this work, a new algorithm CM-Search for non-exact transformation was proposed. Its algorithm allows to obtain, on average, an error rate 7.6% from the optimal in solving the transformed problem by the GLKH algorithm. As shown by the experiments, the GLKH algorithm is a leader among heuristic algorithms and is able to solve the problem with an error rate from the optimal in average of 0% (on tested dataset).