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?
You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities).

http://www.sciencedirect.com/science/article/pii/0167637783900482
http://www.sciencedirect.com/science/article/pii/0167637786900817