Evaluation of Heuristics for the P-Median Problem: Scale and Spatial Demand Distribution

The objective of the p-median problem is to identify p source locations and map them to n destinations while minimizing the average distance between destinations and corresponding sources. Several heuristic algorithms have been developed to solve this general class of facility location problems. In this study, we add to the current literature in two ways: (1) we present a thorough evaluation of existing classic heuristics and (2) we investigate the effect of spatial distribution of destination locations, and the number of sources and destinations on the performance of these algorithms for varying problem sizes using synthetic and real datasets. The performance of these algorithms is evaluated using the objective function value, time taken to achieve the solution, and the stability of the solution. The sensitivity of existing algorithms to the spatial distribution of destinations and scale of the problem with respect to the three metrics is analyzed in the paper. The utility of the study is demonstrated by evaluating these algorithms to select the locations of ad-hoc clinics that need to be set up for resource distribution during a bio-emergency. We demonstrate that interchange algorithms achieve good quality solutions with respect to both the execution time and cost function values, and they are more stable for clustered distributions.