Optimal Assignment of Shipments to Milk Runs for Just-in-Time Part Supply Under Uncertain Due Dates

We focus on a logistics service provider (LSP) that organizes the inbound logistics for an original equipment manufacturer (OEM) using just-in-time production. The LSP conducts periodic milk runs, that is, tours visiting a subset of suppliers on a fixed route to collect shipments bound for the OEM. Although the milk-run routes and rough schedules are fixed well in advance, the exact shipment due dates at the OEM become known only once the production sequence has been finalized. During daily operation, the given milk runs are executed such that shipments are picked up from the suppliers and delivered to the OEM ideally exactly just in time. However, the production sequence on the assembly lines at the OEM often changes on the day of execution, which alters shipment due dates at the OEM and makes it necessary to anticipate potential disturbances when assigning shipments to milk runs. We formulate a two-stage stochastic program, where, in the first stage, shipments are assigned to specific milk runs and, in the second stage, when alterations to the production sequence are revealed, arrival times are adjusted and shipments are express delivered if necessary. The assignment induces earliness–tardiness costs depending on the uncertain due date of each shipment at the OEM, and express deliveries induce fixed costs. Besides an extensive-form mixed-integer linear program, we develop a solution procedure based on the integer L-shaped method, enriched with valid inequalities and cuts derived from partial Benders decomposition and a subproblem relaxation. In a computational study on realistic test data, we show that the proposed L-shaped method solves 62 out of 70 instances to optimality. From a managerial perspective, we show that express deliveries are an effective way of mitigating uncertainty in the production sequence, as are overlapping milk-run routes, which are not yet widely used in practice but are relatively easy to implement. Funding: O. Jabali work is supported by Ministero dell’ Università e della Ricerca (MUR), PRIN 2022 project [20229ZWC97] – Revise and En-hance: Win-win INsights for home Delivery services (REWIND). Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0189 .