Selective pricing in branch-price-and-cut algorithms for vehicle routing

Branch-price-and-cut is a leading methodology for solving various vehicle routing problems (VRPs). For many VRPs, the pricing subproblem of a branch-price-and-cut algorithm is highly time consuming, and to alleviate this difficulty, a relaxed pricing subproblem is used. In this paper, we introduce a new paradigm, called selective pricing, that can be applied in this context to reduce the time required for solving hard-to-solve VRPs by branch-price-and-cut. This paradigm requires the development of a labeling algorithm specific to the pricing subproblem. To illustrate selective pricing, we apply it to a branch-price-and-cut algorithm for the VRP with time windows, where the relaxed pricing subproblem is a shortest ng-path problem with resource constraints. We develop a labeling algorithm for this subproblem and show through computational experiments that it can yield significant time reductions (up to 32%) to reach a good lower bound on certain very-hard-to-solve VRPTW instances with 200 customers. We also introduce a new labeling heuristic which also leads to computational time reductions.

Mots clés

• column generation
• vehicle routing problem
• branch-and-price
• shortest path problem under resource constraints
• selective pricing