# Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think that these algorithms are more time consuming since the evaluation complexity is not constant (assuming my calculations are correct).

What are some good alternative that are less time consuming? are their any technique swapping nodes for example? Could you suggest a good paper about such algorithms?

• TSP or ATSP? I think you mean TSP but in title you wrote ATSP. – Saeed Feb 24 '15 at 23:12
• @Saeed I mean ATSP (Asymmetric TSP) – yafrani Feb 25 '15 at 10:35
• But in your question you wrote TSP, also Lin-Kernighan is for TSP not ATSP, and furthermore there is no known 2 approximation for ATSP. – Saeed Feb 25 '15 at 11:38
• @Saeed LKH = Lin-Kernighan heuristic. This is an implementation of LK. All the heuristics OP mentions have been considered for ATSP, maybe slightly modified. LK has no provable guarantees for symmetric TSP either AFAIK, so I am confused what your complaint is specifically wrt ATSP? – Sasho Nikolov Feb 25 '15 at 16:46
• @Saeed it's not clear to me at least. Are you saying that $k$-opt cannot be adapted to ATSP, or that you doubt it will work as well, or something else? $k$-opt is simply the local search algorithm whose moves are all valid switches of three edges: it works the same way for atsp, but of course what's a "valid switch" depends on the directions. LK is admittedly more tricky to adapt, but it has been done. However, after a second look, the LKH people seem to reduce ATSP to TSP. The reduction is not apx-preserving, but they don't prove approximations anyways. – Sasho Nikolov Feb 26 '15 at 2:33

Best one I know is the polytime approximation algorithm of Asadpour et al., although maybe this isn't what you want (i.e. you want exact solution, I'm guessing). Anyway, the algorithm achieves $O(\log n / \log \log n)$ approximation for $n$-vertex graphs.