theyusko/tsp-heuristics

tsp-heuristics

A team project to implement and compare different TSP heuristics.

Heuristic algorithms:

1. Insertion Heuristics

2. Greedy

3. Nearest Neighbor (Chosen)

4. Branch and Bround

5. 2-Opt

6. Greedy 2-Opt

7. Genetic

8. Simulated Annealing

9. Neural Network

10. Minimum Spanning Tree (Chosen) https://www.geeksforgeeks.org/travelling-salesman-problem-set-2-approximate-using-mst/

11. Christofides

Resources:

Traveling Salesman Problem, four algorithms

https://www.youtube.com/watch?v=q6fPk0--eHY

Heuristic Implementations

• https://github.com/yihui-he/TSP
• https://github.com/rohanp/travelingSalesman
• https://ericphanson.com/posts/2016/the-traveling-salesman-and-10-lines-of-python/

Blogs

http://toddwschneider.com/posts/traveling-salesman-with-simulated-annealing-r-and-shiny/

Greedy Algo

https://stackoverflow.com/questions/30552656/python-traveling-salesman-greedy-algorithm

Test Data

• Euclidean graph is generated with the following definition of triangle inequality: Triangle-Inequality: The least distant path to reach a vertex j from i is always to reach j directly from i, rather than through some other vertex k (or vertices), i.e., dis(i, j) is always less than or equal to dis(i, k) + dist(k, j). The Triangle-Inequality holds in many practical situations. When the cost function satisfies the triangle inequality, we can design an approximate algorithm for TSP that returns a tour whose cost is never more than twice the cost of an optimal tour. The idea is to use Minimum Spanning Tree (MST). Following is the MST based algorithm.