An experimental analysis of the p-median problem under uncertainty: an evolutionary algorithm approach

Facility location under uncertain environments is an important and challenging problem. The problem deals with the optimal placement of facilities that serve a set of spatially distributed nodes. One way to deal with this problem is to model uncertainty by means of scenarios and to optimise some robustness criteria such as the average and maximum regrets over these scenarios. We propose to model the robust design as a bi-objective optimisation problem and to use a well-known multi-objective evolutionary algorithm, the NSGA-II, to solve it. We also propose to use the bi-objective optimisation framework to analyse the effects of variations in the number of facilities to install, and of nodes to be served, on the quality of the Pareto solutions. Computational experiments show that the proposal can be used to design robust solutions and to study the effects of changes in the system parameters on the quality of the generated solutions. [Received 23 June 2012; Revised 15 November 2012; Revised 23 January 2013; Accepted 28 February 2013]