Robust Optimization for Empty Repositioning Problems

We develop a robust optimization framework for dynamic empty repositioning problems modeled using time-space networks. In such problems, uncertainty arises primarily from forecasts of future supplies and demands for assets at different time epochs. The proposed approach models such uncertainty using intervals about nominal forecast values and a limit on the systemwide scaled deviation from the nominal forecast values. A robust repositioning plan is defined as one in which the typical flow balance constraints and flow bounds are satisfied for the nominal forecast values, and the plan is recoverable under a limited set of recovery actions. A plan is recoverable when feasibility can be reestablished for any outcome in a defined uncertainty set. We develop necessary and sufficient conditions for flows to be robust under this definition for three types of allowable recovery actions. When recovery actions allow only flow changes on inventory arcs, we show that the resulting problem is polynomially solvable. When recovery actions allow limited reactive repositioning flows, we develop feasibility conditions that are independent of the size of the uncertainty set. A computational study establishes the practical viability of the proposed framework.