<p>You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities).</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/0167637783900482" rel="nofollow">http://www.sciencedirect.com/science/article/pii/0167637783900482</a>
<a href="http://www.sciencedirect.com/science/article/pii/0167637786900817" rel="nofollow">http://www.sciencedirect.com/science/article/pii/0167637786900817</a></p>

CC BY-SA 3.0
2015-11-30T23:21:45.450Z
2015-11-30T23:21:45.450Z
Edward Kirton
<p>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 <a href="http://homes.cs.washington.edu/~shayan/atsp.pdf" rel="nofollow">algorithm</a> achieves $O(\log n / \log \log n)$ approximation for $n$-vertex graphs. </p>

CC BY-SA 3.0
2015-02-24T22:06:41.383Z
hardly a local search algorithm
Sasho Nikolov
CC BY-SA 3.0
2015-02-24T19:31:32.880Z
2015-03-27T22:08:33.817Z
2015-03-27T22:08:33.817Z
wyas
<p>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).</p>

<p>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?</p>

CC BY-SA 3.0
2015-02-24T23:12:26.967Z
TSP or ATSP? I think you mean TSP but in title you wrote ATSP.
Saeed
CC BY-SA 3.0
2015-02-25T10:35:56.980Z
@Saeed I mean ATSP (Asymmetric TSP)
yafrani
CC BY-SA 3.0
2015-02-25T11:38:32.130Z
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
CC BY-SA 3.0
2015-02-25T11:50:42.673Z
@Saeed I wrote ATSP, and LK works fine for ATSP: http://www.akira.ruc.dk/~keld/research/LKH/Soler_results.html
yafrani
CC BY-SA 3.0
2015-02-25T12:51:15.747Z
Actually I confused by this sentence "I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations)", I think 2-opt is [this](http://en.wikipedia.org/wiki/2-opt) which is for TSP not ATSP, I don't know how they can adopt it for ATSP to get reasonable result, e.g in the link you provided it is LKH algorithm not LK which is variation of LK as authors wrote. Also even in that case maybe inputs are not just euclidean, e.g largest weight is also 12000 as written and they may have more restriction that makes it possible to apply some tricks. (I was not able to open input files).
Saeed
CC BY-SA 3.0
2015-02-25T16:46:16.760Z
@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
CC BY-SA 3.0
2015-02-26T02:12:01.150Z
@SashoNikolov, first I wrote a comment as a response to your comment, but then I thought my previous comment was clear enough in my opinion. So I cannot elaborate it more.
Saeed
CC BY-SA 3.0
2015-02-26T02:33:00.743Z
@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
<optimization><tsp><heuristics>
Good algorithms to solve ATSP
yafrani
# Good algorithms to solve ATSP

(Asked by: username_0 on 2015-02-24)

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?

**Tags:** optimization, tsp, heuristics
> **Comments:**
> **username_1**: TSP or ATSP? I think you mean TSP but in title you wrote ATSP.  
> **username_0**: @Saeed I mean ATSP (Asymmetric TSP)  
> **username_1**: 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.  
> **username_0**: @Saeed I wrote ATSP, and LK works fine for ATSP: http://www.akira.ruc.dk/~keld/research/LKH/Soler_results.html  
> **username_1**: Actually I confused by this sentence "I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations)", I think 2-opt is [this](http://en.wikipedia.org/wiki/2-opt) which is for TSP not ATSP, I don't know how they can adopt it for ATSP to get reasonable result, e.g in the link you provided it is LKH algorithm not LK which is variation of LK as authors wrote. Also even in that case maybe inputs are not just euclidean, e.g largest weight is also 12000 as written and they may have more restriction that makes it possible to apply some tricks. (I was not able to open input files).  
> **username_2**: @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?  
> **username_1**: @SashoNikolov, first I wrote a comment as a response to your comment, but then I thought my previous comment was clear enough in my opinion. So I cannot elaborate it more.  
> **username_2**: @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.  

---

## 2 answers

### Answer by username_3 on 2015-11-30. Score: 4

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>


---

### Answer by username_4 on 2015-02-24. Score: 1

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](http://homes.cs.washington.edu/~shayan/atsp.pdf) achieves $O(\log n / \log \log n)$ approximation for $n$-vertex graphs.

> **Comments:**
> **username_2**: hardly a local search algorithm  

---

