Minimizing maximum regret in two-stage facility location with site preparation costs

This is the authors' abstract. We don't add key points for this paper.

This paper introduces the two-stage capacitated facility location problem under demand and facility construction cost uncertainty with site preparation costs. In the first stage, the decision maker decides whether to pay site preparation costs to obtain an option for potential future utilization of a facility at each candidate site. In the second stage, after demand and facility construction costs are known, the decision maker decides whether to execute each option and construct a facility at each prepared site, and simultaneously allocates demands across the utilized facilities. We use a robust optimization framework with budgeted uncertainty sets to formulate a mixed-integer linear program and develop a column-and-constraint generation algorithm, incorporating a Benders decomposition approach, to solve the resulting minimax regret problem. We conduct numerical tests to identify the relationship between problem conditions and the optimal solution’s properties. We further examine the performance of the minimax regret solution evaluated against the minimax cost objective (and vice versa), and find that minimax cost solutions exhibit higher worst-case regret for instances with a large percentage of fixed cost associated with the first-stage decision and one of the following conditions: (a) small transportation cost, (b) large total facility cost, or (c) a large number of potential facilities. The minimax regret model appears to hedge against the potential regret of overinvestment in the first stage by preparing fewer facilities and increasing capacity utilization, at the expense of larger travel distances.