This repository provides an experimental benchmark of several algorithms used to solve the Traveling Salesman Problem (TSP). The goal of this project is to analyze the trade-off between runtime performance and solution quality across different approaches.
The algorithms are implemented in C++, while Python (Pandas + Matplotlib) is used for data analysis and visualization of benchmark results.
The Traveling Salesman Problem (TSP) is one of the most well-known problems in combinatorial optimization.
Given a set of cities and the distances between them, the objective is to determine the shortest possible route that visits each city exactly once and returns to the origin city.
TSP is classified as an NP-hard problem, meaning that exact solutions become computationally expensive as the number of cities increases.
A greedy heuristic that constructs a tour by repeatedly selecting the nearest unvisited city.
Advantages:
- Extremely fast
- Simple to implement
Limitations:
- May produce suboptimal routes
This method improves the greedy solution using 2-opt local search optimization. The algorithm repeatedly removes two edges and reconnects them in a way that reduces the total tour length.
Advantages:
- Significantly improves solution quality
- Still computationally efficient
The brute force method enumerates all possible permutations of city tours to guarantee the optimal solution.
Time complexity: O(n!)
This approach is only practical for very small graphs.
| Algorithm | Time Complexity | Optimal |
|---|---|---|
| Nearest Neighbor | O(n²) | No |
| Nearest Neighbor + 2-opt | O(n³) | No |
| Brute Force | O(n!) | Yes |
The benchmark generates random complete graphs and evaluates each algorithm across multiple test runs.
Evaluation metrics include:
- Runtime (microseconds)
- Tour cost
- Relative solution quality
- Improvement from 2-opt optimization
The brute force algorithm grows exponentially as the number of vertices increases, while heuristic methods remain efficient.
Nearest Neighbor produces reasonable solutions, while the 2-opt refinement significantly improves tour quality.
This ratio shows how close heuristic solutions are compared to the optimal brute-force solution.
The optimization step significantly reduces the total tour cost.
This visualization highlights the engineering trade-off between speed and accuracy.
These animations illustrate how the greedy heuristic constructs a tour and how the 2-opt local search improves the route.
An interactive dashboard is available in:
benchmark_dashboard.html
It allows exploration of runtime scalability, solution quality, and optimization improvements across algorithms.
| Observation | Result |
|---|---|
| Fastest Algorithm | Nearest Neighbor |
| Best Practical Trade-off | NN + 2-opt |
| Optimal Algorithm | Brute Force |
| Scalability | Heuristics scale significantly better |
Benchmark Generator (C++)
↓
Algorithm Execution
↓
Raw Benchmark Data (CSV)
↓
Data Analysis (Python + Pandas)
↓
Visualization (Matplotlib)
Traveling-Salesman-Problem-Benchmark
│
├── benchmark.cpp
├── tsm.cpp
├── tsm.h
├── bellman.cpp
├── bellman.h
├── main.cpp
│
├── plot_results.py
├── generate_tsp_animation.py
├── benchmark_dashboard.py
│
├── results.csv
├── benchmark_summary.csv
├── benchmark_readme_table.csv
│
├── tsp_nn_demo.gif
├── tsp_nn_2opt_demo.gif
│
├── benchmark_dashboard.html
│
├── 01_runtime_scalability.png
├── 02_solution_quality.png
├── 03_relative_quality.png
├── 04_two_opt_impact.png
├── 05_tradeoff_runtime_vs_quality.png
├── 06_solution_stability.png
│
└── README.md
g++ -O2 -std=c++17 benchmark.cpp tsm.cpp -o benchmark.exe./benchmark.exeThis command will generate:
results.csv
python plot_results.pyThe script will automatically generate all benchmark visualization figures.
- C++
- Python
- Pandas
- Matplotlib
- Git
To evaluate the effectiveness of the implemented algorithms, a benchmark was conducted using randomly generated complete graphs.
Each algorithm was tested on multiple graph instances with varying numbers of vertices.
Evaluation metrics:
-
Runtime (microseconds)
-
Tour cost
-
Relative solution quality
-
Improvement from local optimization
- Nearest Neighbor is the fastest algorithm but often produces suboptimal tours.
- Nearest Neighbor + 2-opt significantly improves solution quality with minimal additional computational cost.
- Brute Force guarantees the optimal solution but becomes computationally infeasible as the number of vertices increases.
The benchmark demonstrates that combining greedy heuristics with local optimization provides the best practical trade-off between performance and accuracy.
- Greedy heuristics provide fast but sometimes suboptimal solutions.
- Local search optimization (2-opt) significantly improves greedy solutions.
- Exact algorithms guarantee optimality but scale poorly for large graphs.
- Combining heuristics with local optimization provides the best practical trade-off between speed and solution quality.
Le Hien Vinh
Ho Chi Minh City University of Technology