# 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. Commented Feb 24, 2015 at 23:12
• @Saeed I mean ATSP (Asymmetric TSP) Commented Feb 25, 2015 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. Commented Feb 25, 2015 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? Commented Feb 25, 2015 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. Commented Feb 26, 2015 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.