The p-Median Problem - Location Science - page 29

concentration algorithm for the p -median problem. The idea is to generate a number
of good solutions based on randomized starting solutions. A subset of the nodes
that are selected in the various runs is then used to reduce the number of location
variables in formulation ( 2.1 )-( 2.6 ) above. In other words, the concentration set, or
the set of candidate sites, is reduced from

to a smaller set consisting of a subset of
the nodes selected as facilities in the various randomized runs.
Heuristic concentration is based on eliminating some of the location variables.
Church ( 2008 ) proposed the BEAMR approach which attempts to eliminate some of
the assignment variables. BEAMR attempts to utilize only the h j closest assignment
variables for each demand node. To ensure feasibility, the model also includes
a variable for each demand node allowing the assignment to a dummy facility
further than the h j closest candidate facilities. This assignment does not need
to satisfy constraints ( 2.4 ). The resulting model provides a lower bound on the
objective function value for the p -median problem. An upper bound can be found
by simply assigning every demand node to the nearest of the selected facility
sites. If the bounds are not close enough, then some of the h j values can be
increased, particularly for those nodes for which assignment to one of the nearest
h j candidate sites was not possible. The algorithm typically results in provably
optimal solutions using a fraction of the constraints and variables of the original
formulation ( 2.1 )-( 2.6 ).
Rosing et al. ( 1998 ) compared heuristic concentration to tabu search in problems
with 100 and 200 demand nodes and candidate sites. Heuristic concentration found
the optimal (or best known) solution in 17 of the 21 test cases, while tabu search
found the optimal (or best known) solution in only two cases.
Mladenovic and Hansen ( 1997 ) introduced a variable neighborhood search
algorithm. Hansen and Mladenovi´c( 1997 ) applied this algorithm to the p -median
problem. They found that variable neighborhood search outperformed both a greedy
interchange algorithm and two different tabu search-based algorithms.
Hansen and Mladenovi´c( 2001 ) reviewed the basics of variable neighborhood
search algorithms and compared a variety of metaheuristic algorithms, including
variable neighborhood search for the 12 largest of the 40 Beasley instances. They
found that variable neighborhood search and heuristic concentration outperformed
tabu search and a greedy interchange algorithm. Variable neighborhood search was
slightly better than heuristic concentration.

J

2.5.3 A Lagrangian Heuristic for the p-Median Problem

In this subsection, we outline a Lagrangian relaxation algorithm to the p -median
problem. The advantage of Lagrangian relaxation over any heuristic approach is
twofold. First, at every iteration of the Lagrangian procedure we obtain lower and
upper bounds on the objective function value. Second, the Lagrangian procedure can
readily be embedded in a branch-and-bound algorithm to obtain provably optimal
solutions.