This paper presents a Discrete Bacterial Memetic Evolutionary Algorithm (DBMEA) for the Traveling Salesman Problem. This algorithm combines the very efficient bacterial evolutionary algorithm with 2-opt and 3-opt local searches. Our approach was tested on TSPLIB and other VLSI benchmark problems. In this paper our computational results (minimal tour lengths, run times) are compared with other efficient TSP solver algorithms (Lin-Kernighan, Concorde). We will show that in significant number of the published benchmark problems the optimal tour was not found by the Concorde algorithm and the Lin-Kernighan heuristic because this approaches use an approximation substituting distances of points by the closest integer values. We suggest the substitution of the benchmark result set by the real optima calculated by the new DBMEA algorithm and the use of DBMEA heuristic as more precise for the solution of TSP and other NP-hard optimization problems.