We study serial supply chain problems where a product is transported from a supplier to a warehouse (inbound transportation), and then from the warehouse (outbound transportation) to a retailer such that demand for a given planning horizon is satisfied. We consider heterogeneous vehicles of varying capacities for transportation in each time period, and the objective is to plan inbound and outbound transportation along with inventory in each time period so that overall inventory and transportation costs are minimized. These problems belong to the class of two-echelon lot-sizing (2-ELS) problems with the warehouse and retailer as the first and second echelons, respectively. We address an open question raised in van Hoesel et al. van Hoesel S, Romeijn HE, Morales DR, Wagelmans APM (2005) Integrated lot sizing in serial supply chains with production capacities. Management Sci. 51(11):1706–1719: Does there exist a polynomial-time algorithm for 2-ELS with a single capacitated vehicle for each of the inbound and outbound transportation? Specifically, we introduce polynomial-time algorithms for this problem and its three generalizations with multiple capacitated vehicles for inbound and/or outbound transportation, thereby generalizing the results of Kaminsky and Simchi-Levi Kaminsky P, Simchi-Levi D (2003) Production and distribution lot sizing in a two stage supply chain. IIE Trans. 35(11):1065–1075 and Sargut and Romeijn Sargut FZ, Romeijn HE (2007) Capacitated production and subcontracting in a serial supply chain. IIE Trans. 39(11):1031–1043 for 2-ELS with a single capacitated vehicle for inbound transportation and uncapacitated outbound transportation. We showcase the practical applications of these approaches in efficiently solving discrete two- and multiechelon lot-sizing problems that arise in freight transportation, the international shipping industry, and the tire manufacturing industry. Based on our computational experiments, we observe that the algorithm for discrete 2-ELS with a capacitated vehicle for inbound and outbound transportation is computationally efficient in comparison with solving the mixed binary formulations of two- and multiechelon lot-sizing problems using an off-the-shelf optimization solver. This paper was accepted by Chung Piaw Teo, optimization and decision analytics. Funding: This work was supported by the Division of Civil, Mechanical and Manufacturing Innovation of National Science Foundation Grants 1824897 and 2034503. Supplemental Material: The data files are available at https://doi.org/10.1287/mnsc.2022.04106 .
Kulkarni et al. (Wed,) studied this question.