Short answer: yes.
The paper you linked benchmarks only GUROBI (an exact MILP solver) and Google OR-Tools (generic meta-heuristics) against D-Wave’s hybrid quantum solvers. Both are respectable baselines, but for TSP-style routing problems there are well-known classical solvers that routinely beat them on both speed and solution quality.
| Family | Representative solver(s) | Why they matter | Typical edge over GUROBI / OR-Tools on TSP-like tasks |
|---|---|---|---|
| Special-purpose exact | Concorde branch-and-cut | Hand-crafted cuts + sophisticated heuristics; still state-of-the-art for optimal solutions up to ~100 k nodes | Finds and proves optimal tours that GUROBI cannot within hours, while being faster on mid-size instances en.wikipedia.org |
| Lin-Kernighan lineage | LKH 2/3, NeuroLKH, VSR-LKH | Variable-depth k-opt with clever candidate sets; LKH-3 handles ~40 TSP/VRP variants (open path, time windows, incomplete graphs) | “Appears to exceed the performance of all STSP heuristic algorithms proposed to date” link.springer.com; NeuroLKH “significantly outperforms LKH and scales to larger instances” proceedings.neurips.cc |
| Evolutionary hybrids | EAX-GA, DBMEA, RHGA | Combine crossovers with LK-style local search; highly competitive in noisy / high-dimensional cost spaces | Beat both Concorde (on time-to-first-tour) and vanilla LK on benchmarks up to 20 k nodes link.springer.com |
What this means for the paper’s problem setting
- Open-route, incomplete 3-D graphs – LKH-3 lets you model an open TSP by adding a dummy “return” vertex of zero cost, or by using its dedicated path variant. It accepts arbitrary cost matrices, so 3-D reachability or robot-energy costs are fine.
- Solution quality – On standard TSPLIB tests, LKH-3 and NeuroLKH usually hit the optimal tour within seconds to minutes for sizes similar to the paper’s (100-200 nodes), whereas OR-Tools was ~6–14 s slower and 4–18 % worse in their own table arxiv.org.
- Runtime – Concorde is slower than LKH for “just get a good tour”, but if you need the optimality certificate it is dramatically faster than a generic MILP (GUROBI needed 17 s–18 k s in the paper, Concorde typically finishes proof in sub-hour for <1 k nodes).
- Ease of use – LKH-3 is a single executable and accepts a simple
.tsp+ parameter file; bindings exist for C++, Python and ROS. Concorde builds on Linux/Mac withmakeand provides a callable library.
Practical recommendation for your experiments
- Add LKH-3 (or NeuroLKH if you can build PyTorch) to the benchmark. Use its
MOVE_TYPE = 5, PATCHING_C = 3defaults and enableSPECIAL = YESfor sparse graphs. - Use Concorde for a quality/optimality baseline instead of GUROBI; you’ll cut proof-of-optimality time and avoid big-M subtour constraints.
- Keep OR-Tools only if you need its rich constraint modelling (pickup-and-delivery, multiple robots, etc.). For pure path-length optimisation it is no longer state-of-the-art. That test matrix will give a much fairer picture of how far hybrid quantum solvers still have to climb.