TSP Algorithms Visualizations

I have displayed visualizations of several inputs of data. I am using data from the TSPLIB as input and the Hamiltonian paths we create as outputs. I am focusing on the visualizations of the paths created by the Nearest Neighbor, Greedy, Convex Hull, and Christofides algorithms. The last visualization corresponds to that of the optimal path. Code for the computation of the paths and visualizations can be found here.
For the graphs, the % difference is calculated by abs(optimal path length - algorithm path length)/ optimal path length. For the first and last dataset, I used the adjacency matrix provided with the TSP instance. For the rest of the data sets, I calculated the adjacency matrix based on euclidean distance.

1. P01 (15 nodes)

Our smallest dataset that I tested. Below are the algorithms and their respective costs.

Optimal Solution

Cost: 219, % Difference = 0%

Nearest Neighbor

Cost: 219, % Difference = 0%

Greedy

Cost: 219, % Difference = 0%

ConvHull

Cost: 219, % Difference = 0%

The next four vids show the performance of Christofides on the dataset.

Minimum

Spanning Tree

Minimum Weight

Perfect Matching

Eulerian Tour of the union

of MW and MST

Christofides Approximation

Cost: 219, % Difference = 0%

2. ATT48 (48 nodes)

A dataset containing 48 of the US state capitals. Below are the algorithms and their respective costs.

Optimal Solution

Cost: 33,523.708, % Difference = 0%

Nearest Neighbor

Cost: 42,156.22, % Difference = 25.76%

Greedy

Cost: 40,160.36, % Difference = 19.8%

Convex Hull

Cost: 34,552.71, % Difference = 3.06%

The next four vids show the performance of Christofides on the dataset.

Minimum

Spanning Tree

Minimum Weight

Perfect Matching

Eulerian Tour of the union

of MW and MST

Christofides Approximation

Cost: 37,381, % Difference = 16.02%

3. ch150 (150 nodes)

A dataset involving 150 mining locations. Below are the algorithms and their respective costs.

Optimal Solution

Cost: 6,532.28 , % Difference = 0%

Nearest Neighbor

Cost: 7,675.33, % Difference = 17.5%

Greedy

Cost: 7,743.035, % Difference = 18.54%

Convex Hull

Cost: 6,916.077, % Difference = 5.87%

The next four vids show the performance of Christofides on the dataset.

Minimum

Spanning Tree

Minimum Weight

Perfect Matching

Eulerian Tour of the union

of MW and MST

Christofides Approximation

Cost: 7,172.75 , % Difference = 9.8%

4. a288 (150 nodes)

A dataset involving 288 city locations. Below are the algorithms and their respective costs.

Optimal Solution

Cost: 2,586.769 , % Difference = 0%

Nearest Neighbor

Cost: 4,991.03, % Difference = 9.3%

Greedy

Cost: 3,115.26, % Difference = 20.4%

Convex Hull

Cost:2,726.97 , % Difference = 5.4%

The next four vids show the performance of Christofides on the dataset.

Minimum

Spanning Tree

Minimum Weight

Perfect Matching

Eulerian Tour of the union

of MW and MST

Christofides Approximation

Cost: 2,909.32, % Difference = 12.4%

Extra DataSets (Not included in data! Just done for fun!) pcb442 (442 nodes)

A dataset involving 442 city locations. Below are the algorithms and their respective costs.

Optimal Solution

Cost: 50,784 , % Difference = 0%

Nearest Neighbor

Cost: 107,213 , % Difference = 111.11%

Greedy

Cost: 63,540, % Difference = 25.112%

Convex Hull

Cost: 54,249, % Difference = 6.82%

The next four vids show the performance of Christofides on the dataset.

Minimum

Spanning Tree

Minimum Weight

Perfect Matching

Eulerian Tour of the union

of MW and MST

Christofides Approximation

Cost: 56,388 , % Difference = 11.6%