There is a good chance that the failure mode of the algorithm is to yield an invalid solution, not a suboptimal one, so in that case you do not even need to know the optimal solution. Besides that you are not going to find a counter example by generating random instances, you will be carefully constructing it with spacial properties to make the algorithm fail. Because of the special structure you might just be able to figure out the optimal solution in your head. And I would guess that you can construct a counter example with ten or so cities and you can easily brute force a few million or billion paths. If you need twenty cities however, things look already different but there are solvers that should still easily deal with those cases.