TravelingSalesmanSolver

A solver for the traveling salesman problem.

image source

This package provides wrappers to call Concord TSP Solver and LKH from C++.

Beware that even though this package is licensed under the terms of the MIT license, neither are the Concord TSP Solver nor the LKH packages.

Both solvers are called through system calls. Inputs and outputs are handled through files. It is required to have the concorde and the LKH executables in the path.

Usage (command line)

Compile:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release --parallel
cmake --install build --config Release --prefix install

Download data:

python3 scripts/download_data.py

Examples:

./install/bin/travelingsalesmansolver -v 1 -i ./data/tsplib/a280.tsp -a concorde

=====================================
       TravelingSalesmanSolver       
=====================================

Instance
--------
Number of vertices:  280

Algorithm
---------
Concorde

       T (s)          UB          LB         GAP     GAP (%)                 Comment
       -----          --          --         ---     -------                 -------
       0.000         inf           0         inf         inf                        
       0.614        2579           0        2579         inf          final solution
       0.614        2579        2579           0        0.00          final solution

Final statistics
----------------
Value:                         2579
Bound:                         2579
Absolute optimality gap:       0
Relative optimality gap (%):   0
Time (s):                      0.614178

Solution
--------
Number of vertices:  280 / 280 (100%)
Feasible:            1
Distance:            2579