🗺️ Travelling Salesman Problem — Multi-Algorithm Solver

A collection of algorithms tackling the Travelling Salesman Problem (TSP): one of the most famous NP-hard combinatorial optimization problems in computer science. The repository explores three fundamentally different approaches — exact constraint programming, graph-theory heuristics, and metaheuristics — benchmarked against a dataset of up to 85,900 cities.

---

What is the TSP?

Given a list of cities and the distances between them, find the shortest possible route that visits every city exactly once and returns to the starting point. Despite its simple formulation, no known algorithm solves it optimally in polynomial time for large inputs — it belongs to the class of NP-complete problems.

This makes TSP an ideal testbed for comparing exact solvers (which guarantee optimality but don't scale) against heuristics and metaheuristics (which sacrifice optimality guarantees for tractable runtime).

---

Algorithms implemented

1. Christofides Heuristic

main.py · TSP-basic.ipynb

The Christofides algorithm is the classic approximation algorithm for TSP with a proven worst-case guarantee of 1.5× the optimal tour length. It works in three phases:

1. Minimum Spanning Tree (MST): build the minimum spanning tree of the complete graph using NetworkX.
2. Odd-degree matching: identify all nodes with odd degree in the MST and add edges to make all degrees even (Eulerian condition).
3. Euler → Hamiltonian: traverse the resulting multigraph in DFS preorder, skipping already-visited nodes to produce a valid TSP tour.

def christofides(nodeCount, G):
    T = nx.MultiGraph()
    minumumTree = nx.minimum_spanning_tree(G).edges
    T.add_edges_from(minumumTree)
    # ...odd-degree matching...
    return list(nx.dfs_preorder_nodes(T))

Scaling strategy: for graphs with more than 1,000 nodes, building a full O(n²) graph is prohibitive. Instead, an incomplete graph is constructed connecting each node only to its next 100–200 neighbours (by index), dramatically reducing memory and build time while preserving enough connectivity for a good MST.

Initial ordering strategies — three orderings of the point cloud are tried and the best result is kept:

Strategy	Description
edgesFromOutlayer	Sort by distance from the sum-of-coordinates outlier point
edgesFromCentroid	Sort by distance from the centroid (center of mass)
Default index order	Use points as they appear in the input file

---

2. Simulated Annealing

TSPsa.py · TSP-basic.ipynb

Simulated annealing is a probabilistic metaheuristic inspired by the annealing process in metallurgy: a material is heated and then slowly cooled to reach a low-energy crystalline state. Applied to TSP:

• A neighbouring solution is generated by swapping two adjacent cities (reverseOrder).
• If the neighbour is better, it is always accepted.
• If it is worse, it is accepted with probability exp(-Δ/T), where T is the current temperature.
• Temperature decreases each iteration: T ← α·T (cooling schedule).

theta = newValue - value
if theta > 0:
    if np.random.uniform(0, 1) <= math.exp(-(theta / t)):
        solution = newSolution   # accept worse solution probabilistically
else:
    solution = newSolution       # always accept improvement
t = alpha * t                    # cool down

This controlled acceptance of worse solutions allows the algorithm to escape local minima, a key advantage over pure greedy descent.

Parameters:

Parameter	Value	Effect
alpha	0.9	Cooling rate — higher = slower cooling = more exploration
Initial T	-(n / log(0.9))	Scaled to problem size
Stopping condition	1,000 iterations without improvement

The TSP-basic.ipynb notebook includes a more complete SimAnneal class with a greedy nearest-neighbour initialisation, 2-opt segment reversal as the neighbourhood operator, and a fitness convergence plot.

---

3. Genetic Algorithm

TSPgenetico.py · TSP-basic.ipynb

A genetic algorithm that evolves a population of candidate tours over generations:

Population & selection:

• Population initialised with random permutations of cities.
• Each individual's fitness is its total tour length (lower = better).
• Survival probability: (1 - cost/total) - random_noise — the noise term prevents super-individuals from dominating and getting stuck in local optima.
• The two best survivors become the next generation's parents.

Crossover operators — two strategies for generating offspring from parents:

Operator	Description
indexGen	Uses parent A's values as indices into parent B — fast but can create symmetric cycles
legit	Takes a random prefix from A, then fills the rest in B's order — always produces valid permutations

Mutation: with probability 0.001 per generation, two random positions are swapped in each parent, preventing premature convergence.

if random.uniform(0, 1) < 0.001:
    mutationSolution(solutions[0])
    mutationSolution(solutions[1])

---

4. Angular Sweep from Centroid

TSP-basic.ipynb

An experimental geometric heuristic: cities are sorted by the angle they form with a vertical reference ray through the centroid of the point cloud, effectively doing a circular sweep around the center of mass. This produces good results for uniformly distributed points but degrades with clustered or sparse inputs.

---

5. Constraint Programming (MiniZinc)

recorridoMapa.mzn

An exact solver formulation using MiniZinc, a constraint programming language. The model:

• Declares orden[i] as a decision variable — the city visited at step i.
• Enforces alldifferent (every city visited exactly once).
• Fixes orden[1] = 1 (start from city 1).
• Minimises total Manhattan distance of the tour.
• Uses first_fail + indomain_min search heuristic for branch-and-bound.

var float: recorrido = sum(i in 1..node_count-1)(
    abs(map[orden[i],1] - map[orden[i+1],1]) +
    abs(map[orden[i],2] - map[orden[i+1],2])
) + regreso;

solve :: int_search(orden, first_fail, indomain_min, complete) minimize recorrido;

This approach guarantees the global optimum but is only tractable for small instances (tens of cities). The circuit constraint (commented out) would enforce the Hamiltonian cycle condition more directly.

---

2-Opt Local Search

All heuristic methods include a 2-opt improvement post-processing step. 2-opt iteratively tries swapping pairs of adjacent edges to remove crossings, reducing total tour length until no local improvement is possible. It is a standard local search refinement for TSP.

---

Benchmark results

Results from the Simulated Annealing solver over the Kaggle dataset (./data), ranging from 5 to 85,900 cities:

Instance	Cities	Tour length
tsp_5_1	5	4.0
tsp_51_1	51	597.6
tsp_100_6	100	11,069.7
tsp_1000_1	1,000	37,405,109.7
tsp_11849_1	11,849	7,593,496.0
tsp_85900_1	85,900	306,187,932.3

Results are saved to result/sample_submission.csv (sorted alphabetically by filename).

---

Project structure

tsp-problem/
├── main.py                        # Christofides pipeline — reads ./data, writes ./result
├── TSPsa.py                       # Standalone Simulated Annealing solver
├── TSPgenetico.py                 # Standalone Genetic Algorithm solver
├── TSP-basic.ipynb                # Kaggle notebook — all methods + SimAnneal class
├── recorridoMapa.mzn              # MiniZinc exact CP model
└── result/
    ├── sample_submission.csv          # Sorted results
    └── sample_submission_non_sorted.csv

---

Usage

# Install dependencies
pip install networkx numpy pandas scikit-learn matplotlib

# Run Christofides solver (reads ./data, writes ./result)
python main.py

# Run Simulated Annealing solver
python TSPsa.py

# Run Genetic Algorithm solver
python TSPgenetico.py

Input format — plain text files in ./data/:

<node_count>
<x1> <y1>
<x2> <y2>
...

---

Algorithm comparison

Algorithm	Optimality	Scales to large n	Runtime	Key idea
Constraint Programming	✅ Exact	❌ Small only	Exponential	Branch & bound
Christofides	≤ 1.5× optimal	✅ With incomplete graph	O(n² log n)	MST + matching
Simulated Annealing	Approximate	✅	O(iterations)	Accept worse solutions probabilistically
Genetic Algorithm	Approximate	✅	O(gen × pop)	Evolve population via crossover + mutation
Angular Sweep	Approximate	✅	O(n log n)	Geometric sweep from centroid

---

Key references

Concept	Reference
Travelling Salesman Problem	TSP — Wikipedia
NP-hardness	NP-hardness — Wikipedia
Christofides algorithm	Christofides algorithm — Wikipedia
Minimum Spanning Tree	Minimum spanning tree — Wikipedia
Simulated Annealing	Simulated annealing — Wikipedia
Genetic Algorithm	Genetic algorithm — Wikipedia
2-opt local search	2-opt — Wikipedia
Constraint programming	Constraint programming — Wikipedia
Centroid	Centroid — Wikipedia
Manhattan distance	Taxicab geometry — Wikipedia