I want to solve the Asymmetric TSP for a large-scale problem for an industrial application where the company cannot buy a commercial software license. For their applications, it is very important to find good solutions within a short computation time. What are the main algorithms (either approximation, randomized, heuristic, dynamic programming, etc.) that are able to find good solutions as fast as possible? And, the same problem arises for the vehicle routing problem.
Although metaheuristic algorithms are powerful algorithms, they are not guaranteed to find good solutions and they may converge to different solutions in each replication of the algorithm.