Multi-Objective Variable Neighborhood Search to Solve the Problem of Partitioning of Spatial Data with Population Characteristics

Abstract

The problem of partitioning is NP hard and has been studied extensively for several reasons including vulnerability to obtain local optima. For partitioning problems in combinatorial optimization, several works have proposed the inclusion of heuristics in order to achieve global optima. There have been made many efforts to solve the partitioning problem and find good solutions when the discrete optimization process optimizes a single objective. However, the partitioning problem with more than one goal has not been addressed due to the difficulty of obtaining the set of efficient optimal and non-dominated solutions. This paper presents the multi-objective partitioning problem with two objectives: minimization of distances and of census variables. The designed partitioning algorithm is an extension of the geographic cluster that optimizes only one objective. In this work, we used Variable Neighborhood Search (VNS) to escape local optima, and to obtain the set of non-dominated solutions, our methodology takes advantage of the properties of the set Maxima.