Sequential approximate approach to the p-median problem

• We study the public service system design formulated as the p-median problem.
• We focus on the approximate radial approach using dividing points.
• To improve the accuracy, a sequential method is introduced.
• Presented approach enables simple implementation in common optimization software.
• The proposed method is a suitable complement to the state-of-the-art methods.

This paper deals with the problem of designing the optimal structure of most public service systems, which is often formulated as the p-median problem. The real instances of these problems are characterized by a considerably big number of possible service center locations, which can take the value of several thousands. Current exact approaches must face up to a big demand on computational time and they often fail when a large instance is being solved. This paper is focused on the approximate approach based on specific model reformulation. It uses the approximation of a common distance by some pre-determined distances given by so-called dividing points. The deployment of the dividing points influences the solution accuracy. To improve this approach, we have developed the sequential method of dividing points deployment. Hereby, we study the accuracy of the suggested method using the upper and lower distance approximations in comparison to the saved computational time.