A statistical analysis of simulated annealing applied to the p-median problem

We present a statistical analysis of simulated annealing applied to the p-m edian problem. The algorithm we use combines elements of the vertex substit ution method of Teitz and Bart with the general methodology of simulated an nealing. The cooling schedule adopted incorporates the notion of temperatur e adjustments rather than just temperature reductions. Computational result s are given for test problems ranging from 100 to 900 vertices, retrieved f rom Beasley's OR-Library for combinatorial problems. Each problem was run f or a maximum of 100 different streams of random numbers. Optimal solutions were found for 26 of the 40 problems tested, although high optimum hitting rates were obtained for only 20 of them. The worst gap in relation to the o ptimal solution was 1.62%, after all runs for each of the test problems wer e computed.