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.
