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

Iman Dayarian () and Guy Desaulniers ()
Additional contact information
Iman Dayarian: Department of Information Systems, Statistics, and Management Science, Culverhouse College of Business, University of Alabama, Tuscaloosa, Alabama 35487
Guy Desaulniers: GERAD, Polytechnique Montréal, Montreal, Quebec H3T 2A7, Canada; Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montreal, Quebec H3T 2A7, Canada

Transportation Science, 2019, vol. 53, issue 3, 829-849

Abstract: 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. The online appendices are available at https://doi.org/10.1287/trsc.2018.0854 .

Keywords: catering services; short-life-span products; production-routing problem; branch-price-and-cut; branching rule (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0854 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:3:p:829-849

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().