Local Search TSP

Python based implementation of local search algorithms - Randomized Greedy, 2 Optimal and 3 Optimal

Background

Traveling Salesman Problem is one of the widely solved problems in Operations Research and is computationally intensive (NP-hard) to obtain optimal solution for. Luckily there exists relatively fast heuristics that search locally to obtain a near optimal tour. As they are called heuristics, there isn't a guarantee on the quality of solution in terms of closeness to the optimal solution. Nonetheless, local search techniques are widely used for their easy implementation and decent performance.

Following local search TSP algorithms have been implemented in this project:

1. Randomized Greedy
2. 2 Optimal
3. 3 Optimal

How it works

Create TSP object by calling

from tsp import TSP

# v is list of vertices/nodes
# (Optional) edges is list of tuples where each tuple is format (u,v,w)
tsp = TSP(v, edges=[])

If edges are not added at the time of initialization they can be added by calling

# for edge between (u,v) with weight w
tsp.addEdge(u, v, w)

First create a greedy tour by calling with optional parameters

# startnode (optional) is to specify starting node for greedy tour
# randomized (optional) is boolean to run randomized greedy when True
tour = tsp.greedyTour(startnode=None, randomized=False)

The greedy tour can be further optimized using 2 OPT or 3 OPT search methods

# argument tour is a list of nodes forming a cycle
twoopttour = tsp.twoOPT(tour)

# 3 OPT may also be called upon tour generated by 2 OPT
threeopttour = tsp.threeOPT(tour)

Running time

Improvement Heuristics - 2OPT and 3OPT: The running time of improvement algorithms primarily depend on number of neighborhoods they are search for better solution. If swapping edges and updating tour length is constant time, running time of 2 OPT and 3 OPT is approximately O(n^2) and O(n^3) respectively.