The 25 city solution is <0-4-3-9-5-7-1-2-6-8-0>, length 1491.

At a computation speed of 50 routes per second, the Naíve algorithm would take (24!)/2/50 seconds = 2 x 10¹⁴ years, or 13000 universe lifetimes. The computer may be sped up through parallel processing, perhaps by a factor of 1 million, reducing the time to 2 million years!

Running the Naíve algorithm on my 2GHz Pentium 4 yielded a solution of length:
4980 after 2 minutes
4589 after 5 minutes
4589 after 10 minutes
4589 after 30 minutes
4589 after 60 minutes

Running the Monte Carlo greedy algorithm on the same machine yields:
1 minutes yielded a solution of length 3090
2 minutes yielded a solution of length 3066
3 minutes yielded a solution of length 3022
10 minutes yielded a solution of length 3006