Employing an Effective Robust Optimization Approach for Cooperative Covering Facility Location Problem under Demand Uncertainty

Abstract

The traditional covering problem has two assumptions: “all or nothing coverage” and “individual coverage”. There are settings where the two assumptions may be unrealistic. In this research, we relax the two assumptions and study the cooperative covering facility location problem with demand uncertainty. Previous research on the covering problem has not considered cooperative covering under uncertain demand, particularly our approach to effectiveness maximization and offering full control of the conservatism of the model. We propose a cooperative covering model to maximize effectiveness, including the quality per dollar as a criterion. Then, the demand at each node is assumed to be uncertain, and the robust counterparts of the deterministic model are presented by considering the different degrees of conservatism of the robust solution. More importantly, the non-linear programming is transformed into equivalent linear programming by introducing auxiliary variables and using duality theory. The numerical examples show that the optimal location of the facility is affected by the protection level and the decision maker can make a trade-off between conservatism and effectiveness in an uncertain environment. Moreover, when the protection level is large, the objective function value makes a smaller sacrifice to get high robustness. In addition, two ways to measure the price of robustness are defined. The facility location decision can be made by evaluating the relative decrease in effectiveness compared to the nominal demand model or by evaluating the relative increase in effectiveness compared to the complete protection model.

Keywords

• linear programming
• budget-of-uncertainty robust approach
• the price of robustness
• effectiveness