I'm surprised that there is no mention of Tabu Search or other metaheuristics (like simmulated annealing, as pointed out in this thread). In my research, I disc

I'm surprised that there is no mention of Tabu Search or other metaheuristics (like simmulated annealing, as pointed out in this thread). In my research, I discovered it to be one of the best algorithms for this class of problems (determinisitic, non-black-boxy, flexible, can incorporate expert knowledge). Also worth mentioning is that while the TSP is interesting from an algorithms class perspective, a problem that occurs far more often in real-life is the Vehicle Routing Problem. The Vehicle Routing Problem (with time-windows, types, multiple vehicles, multi-depot, capacities, etc) is a much more complex problem compared to the TSP, and I would argue that pretty much all the algorithms mentioned in the article would fail to transfer. Here's an open-source library written in Common Lisp that implements the Tabu Search approach [1] -- shameless plug, but we also build an API for it [2] [1] https://github.com/mck-/Open-VRP https://github.com/mck-/Open-VRP [2] https://www.routific.com/developers https://www.routific.com/developers