28 Jul 2026 =====================================
Concorde, Hexaly, and LKH on TSPLIB
=====================================
Hans Mittelmann
<mittelmann@asu.edu>
Logfiles are at: plato.asu.edu/ftp/hex_con_logs/
Platform: AMD Ryzen 9 5900X (12 cores, 128GB). Concorde 03.12.19. Hexaly 15.0, LKH-2.0.11, Random seed for Concorde 99.
Hexaly frequently compares their hybrid heuristic code to exact solvers such as Gurobi and Concorde, see here.
One may rather compare to other heuristics such as LKH in case of the TSP; that also works for asymmetric cases.
This benchmark is showing how well symmetric TSP problems from TSPLIB can be approximately solved in a matter of minutes with the codes.
=============================================================================== geom mean 88 10 1 ------------------------------------------------------------------------------- prob optimum Hexaly gap Concorde gap LKH gap time =============================================================================== brd14051 469385 483988 3.11 471013 0.35 469423 0.008 300 d15112 1573084 1598270 1.60 1578568 0.35 1573377 0.02 300 d18512 645238 689073 6.79 647586 0.36 645805$ 0.09 300 d2103 80450 80588 0.17 81377 1.15 80494 0.05 600 fl3795 28772 28948 0.61 28782 0.03 28935 0.57 300 fnl4461 182566 185105 1.39 183039 0.26 182566 0 60 pcb3038 137694 139600 1.38 137840 0.11 137694 0 120 pla7397 23260728 23690400 1.85 23394587 0.58 23268800 0.03 60 pr2392 378032 382548 1.19 378032 0 378032 0 60 rl11849 923288 939969 1.81 929094 0.63 923339 0.006 600 rl5915 565530 574471 1.58 566951 0.25 565598 0.01 600 rl5934 556045 567837 2.12 557359 0.24 556172 0.02 600 u2152 64253 64874 0.97 64317 0.10 64253 0 60 u2319 234256 234847 0.25 234256 0 234256 0 60 usa13509 19982859 20575000 2.96 20063669 0.40 19984733 0.009 600 =============================================================================== Optimal and best objective and gaps reached after given time. LKH with single run and default parameters. $: time increased to 330s. Scaled and shifted geometric mean of gaps.
