A Clustering-Based Surrogate-Assisted Multiobjective Evolutionary Algorithm for Shelter Location Problem Under Uncertainty of Road Networks

摘要

The shelter location is very important for evacuation planning in natural disasters, and evolutionary algorithms (EAs) have demonstrated their effectiveness in solving this challenging problem. However, few EAs have been reported focusing on the shelter location problem under uncertainty of road networks due to the expensive cost of calculating the evacuation distance for individual evaluation. To address this issue, in this article, we propose a clustering-based surrogate-assisted multiobjective EA, termed AR-MOEA+SA, in the framework of a recently developed EA AR-MOEA. In AR-MOEA+SA, a surrogate model, the radial basis function (RBF), is adopted to approximately calculate the evacuation distance under uncertainty of road networks. Due to the fact that there often exist a large number of communities needing to be considered in shelter location, a clustering strategy is suggested to convert the surrogate of high-dimensional problem into the one of low-dimensional problem in the proposed AR-MOEA+SA for efficiently building the RBF network. A population initialization strategy is also suggested in AR-MOEA+SA to enhance the quality of training data in the early stages of evolution. Experimental results on a variety of test instances demonstrate the superiority of the proposed AR-MOEA+SA over the original version of AR-MOEA in terms of both computational efficiency and solution quality.