# The Geometric Travelling Salesman Problem ## Description:

The Geometric Travelling Salesman Problem is a classified NP-hard optimization problem. It can be defined as:

Input:
-Set C of m cities {v1,...,vn}.
-Distances d(i,j) for each pair (vi,vj) of C.

Output:
-Hamiltonian cycle for C.

## Question

Given 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:

 Distance between v1:(x1,y1) and v2:(x2,y2) = Although, not required by the formulation, we will restrict our TSP into problems in which the the triangle'distance inequality is satisfied: For all d1,d2,d3 in the graph: d1 <= (d2+d3)

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 Instances

In 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

 TextBook Computers and Intractability: A Guide to the Theory of Np-Completeness by Michael R. Garey, David S. Johnson TextBook How to Solve It: Modern Heuristics by Zbigniew Michalewicz, David B. Fogel URL The TSPBIB Home Page http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html URL OR LIBRARY - J.E. Beasley http://mscmga.ms.ic.ac.uk/jeb/orlib/tspinfo.html URL DIMACS TSP Challenge http://www.research.att.com/~dsj/chtsp/ URL Solving Travelling Salesman Problems http://www.math.princeton.edu/tsp/ URL A compendium of NP optimization problems http://www.nada.kth.se/~viggo/problemlist/compendium.html Last Updated: 6/06/03                                                                                                                  For any question or suggestion, click here to contact with us.