View in EDS

Branch-price-and-cut for the production routing problem with time windows.

Saved in:
Bibliographic Details
Title: Branch-price-and-cut for the production routing problem with time windows.
Authors: Fauß, Eric1 (AUTHOR) eric.fauss@rptu.de, Gschwind, Timo1 (AUTHOR) gschwind@rptu.de
Source: OR Spectrum. Jun2026, Vol. 48 Issue 2, p627-668. 42p.
Subjects: Vehicle routing problem, Optimization algorithms, Constraint satisfaction, Mathematical optimization, Mathematical models, Inventory control, Economic lot size
Abstract: Production routing problems (PRPs) are integrated planning problems that combine vehicle routing and lot-sizing decisions. Given a discrete finite time horizon and a set of customers, the basic PRP consists of deciding for each period if and how much to produce, the inventories at the supplier and the customers, and the vehicle routes. The latter include the decisions on which customers to serve and the quantities delivered. The objective is to minimize the total cost over the planning horizon consisting of production, inventory, and routing cost. In this paper, we consider the PRP with time windows (PRPTW) and propose a branch-price-and-cut (BPC) algorithm for its solution. The BPC relies on a path-based formulation that explicitly specifies which demands are satisfied by which deliveries and employs several families of valid inequalities. The performance of the BPC is assessed in an extensive computational study on existing benchmark instances for the related inventory routing problem with time windows (IRPTW) and newly created instances for the PRPTW. Our BPC outperforms the current state-of-the-art BPC for the IRPTW, closing 62 previously open instances. Finally, we derive managerial insights from our PRPTW instances. [ABSTRACT FROM AUTHOR]
Copyright of OR Spectrum is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Production routing problems (PRPs) are integrated planning problems that combine vehicle routing and lot-sizing decisions. Given a discrete finite time horizon and a set of customers, the basic PRP consists of deciding for each period if and how much to produce, the inventories at the supplier and the customers, and the vehicle routes. The latter include the decisions on which customers to serve and the quantities delivered. The objective is to minimize the total cost over the planning horizon consisting of production, inventory, and routing cost. In this paper, we consider the PRP with time windows (PRPTW) and propose a branch-price-and-cut (BPC) algorithm for its solution. The BPC relies on a path-based formulation that explicitly specifies which demands are satisfied by which deliveries and employs several families of valid inequalities. The performance of the BPC is assessed in an extensive computational study on existing benchmark instances for the related inventory routing problem with time windows (IRPTW) and newly created instances for the PRPTW. Our BPC outperforms the current state-of-the-art BPC for the IRPTW, closing 62 previously open instances. Finally, we derive managerial insights from our PRPTW instances. [ABSTRACT FROM AUTHOR]
ISSN:01716468
DOI:10.1007/s00291-026-00850-5