Solving pricing problem heuristically in column generation algorithm for VRP

Question

In the set covering/column generation approach for the VRP (Balinski and Quandt (1964), or e.g. this tutorial), the basic idea is:

1. Generate some routes.
2. Solve the set covering problem using those routes.
3. Generate more routes (using the dual values, via the pricing problem).
4. Go to 2.

(Obviously I'm leaving out a lot of details.)

I'm interested in situations where step 3 happens heuristically—either because the pricing problem can't be solved exactly (efficiently), or maybe even because the dual can't be formulated well or solved well. Presumably this would happen for VRP variants, not for the classical VRP itself.

Are there examples in the literature of new routes being generated heuristically? Are there standard approaches that are used?

Answer 1

Generating routes heuristically, or heuristic pricing, is very common in the vehicle routing literature. Even when the pricing problem can be solved exactly, heuristic pricing is often tried first. Only when no more routes can be generated by heuristics, the exact pricing algorithm is run. When heuristic pricing is used in this way, the overall method is still exact in the sense that the optimal solution to the problem is guaranteed to be found.

For vehicle routing, the state-of-the-art is summarized in a recent survey by Costa et al. (2019), see Heuristic Pricing (Section 3.1.6).

Among other things, the authors list and provide references for

• Relaxing dominance rules in labeling algorithms.
• Heuristically reducing the size of the network.
• Using aggressive dominance rules in labeling algorithms.
• Using tabu search.

Answer 2

The general rule is to use dynamic programming (Labeling Algorithm) to solve the VRP pricing problem. It has some advantage over solving the mathematical model. DP can yield many columns in each iteration versus the one column that yielded by solving the model. As @Kevin Dalmeijer mentioned you need to be able to solve the pricing problem exactly even if you mainly use a heuristic approach.

Normally, a constructive approach combined with a local search would do the work. I saw examples that solves the pricing problem with GRASP or Tabu Search. But if you are going to develop a branch-and-price algorithm later on you should choose a method that is compatible with the branching rule (e.g. Avoiding some edges or including certain edges in the routes). Here are some studies that use a heuristic approach combined with DP to solve the pricing sub problem.

1) Archetti, C., Bouchard, M., & Desaulniers, G. (2011). Enhanced Branch and price and cut for vehicle routing with split deliveries and time windows. Transportation Science, 45(3), 285–298.

2) Ozbaygin, G., Karasan, O. E., Savelsbergh, M., & Yaman, H. (2017). A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological, 100, 115-137

3) Dayarian, I., Crainic, T., Gendreau, M. and Rei, W. (2019). A branch-and-price approach for a multi-period vehicle routing problem.

4) Gauvin, C., Desaulniers, G., & Gendreau, M. (2014). A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands. Computers & Operations Research, 50, 141–153

5) Dayarian, I., Crainic, T. G., Gendreau, M., & Rei, W. (2015b). A column generation approach for a multi-attribute vehicle routing problem. European Journal of Operational Research, 241(3), 888–906

Answer 3

There are two possible situations.

1) You still want to solve your VRP exactly or obtain a valid lower bound. Then heuristic pricing is used only to speed up column generation (and it is always used nowadays). At the end, you always need to solve the pricing problem (or at least its relaxation) exactly. A standard approach for heuristic pricing is some modification of the labelling algorithm (mentioned above). Meta-heuristic algorithms have been less successful for this task. Although there is a paper on this subject (https://doi.org/10.1287/trsc.1070.0223), recent attempts have not been successful (yet) as I know from communication with people working on it.

2) You want to solve you VRP heuristically by a branch-(cut)-and-price (BCP). In principle, you can then solve the pricing problem heuristically. However, this approach is (arguably) not competitive with other more standard heuristics. Probably for this reason there are no papers on heuristic BCP in the literature for vehicle routing problems (I am not aware of them).

Answer 4

Contrary to the other answers, I claim that you don't need to solve the pricing problem exactly, not even as a last resort after trying heuristics. If you do solve it exactly, then you found the optimal solution (say $z^*_\text{LP}$) to the relaxed reduced master problem at the node.

But this is not needed: you want to use $z^*_\text{LP}$ as a lower bound for the objective value at the current B&B node. If you can find another lower bound, you don't need $z^*_\text{LP}$ and can you use your other bound. Perhaps your LB will be worse, which means you will be less effective at pruning your B&B tree, but the overall correctness of the algorithm is not affected. In other words, exploring a B&B tree does not mandate that the dual bound comes from the linear relaxation of the integer programme.

For VRP-like problems you can use the best column found by any pricing heuristic which solves a relaxation of the pricing problem, and plug it into the master problem.

See, for example: Mauro Dell’Amico, Giovanni Righini, and Matteo Salani. "A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection." Transportation science 40.2 (2006): 235-247. Section 3 in general and subsection "Lower bounding and termination" in particular provide a good hint on how you can use dual information from the pricing problem to provide a lower bound for the node.

Answer 5

I found a survey paper¹ that talks about the heuristics for the VRP. In page 289 it is mentioned that:

This formulation was first proposed by Balinski and Quandt (1964), but becomes impractical when $|S|$ is large. Agarwal et al. (1989) have used column generation to solve small instances of the VRP optimally. Heuristic rules for producing a promising subset $S'$of simple vehicle routes, called 1-petals, have been put forward by Foster and Ryan (1976) and Ryan et al. (1993). Renaud et al. (1996b) go one step further by including in $S'$ not only single vehicle routes, but also configurations, called 2-petals, consisting of two embedded or intersecting routes.

1) Classical and modern heuristics for the vehicle routing problem, Gilbert Laporte, Michel Gendreau, Jean-Yves Potvin, Frédéric Semet