Cost Function Approximation for the Dynamic Scheduled Service Network Design Problem

We consider a stochastic and dynamic variant of the service network design problem in which a logistics service provider (LSP) periodically routes shipments through a network of transshipment locations so that they all reach their destination on time. Consolidation of these shipments opens up potential cost savings for the LSP, but is made more difficult by the lack of knowledge about future shipments. We model the problem as a sequential decision process. To reduce computational complexity, we reformulate the decision space via intermediate destination nodes (IDNs), indicating feasible termination nodes in the time-expanded network. We combine the concept with a cost function approximation (CFA) term for each IDN to guide shipments toward those with high potential for future consolidation. We demonstrate both the superior performance of the CFA-based method compared with benchmark policies and the role IDN plays in that performance in an extensive computational study. For academics, we believe the ideas proposed in this paper form some of the first starting points for research on stochastic and dynamic service network design. For practitioners, the parameter values used in the CFA are easily computable and understandable. Funding: M. W. Ulmer’s work is funded by the German Research Foundation Deutsche Forschungsgemeinschaft Emmy Noether Programme [Grant 444657906]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0428 .