Dive-and-cut-and-price heuristics for vehicle routing problems

Branch-and-cut-and-price algorithms based on set-partitioning formulations are popular methods for optimally solving vehicle routing problems (VRPs). This talk explores vehicle routing heuristics based on the branch-and-cut-and-price approach. The exact method is turned into a heuristic by partially exploring the branch-and-bound tree and only solving the pricing problem heuristically. Results will be presented for the vehicle routing problem with time windows, the pickup and delivery problem with time windows, the dial-a-ride problem, the vehicle routing problem with drones, the electric vehicle routing problem with time windows, and the vehicle routing problem with stochastic demand. The handling of the master problem and the cutting and branching are generic for all considered VRP types, while the pricing sub-problem heuristics are tailored for the problem at hand.