Q. What is the smallest number of cities for which it will search all possible routes in a reasonable time?
(Technically we are not sure it searches all n possible different routes.
All we can say is it does n evolutionary tests.
But that shows how a systematic algorithm could search all n routes in the same time.)
Change the code to do random search and see how it does.
Change the code to exhaustively (systematically) search where possible.