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

The authors 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, the authors propose an exact branch-price-and-cut algorithm. The authors 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, the authors' 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, the authors 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.The online appendices are available at https://doi.org/10.1287/trsc.2018.0854.

  • Record URL:
  • Availability:
  • Supplemental Notes:
    • Abstracts reprinted with permission of INFORMS (Institute for Operations Research and the Management Sciences, http://www.informs.org).
  • Authors:
    • Dayarian, Iman
    • Desaulniers, Guy
  • Publication Date: 2019-5


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01714946
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 17 2019 3:36PM