Implementing Algorithms to solve the travelling salesman problem
Jan 20, 2020
For this project we were to implement two algorithms for solving the travelling salesman problem.
I decided to implement Christofides algorithm and a Greedy Algorithm.
The basic greedy algorithm selects the next node with the lowest cost. However I enhanced this as there was indecision when there were multiple minimums to choose from as it couldn’t be determined which was best.
To solve this problem, my enhanced code looked ahead at what the cost would be of choosing the different choices, and chose the one that gave the lowest cost
This was implemented using the following functions
def test_next_step(tour2,depth): # Doing the whole rest of the sequence takes waaaay too much time # But also I really wanna get something cool working # What about limiting the level of recursion # Keep some counter tour=tour2[:] total_distance=0 while len(tour)<len(distance_matrix): first_node=distance_matrix[tour[-1]][:] for i in tour: first_node[i]=infinity minimum=min(first_node) indices = [i for i, x in enumerate(first_node) if x == minimum] if len(indices)>1 and depth<2: minimum_index=index_decision(indices,tour,depth) else: minimum_index=indices tour.append(minimum_index) total_distance=total_distance+minimum return [total_distance,tour] def index_decision(indices,tour,depth): shortest_distance=infinity minimum_index=0 for i in indices: new_tour=tour+[i] # print(i) distance=test_next_step(new_tour,depth+1) if distance<shortest_distance: shortest_distance=distance minimum_index=i return minimum_index
Note the depth is considered here, this is to avoid too many levels of recursion as within one decision there are further decisions that could be made. Considering all of these would have a very large performance impact
Christofides algorithm works by creating a Minimum Spanning Tree of the graph, then finding a minimum weight matching of the nodes with an even number of vertices. This matching is then combined with the original minimum spanning tree to form a multigraph where every vertex has an even degree. Then a Eulerian circuit is formed from this multigraph and finally converted into a Hamiltonian circuit by skipping repeated vertices.
While all of these steps are complicated, they are much easier than the NP problem of TSP.
I performed an enhancement on this in the final step of skipping repeated vertices as there is a choice of which one to remove. I compared the impact of skipping the different ones had on the tour and chose the best one.
In all but one of the hidden files tested on, my enhancement yielded a better result. In the one that didn’t it matched the length.