Tabu search for the discrete $(r|p)$-centroid problem

We consider the discrete $(r|p)$-centroid problem and develop a probabilistic tabu search algorithm for it. It is shown that probability of finding global optima with this algorithm converges to one as number of iterations grows if proper restrictions for Tabu list size are satisfied. We use Lagrangian relaxations for evaluation of the goal function's values. It is proved that this evaluation is not worse than linear program relaxation. Different methods of subgradient optimization are studied to solve the relaxed problem. The presented algorithm was tested on the benchmarks from the library “Discrete Location Problems”. Computational results show that the algorithm finds optimal solutions with high frequency. Ill. 4, tab. 5, bibliogr. 21.