4
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ TSP or ATSP? I think you mean TSP but in title you wrote ATSP. $\endgroup$ – Saeed Feb 24 '15 at 23:12
  • $\begingroup$ @Saeed I mean ATSP (Asymmetric TSP) $\endgroup$ – yafrani Feb 25 '15 at 10:35
  • $\begingroup$ 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. $\endgroup$ – Saeed Feb 25 '15 at 11:38
  • 3
    $\begingroup$ @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? $\endgroup$ – Sasho Nikolov Feb 25 '15 at 16:46
  • 2
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Feb 26 '15 at 2:33
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ hardly a local search algorithm $\endgroup$ – Sasho Nikolov Feb 24 '15 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.