I must say that when it comes to discrete optimization, the genetic/ant/simulated annealing/etc. stuff is more popular in academia than in industry (at least the industry that doesn't heavily include academics).
Works like Lin-Kernighan heuristic are extremely rare and a bunch of knowledge exists in industry only. Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and demonstrated its superiority (K. Helsgaun).
I mean, most of the code that gets released today, doesn't even handle time windows constraint in the best way possible (optimal updates, constant time feasibility evaluations etc.). I believe all open source vehicle routing libraries do not have any data-structure relevant optimizations for handling time windows, task precedence, dynamic workshift starts etc. All are fairly simple implementation tricks that just got lost under giant amounts of population based heuristics or mathematical linear programming approaches.
Concorde is fine. The LK heuristic was published in 1973. After that, until the mid 90s, no one could outperform the original published results with the same heuristic.
Honestly, I found the algorithm description cryptic. It just may be me not "in the know" when it comes to details, with your "bunch of knowledge [that] exists in industry only" being the details the authors didn't care to elaborate on in the algorithm description. Maybe a part of the reason for the failure to replicate is that other people found it cryptic as well and didn't understand crucial details.
BTW, in your opinion, is there any readable text on the LK algorithm? I'm afraid that all I've read so far seems to be suffering from this problem. I have a very specific optimization need that doesn't seem be covered even by LKH-3 (it seems to be that my problem could be treated either as asymmetric TSP with time windows on a small number nodes and a non-metric distance matrix, or alternatively from the other side as VRP with asymmetric distances, unknown number of vehicles, and bounded trip duration for every vehicle, but either of the two needs an additional constraint that all vehicle trips should get close to the number of working hours within a day with the exception of one trip which can be shorter - basically I need an "ATSP with sleeping breaks") so I may need to roll out my own implementation of something and for an outsider, there doesn't seem to be a good text on implementing these things realistically without having some prior knowledge already.
Helsgaun's reports are pretty descriptive when it comes to LK algorithm.
But yes, I do agree that the original writing and the way the algorithm is taught in universities is a little bit cryptic and sometimes a completely different algorithm.
Simple explanation of the algorithm is:
1. 2-opt swap (A .. B -> .. -> C .. D ===> A .. C <- .. <- B .. D) - constant time compute of everything to check feasibility and new cost,
2. recursive 2-opt - now between C .. B with bounds (you can figure out which swaps are inferior and not recurse).
That's all there is to the algorithm. Helsgaun improves it a bunch (with preprocessing, deeper and more efficient k-opt moves, more efficient datastructures) but keeps the same idea.
There's another very flexible method called "ejection chains" started by Fred Glover and is very effective if you couple it with efficient data structures but also, very cryptic. It easily supports time windows, breaks, flexible work hours, flexible number of vehicles etc. Of course, the latest papers in "ejection chains" show no such thing :D
Sometimes you can stumble upon PhDs publishing their code and the tricks do not exist at all.
and there they try to categorize the time complexity of solving these problems and the tables are just not as up-to date with the industry. Some O(n log n) are O(n) or even better (depending on the local moves you do).
But it's a good start. A lot of these subproblems can be implemented really fast on a CPU and I guess the moment they are explicitly solved in a software library that's when the heuristics research will improve.
Works like Lin-Kernighan heuristic are extremely rare and a bunch of knowledge exists in industry only. Even the mentioned heuristic was for decades being implemented incorrectly until one individual came and demonstrated its superiority (K. Helsgaun).
I mean, most of the code that gets released today, doesn't even handle time windows constraint in the best way possible (optimal updates, constant time feasibility evaluations etc.). I believe all open source vehicle routing libraries do not have any data-structure relevant optimizations for handling time windows, task precedence, dynamic workshift starts etc. All are fairly simple implementation tricks that just got lost under giant amounts of population based heuristics or mathematical linear programming approaches.