I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/
stuck in solving TSP.
As there are a lot of methods to solve this problem, I am currently coding
Guided Local Search as described here. This basically penalizes the longest edge and repeatedly searches that neighborhood until no improvement found. To search the neighborhood faster, it uses Fast Local search which basically marks a vertex inactive if no improving (2-Opt) moves are found.

My problem is that I do not see any improvement after the first Fast Local Search(FLS).
Any insights on this?

Also, what is the suggested method to solve TSP in order to ease?
Like I know these are methods
- Simulated Annealing with re-heat.
- Mixed Integer Programming(MIP) with Gomory Cut.
- LK(Lein-Kerninghan), LKH, ILKH heuristics
- GLS+FLS (I find this easy to start with)
- Hybrid approaches like MIP + SA.

  • $\begingroup$ This is a rather broad question. People have written surveys on practical approaches to TSP. Perhaps you could take a look at some of them. $\endgroup$ Feb 15, 2019 at 5:28
  • $\begingroup$ Thanks, should I try 3-opt, when 2 opt stuck in local minima $\endgroup$
    – Chits
    Feb 15, 2019 at 5:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.