Meta-heuristics usually lack any kind of performance guarantee and therefore one cannot be certain whether the resulting solutions
are (near) optimum solutions or not without relying on additional algorithms for providing lower bounds (in case of minimization).
In this paper, we present a highly effective hybrid evolutionary local search algorithm based on the iterated Lin-Kernighan
heuristic combined with a lower bound heuristic utilizing 1-trees. Since both upper and lower bounds are improved over time,
the gap between the two bounds is minimized by means of effective heuristics. In experiments, we show that the proposed approach
is capable of finding short tours with a gap of 0.8% or less for TSP instances up to 10 million cities. Hence, to the best
of our knowledge, we present the first evolutionary algorithm and meta-heuristic in general that delivers provably good solutions
and is highly scalable with the problem size. We show that our approach outperforms all existing heuristics for very large
TSP instances.