An original approach to the well-known Travelling Salesman Problem

Since its first approaches in the nineteenth century, scholars have paid extensive attention to the Travelling Salesman Problem (TSP); likely due to the confluence of a simple definition, a variety of practical applications, and high computational complexity.

The classic definition of the TSP can be stated as follows: Find the shortest route (tour) for a salesman starting from a given city, visiting each of a specified group of cities, and then returning to the original point of departure (Dantzig et al. 1954).

Besides the immediate application to logistics, the original formulation or through slight variations, the TSP has been used in scheduling, material cutting, semiconductor manufacturing, crystallography or DNA sequencing.

Early mathematical analysis stated its high computational complexity. It belongs to the so-called NP-complete (nondeterministic polynomial-time complete) problem class, which encompasses the hardest computational problems to tackle.

Under the framework of a research Project preceding the current DIGEST Project, Herráiz, Gutierrez and Ortega-Mier (2022) proposed an original geometric transformation of the problem.  As shown in the figure (extracted from the paper), the idea is based on the construction of an inscribed n-polygon such that the lengths of the edges are equal to the corresponding TSP tour links and follow the same sequence order.

Example of a TSP tour geometric transformation (taken from Herráiz et al., 2022)

This transformation leads to a modified formulation for the Euclidean TSP in which the objective function is expressed as a summation of angles instead of distances. This modification opens the way to identifying characterizing geometric parameters of the TSP as well as to explore new heuristics based on the inclusion of additional constraints. The experimentation with a set of cases shows promising results compared to the traditional compact formulations for randomly or evenly distributed nodes.