## 1 Introduction
[17] investigated the uncertain \(p\)-median problem, and developed an \(\alpha\)-reliable mean-excess model to minimize the expected regret. [PERSON] and [PERSON] [18] introduced the \(\beta\)-robust approach for the \(p\)-median problem with uncertainties, which can be used to obtain a trade-off between the expected transportation cost/distance and the robustness. The \(\beta\)-robust approach for facility location integrates the advantages of both the stochastic and robust optimization methods. Then, [PERSON] and [PERSON] [19] further studied the \(\beta\)-robust facility relocation problem under budget constraint. [PERSON] and [PERSON] [20] employed both ant colony optimization and the GA to solve a tactical production-distribution planning problem in an uncertain environment. In most of the studies on robust facility location, in order to estimate the regrets under different scenarios, the optimal solutions for all scenarios should be first obtained. The instance under each scenario usually corresponds to a kind of classical facility location problem, which is NP-hard. The solving of each scenario problem has to employ approximate heuristics such as the GA and Lagrangian heuristic [21], which is time-consuming. When the number of scenarios is lower, all of the instances can be solved through iteratively running an approximate heuristic. For example, nine scenarios were included in the experiments of both [18; 19]. However, in many practical situations, the uncertainties have to be modeled as a larger number of scenarios, which means that the computational time would be unaffordable by iteratively running traditional methods. Motivated by the requirement of efficiently solving the \(\beta\)-robust \(p\)-median problem with a large number of possible scenarios, a novel multi-scenario cooperative evolutionary (MSCE) metaheuristic was proposed. The definition of the neighborhood scenario was introduced, which was used to describe scenarios similar to each other. The major contribution of the MSCE algorithm is to utilize the knowledge obtained in the solutions of neighborhood scenarios. As all of the scenarios are used to model the uncertainties in a \(p\)-median problem, there are some similarities between these scenarios. The basic observation is that the optimal solution of a scenario is close to another scenario, if these two scenarios have higher similarities. Thus, the knowledge obtained in the solving of a scenario is helpful to the solving of its neighborhood scenarios. There are two advantages of the MSCE algorithm compared to other approximate heuristics. First, all scenarios are solved parallelly in one run of the MSCE algorithm, which improves the efficiency of computational time. Second, in the parallel search process of MSCE, helpful knowledge is exchanged among neighborhood scenarios for a certain number of iterations, which improves the performance in both optimality and efficiency. The rest of this paper is organized as follows. The model methodology is presented in Section 2. Section 3 proposes the MSCE algorithm and Section 4 presents the computational experiments. Finally, the paper is concluded in Section 5.