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 {v₁,...,v_n}.
-Distances d(i,j) for each pair (v_i,v_j) 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 d₁,d₂,d₃ in the graph: d₁ <= (d₂+d₃)

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