6
$\begingroup$

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?

$\endgroup$

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a great response. Thank you so much! $\endgroup$
    – mars
    Jun 2, 2022 at 19:35
5
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ "Genetic algorithms on their own tend not to be powerful enough to solve VRPs effectively" Note that, in the VRP community, what is called "genetic algorithm" is usually a local search algorithm which strategy to get out of local optima is to restart from a new solution obtained by crossing two previous solutions. In this case, it is very powerful doi.org/10.1016/j.ejor.2013.09.045 doi.org/10.1016/j.cor.2021.105643 several of the best methods of the Dimacs challenge on VRPs rely on this strategy $\endgroup$
    – fontanf
    Jun 5, 2022 at 5:57
  • 1
    $\begingroup$ Interesting. Obviously hybrid or modified GAs are a different matter, it's just 'plain vanilla' GAs on their own (without any kind of local search) that aren't really powerful enough in my opinion. $\endgroup$ Jun 6, 2022 at 1:03
  • 1
    $\begingroup$ It's also interesting how the academic and commercial have different goals. The Dimacs challenge would likely be aimed at finding the best solution to medium-sized problems which probably aren't that rich. In industry, what's more important is finding 'good enough' solutions to richer problems which can be significantly larger (e.g. 5000 jobs). Richer problems can be slower to evaluate changes to a solution, which means that population-based approaches like GAs have to be replaced by algorithms which focus more on the improvement of a single or small number of solutions. $\endgroup$ Jun 6, 2022 at 1:08
  • 1
    $\begingroup$ "it's just 'plain vanilla' GAs on their own (without any kind of local search) that aren't really powerful enough in my opinion" I agree on this, I just wanted to clarify since we often use same words to talk about different things in our field. $\endgroup$
    – fontanf
    Jun 6, 2022 at 6:55

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .