An example of a salesperson with a known global optimal

Question

I made a memetic algorithm in Python for the traveling salesman problem . However, all the test data (list of distances between cities) that I came across do not have information about the best solution, so I can’t know how close to the global optimal algorithm.

Does anyone know where I can find some tsp test data (preferably in matrix form, but nothing good) with a known better solution?

Answer 1

Are you google

http://www.tsp.gatech.edu/data/index.html

This page contains several test cases, of which 16 have an optimal solution.

Answer 2

Perhaps you can create your own test data?

This will definitely not be exhaustive testing, but it can help. Note: The Hamiltonian path is shown below, and if you are looking for loops something like this will work.

You can do the following:

Say you are given an undirected graph G with n nodes.

Now you create a weighted graph G 'by setting the weight of the edges in G to 1 and adding edges not to G and giving them a random weight> 1, i.e. G 'is a complete graph with weights assigned to all its edges.

Now, if you run the current TSP algorithm on G 'and generate a path of size n-1, then G has a Hamiltonian trajectory. Otherwise, G does not have a Hamiltonian trajectory.

So, now you can use graphs you know that have / don't have Hamiltonian paths (for example: Hypercube has Hamiltonian paths) and generate test data for your TSP algorithm.

This page has some sufficient conditions that may be useful when creating graphs that have Hamiltonian paths: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

I believe you will not be able to find data on graphs with / without Hamiltonian paths.

Hope this helps. Good luck

Answer 3

TSPLIB is a library of sample instances for TSP (and related problems) from various sources and various types.

http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/