부산대학교 도서관

We define a geometric transformation of Euclidean Travelling Salesman Problem (TSP) tours that leads to a new formulation of the TSP. For every Euclidean TSP n-city tour, it is possible to construct an inscribed n-polygon (Equivalent Cyclic Polygon, ECP) such that the lengths of the edges are equal to the corresponding TSP tour links and follow the same sequence order. The analysis of the ECP elicits the possibility of defining a new objective function in terms of angles instead of distances. This modification opens the way to identify 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. The behavior of the ECP-based TSP formulations is better when the nodes of the TSP are randomly or evenly distributed.
Author(s): A. Herraiz [sup.1] , M. Gutierrez [sup.1] , M. Ortega-Mier [sup.1] Author Affiliations: (1) grid.5690.a, 0000 0001 2151 2978, Ingeniería de Organización, Administración de Empresas y Estadística, Escuela Técnica [...]