  Metaheuristics are known to be strong in solving large-scale instances of
computationally hard problems. However, their efficiency still needs
exploration in the context of instance structure, scale and numerical
properties for many of these problems. In this paper, we present an in-depth
computational study of two local search metaheuristics for the classical
uncapacitated facility location problem. We investigate four problem instance
models, studied for the same problem size, for which the two metaheuristics
exhibit intriguing and contrasting behaviours. The metaheuristics explored
include a local search (LS) algorithm that chooses the best moves in the
current neighbourhood, while a randomised local search (RLS) algorithm chooses
the first move that does not lead to a worsening. The experimental results
indicate that the right choice between these two algorithms depends heavily on
the distribution of coefficients within the problem instance. This is also put
further into context by finding optimal or near-optimal solutions using a
mixed-integer linear programming problem solver. Since the facility location
problem is a relatively simple example of a choice-and-assignment problem,
similar phenomena are likely to be discovered in a number of other, possibly
more complex computational problems in science and engineering.
