A Branch-and-Price-and-Cut Algorithm for a Vehicle Routing Problem: an Industrial Case Study

Efficient vehicle routing is a fundamental challenge in modern logistics, directly impacting operational costs, resource utilization, and customer satisfaction. This thesis presents a solver for a Capacitated Vehicle Routing Problem with soft time windows, staggered departure times, time dependent travel times and compatibility constraints under several optimization objectives. An exact branch-and-price-and-cut algorithm is developed, using both heuristic and exact labelling schemes and several recent techniques from the literature. The MILP solver is coupled with a memetic algorithm that provides high-quality initial solutions. The effectiveness of the proposed methodology is evaluated through a case study based on real-world industrial data.