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 the transportation in each time period, and the objective is to plan inbound and outbound transportation along with inventory in each time period such that the overall inventory and transportation costs are
minimized. These problems belong to the class of two-echelon lot-sizing problems (2-ELS) with warehouse
and retailer as first- and second-echelons, respectively. We address an open question raised in van Hoesel,
Romeijn, Morales, Wagelmans [Management Science 51(11):1706-1719, 2005]: 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 [IIE Transactions 35(11):1065-1075, 2003] and Sargut and Romeijn [IIE
Transactions 39(11):1031-1043, 2007] for 2-ELS with a single capacitated vehicle for inbound transportation
and uncapacitated outbound transportation.