As that article says, approximate classical algorithms "can find solutions for extremely large problems (millions of cities) within a reasonable time which are

As that article says, approximate classical algorithms "can find solutions for extremely large problems (millions of cities) within a reasonable time which are with a high probability just 2–3% away from the optimal solution." Although faster quantum algorithms for the exact solution exist, I see no reason why this would result in "vastly" improved efficiency.