A Stochastic Multi-stage Fixed Charge Transportation Problem: Worst-Case Analysis of the Rolling Horizon Approach

We introduce a stochastic multi-stage fixed charge transportation problem, in which a producer has to satisfy an uncertain demand within a deadline. At each time period, a fixed transportation cost can be paid to buy a transportation capacity. If the transportation capacity is used, the supplier also pays an uncertain unit transportation cost. A unit inventory cost is charged for the unsatisfied demand. The aim is to determine the transportation capacities to buy and the quantity to send at each time period in order to minimize the expected total cost. We prove that this problem is NP-hard, we propose a multi-stage stochastic optimization model formulation, and we determine optimal policies for particular cases, with deterministic unit transportation costs or demand and zero fixed costs. Furthermore, we provide the worst–case analysis of the rolling horizon approach, a classical heuristic approach for solving multi-stage stochastic programming models, applied to this NP-hard problem and to polynomially solvable particular cases. Worst–case results show that the rolling horizon approach can be very suboptimal. We also provide experimental results.