A stochastic multi-stage fixed charge transportation problem: Worst-case analysis of the rolling horizon approach

作者：Bertazzi Luca^*; Maggioni Francesca

来源：European Journal of Operational Research, 2018, 267(2): 555-569.

DOI：10.1016/j.ejor.2017.12.004

• Logistics
• Fixed charge transportation problem
• Multi-stage stochastic programming
• Rolling horizon
• Worst-case analysis

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.

• 出版日期2018-6-1