This C project implements various algorithms for solving the Symmetric Traveling Salesman Problem (TSP), along with performance analysis tools. For more detailed information, please refer to the accompanying thesis file in repository. The thesis provides an in-depth explanation of the project and its analysis.
The primary objective of this project is to explore various algorithms and methodologies for efficiently solving the Traveling Salesman Problem (TSP).
- Greedy heuristic with GRASP
- Extra-mileage heuristic
- 2-OPT refining heuristic
- Tabu Search
- VNS (Variable Neighborhood Search)
- Simulated Annealing
- Genetic Algorithm
- Hard fixing
- Local branching
- Benders' loop
- Callback method
Performance profiles of the implemented methods are provided in the perf_prof folder. These profiles include computational performance metrics, solution quality, and convergence behavior.
- Installation: Clone the repository to your local machine.
git clone https://github.com/elnurisg/Symmetric_TSP- Compilation: Use the provided Makefile to compile the project.
make- Execution: Run the solver with the desired parameters.
./tsp <parameters>- Performance Profiling: Explore performance profiles in the perf_prof folder for detailed analysis.
- CPLEX Optimization Studio version 22.1.1
- GNU Plot for visualization
Implemented algorithms are documented with Doxygen for easy reference and understanding.