Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6894997 | European Journal of Operational Research | 2018 | 39 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Luca Bertazzi, Francesca Maggioni,