- The travelling salesman problem (TSP) asks the following question:
- "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
- Main purpose of this problem is to find the shortest path which is as close to the optimal tour as possible.
- Since TSP problem is NP-hard problem, best approach for effiency is to find the approximate result in shortest amount of time.
- I decided to use 2-opt heuristic algorithm.
- In this approach algorithm works by looking for search area of possible solutions that will result in different set of permutations of a tour.
-
For optimizing this approach , in first step, I used Fast Local Search(FLS) optimization. Having declared 2-opt algorithm will create a chance to explore all possible 2-opt moves.
-
One approach is to continuously select two pair of edges and check whether they would result a better tour.
-
Instead of selecting random edges, FLS will iterate through all potential pair of edges and checking them for potential moves. If we found a move that can be used, then the corresponding pair of edges will be used in 2-opt algorithm and searching will be continued from the previous edge in the tour until there is no possible moves left. Then at that point we found 2-optimal.
-
The trouble that comes with this approach is wasting time to evaluating moves that will not give an improvement. To overcome this situation if a move is found by the program, I simply declare the pair of edges as used with using setUsedBits() and isUsed() functions. So that program will not check these edges ever again.
- In addition to FLS i decided to use Guided Local Search since it works synchronously with FLS.
- Guided Local Search is a metaheuristic search method. This approach is a method that builds on top of a local search algorithm to explore the search space for finding near-optimal solutions.
- The main purpose of this approach is guiding a local search algorithm, FLS in this case, by improving the corresponding objects that are declared and assigning a cost value to possible edges so that we can compare efficiently.