R. Simha et al., Simulated N-body: New particle physics-based heuristics for a Euclidean location-allocation problem, J HEURISTIC, 7(1), 2001, pp. 23-36
The general facility location problem and its variants. including most loca
tion-allocation and P-median problems. are known to be NP-hard combinatoria
l optimization problems. Consequently. there is now a substantial body of l
iterature on heuristic algorithms for a variety of location problems, among
which can be found several versions of the well-known simulated annealing
algorithm. This paper presents an optimization paradigm that, like simulate
d annealing, is based on a particle physics analogy but is markedly differe
nt from simulated annealing. Two heuristics based on this paradigm are pres
ented and compared to simulated annealing For a capacitated facility locati
on problem on Euclidean graphs. Experimental results based on randomly gene
rated graphs suggest that one of the heuristics outperforms simulated annea
ling both in cost minimization as well as execution time. The particular ve
rsion of location problem considered here, a location-allocation problem, i
nvolves determining locations and associated regions For a fixed number of
facilities when the region sizes are given. Intended applications of this w
ork include location problems with congestion costs as well as graph and ne
twork partitioning problems.