This project implements several heuristic algorithms to solve the classic Travelling Salesman Problem (TSP). The TSP is an NP-hard problem that asks for the shortest possible route that visits each city exactly once and returns to the origin city.
The algorithms are divided into two main categories:
These algorithms build a solution from scratch, adding one city at a time based on some criteria.
-
Nearest Neighbor (NN):
Starts from a random city and always chooses the nearest unvisited city. -
Pilot Method (with NN as base):
Enhances the basic NN by evaluating the impact of choosing each candidate city next, then picking the one that leads to the best complete solution (pilot evaluation).
These algorithms take an existing solution and try to improve it iteratively by exploring its neighborhood.
-
Hill Climbing:
Starts from an initial solution and continuously moves to a better neighboring solution (if any) until no further improvement is possible. -
2-opt:
A simple yet powerful improvement method that iteratively swaps two edges to eliminate path crossings and reduce total tour length. -
Tabu Search:
An advanced local search technique that uses memory structures (tabu list) to avoid revisiting previously explored (or recently altered) solutions and escape local minima.
We tested all algorithms on four datasets of increasing size:
| File Name | Number of Cities | Description |
|---|---|---|
tiny.csv |
10 | Very small, easy for debugging |
small.csv |
30 | Small, suitable for quick testing |
medium.csv |
100 | Medium-sized, highlights differences |
large.csv |
1000 | Larger scale, tests scalability |
