The Geometric Travelling Salesman Problem


Description:The Geometric Travelling Salesman Problem is a classified NPhard optimization problem. It can be defined as: Input: Output: 

QuestionGiven a set of points representing cities over a map like a Graph (where each point is a vertex), find the graph's hamiltonian cycle associated with minimum length of the tour, where the distance between vertexs is the discretized Euclidean length shown below:
Although, not required by the formulation, we will restrict our TSP into problems in which the the triangle'distance inequality is satisfied:
A hamiltonian cycle of a connected graph is a path that visits all the vertexs in the graph, without repeating any of them, and finishing in the same vertex which we started the cycle. 

Problem InstancesIn order to define an instance of this problem we need to provide the set of cities, where foreach city we must indicate the (X,Y) coordinates over the map. 

Related Bibliography and Papers


Last Updated: 6/06/03 For any question or suggestion, click here to contact with us. 