I wonder the author considered using Integer Linear Programming. For me it tends to be a go-to way to solve problems like this, but often have issues when the modelled problems become harder than I thought and processing times will be .. months?
You end up with a very similar situation as you do without integer linear programming - an enormous search space. In the papers I've read on VRP that provide a linear programming formulation (2), they then fall back to approximate methods for actually doing the work.
ILP is not the same as brute forcing it, branch and bound and cut will quickly weed out a lot of that search space. And a good solver should find approximate solutions quickly.
The question is whether good solutions are found 1) as quickly as with the simulated annealing approach 2) as good as that approach 3) whether the formulation is maybe simpler.
I don't know of any, I learned that in school. But I'm currently working on writing one. If you're interested, I'd be interested in some feedback whether it's understandable.
