The project deliberately combines algorithms with different trade-offs so that solution quality, runtime, scalability, and implementation complexity can be compared.
Category: Greedy heuristic
Starting from one node, the algorithm repeatedly chooses the nearest unvisited node and finally returns to the start. It is easy to explain and fast enough for larger demonstrations, but it has no optimality guarantee and can be sensitive to the start node.
Category: Exact algorithm
The implementation uses a bitmask-based state representation and memoization. Each state consists of the current node and the set of remaining nodes. It returns an optimal tour but has exponential time and memory requirements.
For controlled execution, the application rejects instances with more than 26 nodes.
Category: Approximation algorithm
The implementation follows the classic structure:
- construct a minimum spanning tree,
- identify odd-degree vertices,
- add a matching,
- construct an Euler tour,
- shortcut repeated vertices.
For metric TSP instances, Christofides provides a theoretically bounded approximation. The project implementation is intended for educational comparison and visualization.
Category: Metaheuristic
The reference implementation starts with a deterministic random tour, creates neighboring tours by swapping internal positions, and accepts improvements immediately. Worse solutions can also be accepted according to the temperature-dependent probability:
exp(-delta / temperature)
Common comparison parameters include:
| Parameter | Value |
|---|---|
| Seed | 20260701 |
| Initial temperature | 1000.0 |
| Cooling factor | 0.995 |
| Minimum temperature | 0.01 |
| Maximum iterations | 10000 |
| Neighborhood | Swap two internal tour positions |
Three additional Simulated Annealing implementations are included:
SimulatedAnnealingClaudeSimulatedAnnealingGemma4SimulatedAnnealingQwen3CoderNext
They solve the same problem using the same project interfaces while differing in path representation, helper-method structure, neighbor handling, edge-case handling, and update strategy. The frontend compares them with the team reference implementation.
These files are presented as an educational experiment, not as evidence that one model or implementation is universally superior.
Category: Integer linear programming
The project's DFJ implementation constructs a linear model, solves it with project-specific simplex and integer-programming components, detects subtours, and iteratively adds subtour-elimination constraints until one valid tour remains.
This implementation is especially useful for demonstrating the relationship between TSP, linear programming, integrality, and subtour elimination. It is not intended to replace specialized industrial optimization solvers.