Maximum Traveling Salesman Problem by Adapted Neural Gas

This paper considers the problem of solving the Maximum Traveling Salesman Problem (otherwise known as “taxicab ripoff problem”) in a plane, using an adapted Neural Gas algorithm with some features of Kohonen’s Self-Organizing Map. Maximum Traveling Salesman Problem is similar to classical Traveling Salesmen Problem (TSP), but instead of a search for a Hamiltonian tour visiting all vertices and returning to the initial vertex, which has a minimum sum of lengths of visited edges, we are looking for a maximum sum of lengths. This problem is less popular than classical TSP, nevertheless, in recent years also received a great amount of attention, leading to many heuristics and theoretical results. In this paper, we propose a new heuristic, which is certainly not as efficient as the already existing methods. We are not trying to enter the fierce competition to find the most effective algorithm, but we are trying to experimentally examine a possibility to use a special type of neural network to solve such a problem. Experiments show, that elements of neural gas approach together with SOM are applicable to this kind of problem and provide reasonable results.