TSP / ATSP Solver — Exact and Heuristic Algorithms

A C++17 solver for the symmetric (TSP) and asymmetric (ATSP) Travelling Salesman Problem, developed for the Design of Efficient Algorithms (Projektowanie Efektywnych Algorytmów, PEA) course at the Wrocław University of Science and Technology. The repository collects all four project stages in a single configurable program, ranging from exact methods to metaheuristics.

The algorithm, the instance, and all control parameters are selected through a plain-text configuration file. Each run reports the obtained tour cost, the relative error against a known optimum, and the average execution time, and appends the results to a CSV file for further analysis.

Implemented algorithms

The active algorithm is chosen with the algorithm key in config.txt.

Category	Key	Description
Exact	BF	Brute force (full permutation search); intended for small instances
Exact	BB_BFS	Branch and Bound, breadth-first search
Exact	BB_DFS	Branch and Bound, depth-first search
Exact	BB_BEST	Branch and Bound, best-first (lowest lower bound expanded first)
Greedy heuristic	NN	Nearest Neighbour from a fixed start city
Greedy heuristic	RNN	Repetitive Nearest Neighbour (best over all start cities)
Greedy heuristic	RNN_NO_TIES	Repetitive Nearest Neighbour with deterministic tie-breaking
Random	RAND	Random sampling of tours, returning the best found
Metaheuristic	TABU_SEARCH	Tabu Search with SWAP / 2-opt neighbourhood and aspiration criterion
Metaheuristic	ACO	Ant Colony Optimization (Ant System, ant-cycle variant)

Supporting components: a matrix-reduction lower bound for Branch and Bound, a minimum spanning tree (Prim) lower bound used as an early-stop condition for Tabu Search, and several upper-bound strategies (INF, NN, RNN, RNN_NO_TIES, RAND) used to seed the search.

Repository structure

.
├── main.cpp              Entry point: config loading, run loop, CSV output
├── algorithms.cpp/.h     All TSP/ATSP algorithms and bounds
├── utils.cpp/.h          Config parsing, graph loading/generation, statistics
├── CMakeLists.txt        Build definition (C++17, -O3 -static)
├── config.txt            Run configuration (algorithm, instance, parameters)
├── badania.bat           Batch experiment driver (ACO parameter grid search)
├── scripts/              Python analysis (plots, result verification) and helpers
├── tsplib/               TSPLIB instances in the converted matrix format
├── results/              CSV output (created/used at run time)
└── sprawozdanie/         LaTeX report (Polish) with figures and tables

Requirements

• A C++17 compiler (GCC / MinGW-w64 recommended).
• CMake (the project is configured against the version stated in CMakeLists.txt).
• Python 3 with pandas and matplotlib, only for the analysis scripts under scripts/.

On Windows the executable links against psapi to report process memory usage; this is handled automatically by CMake. The binary is linked statically (-static), so it runs without extra runtime DLLs.

Building

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build

The resulting executable is named PEA_project_1 (PEA_project_1.exe on Windows). The project can also be opened and built directly in CLion using the bundled CMake toolchain.

Configuration

All behaviour is controlled by config.txt. Lines use a key = value format; everything after a # character is treated as a comment.

Key	Applies to	Description
algorithm	all	Algorithm key from the table above
repetitions	all	Number of repeated runs to average timing/statistics
symmetric	all	1 for TSP, 0 for ATSP
generateRandom	all	1 to generate a random instance, 0 to read from inputFile
inputFile	file mode	Path to the instance file
outputFile	all	Path to the CSV results file (appended to)
knownOptimum	all	Optimal cost used to compute relative error (0/absent = unknown)
showProgress	all	1 to print a progress indicator
startInstanceSize	random mode	Size n of the first generated instance
instancesCount	random mode	Number of consecutive sizes to test
minWeight/maxWeight	random mode	Edge weight range for the generator
randIterations	RAND	Number of random tours sampled
ubStrategy	BB_*, Tabu	Initial upper bound / starting solution strategy
metaNeighborhood	TABU_SEARCH	Neighbourhood operator: SWAP or TWO_OPT
tsMaxIterations	TABU_SEARCH	Iteration budget
tsTenure	TABU_SEARCH	Tabu list length (tenure)
tsAspiration	TABU_SEARCH	1 to enable the aspiration criterion
acoAnts	ACO	Number of ants in the colony
acoIterations	ACO	Number of cycles
acoAlpha	ACO	Pheromone weight (alpha)
acoBeta	ACO	Heuristic (visibility) weight (beta)
acoRho	ACO	Pheromone evaporation rate (rho), in the range 0..1

Input format

Instances use a simple matrix format:

n
d11 d12 ... d1n
d21 d22 ... d2n
...
dn1 dn2 ... dnn

The first line is the number of cities n, followed by an n x n distance matrix. A value of -1 denotes a missing edge (treated as infinity); diagonal entries are ignored. An optional trailing token sum_min=<value> may carry the known optimum for that instance.

If the program is run with generateRandom = 1, no input file is required and a random graph is created instead, according to startInstanceSize, symmetric, and the weight range.

Output format

Results are appended to the CSV file given by outputFile (semicolon-separated). The header is written automatically when the file does not yet exist. Columns:

Algorytm;Plik;Rozmiar;Repetycje;UB_Strategy;Sasiedztwo;TS_MaxIter;TS_Tenure;TS_Asp;
ACO_Ants;ACO_Iter;ACO_Alpha;ACO_Beta;ACO_Rho;Koszt;Optimum;Blad_wzgledny_%;Czas_us

Fields that do not apply to the selected algorithm are written as -. Koszt is the obtained tour cost, Optimum the reference optimum, Blad_wzgledny_% the relative error in percent, and Czas_us the run time in microseconds.

Note: the program does not create the output directory. Ensure the folder referenced by outputFile (for example results/) exists before running.

Author

Franciszek Wojnowski - Wrocław University of Science and Technology, Faculty of Information and Communication Technology. Developed for academic purposes as part of the PEA course.