5
$\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, 2015 at 23:12
  • $\begingroup$ @Saeed I mean ATSP (Asymmetric TSP) $\endgroup$
    – yafrani
    Feb 25, 2015 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, 2015 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, 2015 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, 2015 at 2:33

2 Answers 2

Reset to default
4
$\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, 2015 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.