The Traveling Salesman Problem on the Hyperbolic Plane

This paper is concerned with the traveling salesman problem (TSP) on the two-dimensional hyperbolic space. We provide an efficient heuristic to find near optimal tour along the cities, where the distance measure is the hyperbolic distance between the points (cities) placed randomly and uniformly on a hyperbolic disk. Our approach is mainly experimental, that is for a large number instances of points randomly generated on hyperbolic disks with different size are performed and statistics on our TSP heuristic are provided and compared to the results of standard TSP solvers. Nevertheless, we also show analytical approximations on the expected tour length in our heuristic solution of the TSP. We also perform an application possibility of our TSP solution for designing optimal address space of hop-by-hop routing in hyperbolic complex networks.