Various solvers for the Travelling Salesman Problem

The Travelling Salesman Problem (TSP) is a famously hard combinatorial optimization problem. Here two solvers are implemented:

• An efficient solver, which uses the Miller-Tucker-Zemlin Encoding to translate TSP into an Integer Programming problem and solves that with the commercial state-of-the-art solver Gurobi
• A standalone solver which implements the Held-Karp algorithm to solve TSP with dynamic programming
• A simple branch-and-bound solver for educational purposes, who can prune backtracking branches as soon as their lower bound is bigger than the current maximum
• Concorde State-of-the-art exact TSP solver using cutting planes
• LKH-3 Lin-Kernighan Heuristic, one of the best TSP heuristics
• Hygese Hybrid Genetic Search for CVRP/TSP

Quick Start

# 1. Run setup (installs all Julia packages)
julia setup.jl

# 2. Run the benchmark
julia --project=. main.jl

Requirements

• Julia 1.9+ (tested with 1.12)
• Concorde binary (for optimal solutions on larger instances)

Using benchmark(), one can compare the performances on the TSPLIB95 Dataset. benchmark.log also provides pre-recorded results measured with an Intel i9-10980HK and 32 GB of memory.

(c) Mia Müßig