Traveling Salesman

A Python TSP solver with exact methods, local search, metaheuristics, a command-line interface, and reproducible TSPLIB comparisons.

View TSP source and benchmarks

Why it matters

A solver comparison needs both solution quality and computation cost. Known benchmark answers and repeatable runs make that tradeoff inspectable, while keeping coordinate-based tour results separate from real road-network operations.

My contribution

I implemented and extended Python TSP solvers with a command-line interface and TSPLIB input. Fixed seeds and consistent distance rules make comparisons repeatable; small exact solutions and published optima provide references for judging the tradeoff between route quality and runtime.

Result

On four bundled TSPLIB instances, seeded iterated local search matched two published optima and finished within 0.75% on the other two. Held-Karp confirmed the 20-city example optimum of 386.43. CI passed 229 tests on both Python 3.8 and 3.12.

Tools

Python
NumPy
Held-Karp
Local search
Metaheuristics
TSPLIB
pytest
GitHub Actions

These are coordinate-based benchmark tours, not road-network routes with traffic, vehicle capacity, or time windows. Runtime depends on the machine; these results do not measure the separate municipal inspection project.

Project gallery

Current benchmark figures come from fixed-seed runs in the public repository. The final two images preserve the earlier portfolio version and are labelled historical. Select a preview to read the full chart. 7 images. Select an image to view it full size.

Current 20-city example: the genetic algorithm finds a tour of 386.43, also confirmed optimal by Held-Karp. Synthetic coordinates; seed 42.

Eight methods on the same 50-city random instance. Gaps are relative to the best observed route, not a proven optimum.

Solution quality for 20, 50, and 100 random cities. Percentages compare with the best observed result for each size; only the 20-city optimum is proven here.

Quality versus runtime on the 100-city random instance. Times are the fastest of three recorded runs and depend on the machine.

Four TSPLIB instances compared with their published optimal tour lengths using TSPLIB distance conventions. Seed 42.

Historical portfolio figure: the earlier 20-city best tour. The current benchmark figures appear first.

Historical console comparison from the earlier solver version. Its local-search distances and timings are superseded by the current benchmarks above.

From a route comparison to a reusable solver

The package now supports CSV coordinates, generated instances, and TSPLIB files through a command-line interface. Users can compare multiple algorithms, export a tour, and save a plot. TSPLIB EUC_2D, CEIL_2D, and ATT distance rules keep comparisons consistent with each instance.

Exact baselines: brute force is limited to 10 cities and Held-Karp defaults to 20; larger requests are skipped in comparisons rather than presented as solved.
Local search: distance-matrix move evaluation, ordered neighbor scans, and a final complete 2-Opt sweep improve speed while checking the default result for remaining improving moves.
Search diversity: double-bridge perturbations, simulated annealing, and a genetic algorithm explore alternatives beyond the initial local optimum.

Quality against known answers

The table uses seed 42 and the bundled TSPLIB distance rules. These route lengths were reproduced during the October 1 portfolio review. Matching a published optimum establishes the answer for that instance, not a general guarantee for the heuristic.

Seeded TSPLIB tour lengths; lower is better
Instance	Published optimum	2-Opt	Iterated local search	Genetic algorithm
eil51	426	446	427	427
berlin52	7,542	8,108	7,542	7,542
st70	675	716	680	681
kroA100	21,282	22,294	21,282	21,282

Scale and verification

The repository also compares random instances from 20 to 1,000 cities. Its 1,000-city example records tour lengths of 2,433.2 for 2-Opt, 2,358.3 for combined 2-Opt and Or-Opt, and 2,324.8 for iterated local search. These larger random instances have no proven optimum in the reported comparison.

The October 1 CI run passed 229 tests for each of Python 3.8 and 3.12, followed by a TSPLIB command-line smoke check. Tests cover valid tours, reproducibility, exact solutions on small instances, distance conventions, local-search behavior, and failed input or output handling. Chart timings are the fastest of three recorded runs and are machine-specific.

Technical details

Independent portfolio project · Updated October 2026

A fast route is not necessarily a good route. Comparing solvers requires consistent distance rules, repeatable random choices, and a known reference where one is available.

Compare brute force and Held-Karp with constructive methods, 2-Opt, 3-Opt, Or-Opt, iterated local search, simulated annealing, and a genetic algorithm with local search.
Use TSPLIB distance conventions and published optima for four bundled benchmark instances.
Reset the random stream for each algorithm so results do not depend on comparison order.
Check tour validity, exact-method agreement, local optimality, input errors, and the command-line workflow.

← Back to projects