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

Area of Science:

• Operations Research
• Computational Optimization
• Spatial Analysis

Background:

• The p-median problem aims to optimize facility location by minimizing average distances between sources and destinations.
• Heuristic algorithms are commonly used to address this complex facility location problem.

Purpose of the Study:

• To comprehensively evaluate existing heuristic algorithms for the p-median problem.
• To analyze the impact of destination spatial distribution and problem scale on algorithm performance.
• To assess algorithm effectiveness for real-world applications like bio-emergency resource distribution.

Main Methods:

• Evaluation of classic heuristic algorithms using synthetic and real-world datasets.
• Performance metrics include objective function value, solution time, and solution stability.
• Analysis of algorithm sensitivity to destination distribution and problem size.

Main Results:

• Interchange algorithms demonstrate high-quality solutions concerning execution time and cost.
• These algorithms exhibit greater stability, particularly with clustered destination distributions.
• Performance is sensitive to spatial distribution and problem scale across evaluated metrics.

Conclusions:

• Interchange algorithms are recommended for the p-median problem due to their efficiency and stability.
• Understanding the influence of spatial data is crucial for selecting appropriate facility location algorithms.
• The findings are applicable to practical scenarios such as optimizing emergency resource deployment.