Group for Research in Decision Analysis


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

, , and

Branch-price-and-cut is a leading methodology for solving various vehicle routing problems (VRPs). For many VRPs, the pricing problem of a branch-price-and-cut algorithm is highly complex and, to alleviate this difficulty, a relaxed pricing problem is used. In this paper, we introduce a new paradigm, called selective pricing, that can be applied in this context to improve the solution process of hard-to-solve VRPs by branch-price-and-cut. This paradigm requires the development of an ad hoc labeling algorithm. To illustrate selective pricing, we apply it to a branch-price-and-cut algorithm for the VRP with windows where the relaxed pricing problem is a shortest $ng$-path problem with resource constraints. We develop an ad hoc labeling algorithm and show through computational experiments that it can yield substantial 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 is also efficient at reducing the overall computational times.

, 16 pages