Group for Research in Decision Analysis


A Branch-Price-and-Cut algorithm for a production-routing problem with short-lifespan 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 datasets show the effectiveness of this branching rule. Overall, our algorithm is able to solve instances with up to 25 orders and 4 products in less than 3 hours of computational time.

, 29 pages