TSP solver

Advanced algorithms practice project of MLDM first year students for TSP problem ##Description The objective of this project is to implement some algorithms for solving Traveling Salesman Problem (TSP) and to provide an experimental study of their running time and the quality of the outputs as well. ##Alogorithms Included The algorithms developed for solving the TSP problem are:

1. Brute-force approach
2. Branch-and-Bound approach
3. 2-opt (edge swapping)
4. Minimum Spanning Tree approximation
5. Greedy approach and Itrative greedy
6. Randomized approach
7. Genetic algorithm
8. Evolutionary algorithm (Hillclimbing based)

##Installation Clone the repository at this link: https://github.com/thovo/aa_practice_project/

Run the command below to install the dependencies:

pip install setup.py

After finish installing, you can run with this command:

python TSP.py

Follow the instructions to run the test for every algorithms.

Utilities

1. XmlParserFinal: XML parser script for parsing TSPLIB95 xml files to python friendly input
2. RandomGenerator: Random TSP data generator with different configuration available
3. grahping: Automated graphing script using matplotlib APIs
4. Experimenter: Automation script for running of tests on algorithms and logging of results

##Contact If you get any issues or ideas, don't hesitate to fire us an email:

• Ahmed Hassan ahmed.adel.hassan@hotmail.com
• Tho VO votuongtho@gmail.com
• Omar Samir omar.samir3000@gmail.com