Metaheuristics vs Column generation for VRP

Question

I am solving a vrp and its variants (pick up drop off, milk-run problem) using genetic algorithms. The issue that I am getting with the genetic algorithm is the randomness associated with the algorithm. Although randomness is an expected property of GA as it has to search the solution space, I feel like for some problem instances I am not getting good results. Using a fixed seed number gives the same results but the GA may produce worse results if the seed number is fixed . I recently discovered that some literature used the column generation approach.

Is column generation better than metaheuristics in terms of solution quality and solution runtime? If you used both metaheuristics and column generations for solving any vrp or tsp, would you share which method performed better and why?

Answer 1

Please note that it is difficult to say something generic about all VRP variants. There are certainly a lot of counter examples of what I wrote below.

First, column generation is mainly used within branch-and-cut-and-price algorithms which are the best exact methods for most VRP variants, even if branch-and-cut algorithms remain better in a few cases. You can give a look at the VRPSolver package for example.

Given an infinite time, branch-and-cut-and-price algorithms will find the optimal solution of a VRP problem and prove that it is optimal. Whereas local search based metaheuristics may find it, but won't prove that it is optimal.

Unfortunately, when branch-and-cut-and-price algorithms fail to terminate within the given time limit, they usually don't terminate with a solution as good as the solution found by local search based metaheuristics within the same time limit.

A rule of thumb would be, up to 200 locations to visit, branch-and-price-and-cut algorithms should find the optimal solution quickly; above, local search based metaheuristics would yield better solutions for running times of the order of 1 hour. Of course, this depends on the variant and the dataset.

In addition, column generation can also be used in a heuristic fashion, which can yield better solutions than a whole branch-and-cut-and-price, and quicker. If I'm not mistaken, this is for example the approach chosen by the VRPy package. Something to look at to determine if it might work better than local search based metaheuristics is how much the problem is constrained. More constraints will make local search less effective, but the pricing problem of the column generation easier. Still, in the literature on VRP problems, local search based metaheuristics are far more present that column generation based heuristics.

Answer 2

I make a commercial VRP solver - https://odllive.com

Speaking from my experience of commercial solvers, using local search methods (i.e. improvement heuristics like cheapest insert or cheapest move) together with controlling meta-heuristics seems to be the most common choice of algorithm. Controlling meta-heuristics could be something like iterated local search, construction-destruction methods etc. The combination of local search + controlling meta-heuristics being the 'best' algorithm to use has some backing in the academic literature as well.

Genetic algorithms on their own tend not to be powerful enough to solve VRPs effectively, they take too long to find an improvement that a simple cheapest move algorithm would find straight away. Local search heuristics on their own will get stuck in a local minima as they're pure greedy, which is why you need controlling meta-heuristic too.

Mathematical programming approaches like column generation tend not to be used much commercially, they're too slow. I also suspect (but don't know for sure) that it would be difficult to configure mathematical programming solvers to handle some of the rich problem features you can encounter in real-life, e.g. rush hours, modelling vehicle parking and a sub-route on foot (park-and-loop) etc.