A tight bound drop exchange algorithm for solving the p median problem

A drop algorithm is proposed for solving the <i>p </i>median problem. In solving for a fixed value of <i>p</i>, tight bounds on all other median solutions in the range <i>m</i>-1 to <i>p</i>+1 are generated where <i>m </i>is the number of possible location sites and <i>p </i>is the number of medians. A step by step numerical example is described, and extensive computational experience is reported for some standard sets of tests problems in the literature. Comparisons with the well-known greedy interchange heuristic confirm the effectiveness of this drop approach in solving a significant number of difficult median problems.