A Python implementation of the Lin-Kernighan (LK) heuristic for solving the Traveling Salesperson Problem. This solver processes TSPLIB format instances with Euclidean 2D geometry and provides high-quality approximate solutions using a chained version of the LK algorithm.
Key Features:
- Multiple starting cycle algorithms (natural, random, nearest neighbor, greedy, Borůvka, quick-Borůvka)
- Parallel and sequential processing modes
- Automatic gap calculation against optimal tours (when available)
- Tour visualization and saving in TSPLIB format
- Comprehensive test coverage and helper tools
Requirements: Python 3.12+ (uses modern features like f-strings, pathlib, and extensive type hinting)
# 1. Setup
python -m venv venv
source venv/bin/activate # On Windows: venv\Scripts\activate
pip install -r requirements.txt
# 2. Run with default settings (processes all TSPLIB95 instances)
python -m lin_kernighan_tsp_solver
# 3. Process specific files
python -m lin_kernighan_tsp_solver problems/tsplib95/berlin52.tsp
# 4. Customize settings (visualization enabled by default)
python -m lin_kernighan_tsp_solver --time-limit 10.0 --starting-cycle greedyFor interactive plotting on Ubuntu/Debian:
sudo apt-get update
sudo apt-get install python3-tk # Enables interactive plot windowsNote: The solver automatically detects tkinter availability and enables plotting by default:
- With
tkinter: Shows interactive plot windows - Without
tkinter: Automatically saves plots tosolutions/plots/
# Process all instances in problems/tsplib95/ (default)
python -m lin_kernighan_tsp_solver
# Process specific files
python -m lin_kernighan_tsp_solver file1.tsp file2.tsp
# Use different starting algorithm
python -m lin_kernighan_tsp_solver --starting-cycle greedy
# Set time limit (plots generated by default)
python -m lin_kernighan_tsp_solver --time-limit 20.0
# Process with default settings (tours saved and plots generated by default)
python -m lin_kernighan_tsp_solver| Option | Description | Default |
|---|---|---|
--starting-cycle |
Algorithm: natural, random, nearest_neighbor, greedy, boruvka, qboruvka |
qboruvka |
--time-limit |
Time limit per instance (seconds) | 5.0 |
--workers |
Number of parallel workers | All CPU cores |
--sequential |
Force sequential processing | Parallel |
--no-save-tours |
Don't save heuristic tours | Tours saved by default |
--save-plot |
Force saving plots to files (even with GUI) | Interactive if tkinter available |
--no-plot |
Disable all plot generation | Plots enabled by default |
qboruvka(default): Best balance of speed and qualitygreedy: Highest quality, slower for large instancesnatural: Fastest, lowest qualitynearest_neighbor: Good compromiseboruvka,random: Alternative options
Performance: natural > random > nearest_neighbor > qboruvka > boruvka > greedy
Quality: Often greedy ≥ qboruvka ≥ boruvka ≥ nearest_neighbor > random > natural
The solver automatically generates visualization plots showing optimal and heuristic tours:
# Default behavior: generate plots (interactive if `tkinter` available, otherwise saved to file)
python -m lin_kernighan_tsp_solver problems/tsplib95/berlin52.tsp
# Force saving plots to files (useful for servers/CI)
python -m lin_kernighan_tsp_solver problems/tsplib95/berlin52.tsp --save-plot
# Disable plotting entirely
python -m lin_kernighan_tsp_solver problems/tsplib95/berlin52.tsp --no-plot
Found 18 TSP instances.
Processing using 12 parallel workers...
Configuration parameters:
TIME_LIMIT = 20.00
STARTING_CYCLE = qboruvka
Instance OptLen HeuLen Gap(%) Time(s)
----------------------------------------------
berlin52 7544.37 7544.37 0.00 0.45
eil51 429.98 428.98 0.00 20.00
kroA100 21285.44 21285.44 0.00 4.07
...
----------------------------------------------
SUMMARY 910625.92 1104939.02 3.52 15.20
pip install -r requirements-dev.txt # Includes testing, linting toolspython -m pytest # Run all tests
python -m pytest --cov=lin_kernighan_tsp_solver --cov-report=html --cov-report=term-missing # With coverage# Create random TSP instances with defaults
python helpers/create_tsp_problem.py 20 # Creates rand20.tsp in problems/random/
python helpers/create_tsp_problem.py 15 --name custom --seed 123 # Custom name with seed
# Exact brute-force solver for small instances
python helpers/exact_tsp_solver.py # Process problems/random/*.tsp
python helpers/exact_tsp_solver.py --input-dir problems/custom # Custom input directory
# Simple k-opt TSP solver with time limits
python helpers/simple_tsp_solver.py # Process problems/tsplib95/*.tsp
python helpers/simple_tsp_solver.py --save-tours # Save tours and show plots (plots enabled by default)
python helpers/simple_tsp_solver.py --input-dir problems/random --time-limit 10 # Custom config- TSP files: Place
.tspfiles inproblems/tsplib95/(default) or updateTSP_FOLDER_PATHinlin_kernighan_tsp_solver/config.py - Optimal tours: Place
.opt.tourfiles alongside.tspfiles for gap calculation - Output folders:
- Lin-Kernighan heuristic tours:
solutions/lin_kernighan/(saved by default, disable with--no-save-tours) - Tour visualization plots:
solutions/plots/(automatically created, named by problem) - Helper tools:
solutions/simple/for simple TSP solver output
- Lin-Kernighan heuristic tours:
- Input folders:
problems/tsplib95/,problems/random/,problems/custom/for organized problem storage - Algorithm parameters: Modify
LK_CONFIGandSTARTING_CYCLE_CONFIGinconfig.py
Algorithm based on:
- Applegate, D.L., Bixby, R.E., Chvatál, V. & Cook, W.J. (2006): The Traveling Salesman Problem: A Computational Study, Princeton University Press
- Lin, S. & Kernighan, B.W. (1973): "An Effective Heuristic Algorithm for the Traveling-Salesman Problem", Operations Research, Vol. 21, No. 2, pp. 498–516
Course documentation (Finnish): Määrittelydokumentti | Toteutusdokumentti | Testausdokumentti
Weekly reports: Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8