Traveling Salesman Problem (TSP)

Implementing four different approaches to solve traveling saleman problem

Originally, it was a group project (group of four) in CSE Advance Algorithms course. Even though I was exempetd, I accomplished and submitted this project individually, and won one of the performance competitions. In this project, I developed multiple different algorithms, including

  • (1) Brute-Force,
  • (2) Branch-And-Bound (BnB),
  • (3) Approximation,
  • (4) Multiple Local Search Approaches,
in Python. At the end, a comprehensive report is presented including algorithms details, empirical evaluations, accuracy tables and evaluation plots (QRTDs, SQDs, etc.).

The source codes of this project is available for download in the downloads section.

Developed multiple different algorithms to solve TSP problem and presented an extensive report, including a comprehensive discussion on the performances and trade-offs