Seller Issue Paper (TSP)

Question

I am looking for relative (after 2000) new articles about TSP. All the documents that I found were quite complex and required a high level of mathematical skills. I am looking for documents that are easy to read for those who have simple college mathematical knowledge and good knowledge of Java and C programming (I have not found any current article implementing TSP with these languages).

Any hints would be greatly appreciated.

---

(edit)

What I'm trying to say is that I am looking for documents that do not need to understand complex formulas. For example, some papers describe algorithms or solution philosophy. It is not necessary to implement this algorithm, just describe the methods. Perhaps using some simple geometry ...

I found several articles based on Lin-Kernigan methods that looked fine ...

Answer 1

I am a little familiar with TSP literature and I doubt that something meets your criteria; simpler, less mathematical algorithms were laid long before your cutoff.

David S. Johnson et al have some articles that I like: http://www2.research.att.com/~dsj/papers.html , specifically # 1 and # 3 in the Problem with the seller section.

Answer 2

If you want to simply, here is one page that describes the space filling curves to find a good solution (not optimal, obviously). Of course, a web page is not paper. I also do not know if the ideas presented were created after 2000. If this is more than what you are looking for, perhaps you should edit your question or give an example.

http://www2.isye.gatech.edu/~jjb/mow/mow.html

Answer 3

Here is what you can do:

1) Exploring Chapter 11, “Directional Local Search,” and Chapter 12, “Iterated Local Search from the Metaheuristics Handbook” (2010), each of which contains a section describing how GLS and ILS are designed for TSPs. Both ILS and GLS are interesting and fairly easy to implement.

2) Check this document: "Local Search Performed and its Application to the Salesman Problem"

3) Find the Ruby code for these algorithms here and rewrite it in Java