E-Commerce Order Fulfillment Problem with Limited Time Window.

The article focuses on optimizing the middle-mile order fulfillment process in e-commerce under limited logistical capacity constraints. It develops a stochastic dynamic programming model and proposes two heuristic policies—scaled Lagrangian relaxation (sLR) and threshold Lagrangian relaxation (tLR)—based on Lagrangian relaxation to approximate the optimal fulfillment strategy. The tLR policy prioritizes orders by discounted penalty costs and dynamically manages warehouse allocations to respect capacity thresholds, achieving asymptotic optimality as the number of demand locations grows. Numerical experiments using synthetic and real data from a North American electronics retailer demonstrate that the tLR policy outperforms benchmarks, highlighting the benefits of multiperiod fulfillment windows and strategic order postponement. The findings suggest practical implications for e-commerce firms in managing fulfillment options and logistics capacity, such as offering "two-day fulfillment" services to alleviate capacity constraints.