A Variable Neighborhood Search Approach to the p-Median Problem with Balanced Constraints

Abstract

This study considers p-median problem with balanced constraints (p-MBC) that represents a variant of the well-known p-median problem. The goal of p-MBC is to choose p medians from the given set of nodes and to assign each node to exactly one median, such that the total distance between the nodes and the corresponding medians is minimized. In addition, it is required that the allocations of nodes to medians must be balanced with respect to some measures of activity. In this study, a Variable Neighborhood Search (VNS) is proposed as a metaheuristic approach to p-MBC. The VNS method is evaluated on small and medium size problem instances from the literature and on the set of newly generated large size instances. The obtained computational results show that proposed VNS quickly reaches all known optimal solutions and provides high quality solutions on large size problem instances unsolved to optimality by exact solver.