A Branch-Price-and-Cut Algorithm for a Production-Routing Problem with Short-Life-Span Products

We study a rich production-routing problem with time windows arising at a catering services company. The production part consists of assembling the meals to deliver. It considers release times to ensure freshness of the products to be delivered and is also restricted by due times incurred by the constructed routes. Production employee shifts together with a compatible production schedule must be determined. The routing part consists of building vehicle routes that can contain multiple trips and must satisfy customer time windows and vehicle capacity. Routing and production costs, including a guaranteed minimum paid time for the drivers and the production employees, are minimized under various constraints. To solve this complex problem, we propose an exact branch-price-and-cut algorithm. We introduce a new branching rule that imposes on one branch a lower bound on the production costs. Computational results obtained on instances derived from real-world data sets show the effectiveness of this branching rule. Overall, our algorithm is able to solve to optimality instances with up to 25 orders and four products in less than two hours of computational time. To tackle larger instances involving up to 50 orders, we turn the proposed algorithm into a heuristic by avoiding a complete enumeration of the search tree and develop two other matheuristics based on this branch-price-and-cut heuristic.