Hello.
I made a memetic algorithm in Python for traveling salesman problem. However, all the test data (list of distances between cities) I've encountered lack the information of the best solution, so I can't know how close to global optimum my algorithm gets.
Does anyone know where I can find some tsp test data (preferably in matrix form, but anything's good) with known best solution?
Did you google?
http://www.tsp.gatech.edu/data/index.html
That page provides several test-cases of which 16 has an optimal solution.
Perhaps you can generate your own test data?
This definitely won't be comprehensive testing, but it might help. Note: the below is about hamiltonian path, and if you are looking for cycles, something similar will work.
You can do the following:
Say you are given an undirected graph G with n nodes.
You now create a weighted graph G', by setting the weight of edges in G to be 1, and adding the edges not in 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 a valid TSP algorithm on G' and it generates a path of size n-1, then G has a hamiltonian path. Otherwise G does not have a hamiltonian path.
So now you can use graphs you know that have/don't have hamiltonian paths (for e.g: Hypercube has hamiltonian paths) and generate test data for your TSP algorithm.
This page has some sufficient conditions which might prove useful in generating graphs which have hamiltonian paths: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
I suppose you won't have a hard time finding data on graphs with/without hamiltonian paths.
Hope it helps. Good luck!
TSPLIB is a library of sample instances for the TSP (and related problems) from various sources and of various types.