mariabauza and I are trying to do the Travelling Salesman Problem in a segment graph (for a real life application, it's not a CP problem): you are given 10-100 segments in the plane you have to color (go through), give the shortest path to color them all.
For example, here are 2 possible paths (in red) for the same segments, one shorter than the other.
To do it we use the 2-opt algorithm we learned in Petr's blog. There he explains that the 2-opt algorithm works very well, finding the best solution in very few tries. However, with only those 5 (random) segments it only finds the optimal solution 26% of the time after 400 restarts (finding only local minimums during 400 tries, 74% of the time).
Do you think the algorithm may not be as effective for the fact we are now dealing with segments and not points? Or are you sure the algorithm should work almost perfectly and we must have some bug? (We have looked our code thoroughly before posting here, but you never know) Can it be slightly modified to work better in this kind of graph?
Finally, we know that we can develop TSP algorithms for Euclidean graphs, but the only one we know (using the MST) doesn't quite apply when dealing with segments. Do you know/can you come up with any other algorithm that could help?
Thanks!
Full text and comments »