In this paper we analyze the efficiency of three TSP solver methods: the best-performing exact Concorde algorithm, the state-of-the-art inexact Helsgaun’s Lin–Kernighan heuristic and our Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA). In our analysis the run time predictability was also taken into account, not only the tour quality and the run time properties. Three models (polynomial, exponential, square-root exponential) were fitted to the mean run times of VLSI (Very-large-scale integration) instances up to 20,000 nodes. The DBMEA produces the highest (close to 1) R²-values for each model. The Concorde algorithm shows very low run time predictability.