A trajectory based heuristic for the planar p-median problem

This paper presents a novel approach for solving the planar p-median problem. A sub-class of the distributed p-median problem (Brimberg et al., 2021) is identified that allows a continuous trajectory of local optima to be constructed as a parameter α decreases from 1 to 0. The trajectory converges to a local optimum of the planar p-median problem as α approaches 0. Computational results are very encouraging. For larger instances tested, the proposed trajectory method finds better solutions in a small fraction of the time taken by a conventional multi-start local search. The methodology is readily extended to continuous p-median problems in higher dimensional spaces.