This project was developed as part of the "Optimization Algorithms" course and addresses the Travelling Salesman Problem (TSP). The objective was to start from basic greedy algorithms, develop a local search, and finally create and test a hybrid metaheuristic based on ILS (Iterated Local Search) and SA (Simulated Annealing).
The final result of the project is an in-depth performance analysis of the hybrid metaheuristic and other techniques used, tested on TSPLIB instances and compared through graphs and metrics.
The project is organized into the following directories:
- algorithms: Contains implementations of metaheuristics, local search, neighborhood generators, and functions for perturbing solutions (ILS).
- analysis: Includes files for generating datasets and analyzing the performance of various algorithms on TSPLIB instances.
- plotting: Contains scripts to visualize the results of the tests performed.
- utils: Contains reusable utility functions, such as greedy algorithms, logger decorators, and tools for analyzing TSPLIB instances.
- data: Contains generated datasets and organized TSPLIB instances.
- outputs: Saves test results (JSON), logger logs, and graphs generated by the plotting scripts.
N.B.: Each directory contains a README file with more detailed information about its contents and functionalities.
The data directory includes the following subsets:
- EUC_2D, EXPLICIT, GEO: Instances to be used for metaheuristics, further subdivided by the number of instances.
- TSP_INSTANCES: Original TSPLIB instances.
- new_instances_filtered: TSPLIB instances filtered by size or type.
- euclidean: Dataset randomly generated using a previous script.
- TSP_instances_clean: Support directory for temporary processing.
The outputs directory includes:
-
plots:
-
EUC_2D_plot: Graphs related to EUC_2D instances. -
EXPLICIT_plot: Graphs related to EXPLICIT instances. -
GEO_plot: Graphs related to GEO instances. -
analysis_results: Results produced by the scripts in the
analysisdirectory.
Specific README files are present in the other directories with more details on the files and their functionalities.
- Clone the repository:
git clone https://github.com/lucadileo9/TSP.git
cd tsp-solver
- Run the scripts:
python -m TSP.[directory].[fileName]
Feel free to submit pull requests or report issues. Contributions to improve the algorithms or add new features are welcome.
This project is licensed under the MIT License - see the LICENSE file for details.