Heuristics for the travelling salesman

Question

I am working on evolutionary optimization and on this project I need heuristics for the travelling salesman problem. In this context, genetic algorithms, we apply small mutations and hope that somewhere down the road things will get better. So, I am looking for simple heuristics for transforming the solution that could potentially lead to improvement.

Thank you for any suggestions

Answer 1

I think that you are looking for tour improvement heuristic and I can suggest that Lin-Kernighan algorithm for you. But this algorithm may be too difficult for you. So instead you can research 2-opt or 3-opt algorithm.

Answer 2

One reference that I want to recommend is R's TSP package. (Do look into it even if you are not using R.) Their vignette on TSP is excellent, and has lots of Dynamic Programming based tricks that you can try to improve your GA implementation.

Section 2.4 of the vignette in particular talks of Tour construction heuristics that you can incorporate. Quoting from that:

Nearest neighbor algorithm: follows a very simple greedy procedure: The algorithm starts with a tour containing a randomly chosen city and then always adds to the last city in the tour the nearest not yet visited city. The algorithm stops when all cities are on the tour.

An extension to this algorithm is to repeat it with each city as the starting point and then return the best tour found. This heuristic is called repetitive nearest neighbor.

Insertion algorithms. start with a tour consisting of an arbitrary city and then choose in each step a city not yet on the tour. This city is inserted into the existing tour between two consecutive cities i and j, such that the insertion cost (i.e., the increase in the tour's length) is minimized. The algorithms stop when all cities are on the tour.

Nearest insertion The city k is chosen in each step as the city which is nearest to a city on the tour.

Farthest insertion The city k is chosen in each step as the city which is farthest from any of the cities on the tour.

Cheapest insertion The city k is chosen in each step such that the cost of inserting the new city is minimal.

You can find a lot more detail and other techniques mentioned in the vignette.