The travelling salesman problem (TSP) is a problem that involves finding the shortest possible route that visits every city in a given list exactly once, before returning to the starting city. TSP has numerous practical applications, including in logistics, planning, and microchip production.
I solved this problem using some heuristic and metaheuristic Algorithms (NN, GA & ACO)
The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. Steps :
- Initialize all vertices as unvisited.
- Select an arbitrary vertex, set it as the current vertex u. Mark u as visited.
- Find out the shortest edge connecting the current vertex u and an unvisited vertex v.
- Set v as the current vertex u. Mark v as visited.
- If all the vertices in the domain are visited, then terminate. Else, go to step 3.
Genetic Algorithm (GA) is a meta-heuristic algorithm that attempts to simulate natural selection to find the best path by crossing-over parents and producing fitter offspring. Steps:.
- Creating initial population.
- Evaluation of each individual by fittness function.
- Selecting the best genes.
- Reproduction by Crossing over.
- Mutating to introduce variations.
Ant Colony Optimization (ACO) Algorithm is a meta-heuristic algorithm where "ants" explore different paths leaving pheromones where they travel further leading the shorter distances to be crossed more and thus have more pheromones for others to follow.
These algorithms do not guarantee optimal solution, but rather reach a sub-optimal or near-optimal solution in a manageable time.