Multi-Exchange Heuristics for some Capacitated Facility
Location Problems
Exchange neighborhood structures play a leading role in the design of local
search algorithms for solving hard combinatorial optimization problems. In
particular, they are suitable for solving partitioning problems, i.e.
problems whose solutions can be represented as partitions of elements. The
multi-exchange neighborhood, which was recently introduced by Ahuja
et al. [1], is a generalization of the more traditional two-exchange
neighborhood. The two-exchange neighborhood of a solution comprises all
the solutions which can be obtained from that solution by exchanging the
assignment of two elements. Similarly, the multi-exchange neighborhood is
induced by an exchange of elements, but this time the exchange can involve
more than two elements, which are moved in a cyclic manner among the
partition subsets. Each cyclic transfer generates a neighbor of the current
solution. It is easy to see that the number of neighbors of a solution is
exponentially large and hence the search of an improving solution in the
multi-exchange neighborhood can be prohibitively expensive. In order to
reduce the computational effort needed to explore the neighborhood, the
problem of detecting improving multi-exchange moves is reformulated as the
problem of identifying special cycles on a suitably defined improvement
graph. Network optimization techniques are then used to efficiently
identify such cycles. The peculiarity of these cycles is that they must be
subset-disjoint, meaning that they can not involve nodes associated to the
same partition subset. Two major issues need to be addressed when
implementing multi-exchange local search algorithms:
- how to build the improvement graph, which implies assigning particular
significance to nodes and arcs, identifying feasible arcs with respect to
the problem constraints, and defining the arc costs;
- how to efficiently find cost-decreasing, subset-disjoint cycles on the
improvement graph. This problem, which is known to be NP-complete on
general graphs, can be approached in different ways, such as through
variants of the well-known label-correcting algorithm for shortest paths,
or through implicit enumeration.
We have chosen two classes of well-known and notoriuosly difficult location
problems (which belong to the category of partitioning problems) to
investigate the conceptual issues involved in the design of multi-exchange
algorithms: the Single Source Capacitated Facility Location Problem
(SSCFLP) and the Capacitated Vertex p-Center Problem (CVPCP). These
two classes of problems were chosen to provide evidences of the versatility
of the multi-exchange approach to handle problems with different
objectives. SSCFLP, in fact, is characterized by a fixed-charged
objective, whereas CVPCP present a minimax objective.
Below, we provide a brief outline of the methodology, some benchmark
instances, and the computational results for the two problems.
For detailed explanations concerning the algorithms design and
implementation, the reader is referred to the companion papers [2] and [7].
Multi-exchange heuristics for the single source capacitated facility
location problem
Solution Method Outline
The multi-exchange heuristic for the Single Source Capacitated Facility
Location Problem consists in the alternating use of customer exchanges and
facility moves. Two different kinds of customer exchanges are considered:
single-customer multi-exchanges, detected on a suitably defined customer
improvement graph, and multi-customer multi-exchanges, detected on a
facility improvement graph dynamically built through the use of a
greedy scheme. Whereas customer exchanges mainly affect the customer
assignment among facilities already located, the facility moves are
specifically designed to find improving configurations of the open
facilities. The neighborhood structures thus obtained are embedded in a
local improvement algorithm which starts with a feasible solution and
alternatively performs improving customer and facility moves to produce
cost-decreasing solutions. Restart mechanisms are also considered to escape
local optimality.
Benchmark Instances
The multi-exchange heuristic was tested on two varieties of benchmark
instances available in the literature, and on a real-life instance
provided by an Italian cookie factory.
Benchmark Problems by Holmberg et al.
This set of problems was randomly generated by Holmberg et al. [5] and
comprises four subsets of problems. The test problems in each subset differ for
the distributions of the inputs and for the size, which ranges from 50
to 200 customers, and from 10 to 30 candidate facility locations.
Download: p1-p71
Benchmark Problems by Beasley
This set of problems is part of the data set collection provided by
Beasley [3] for the capacitated warehouse location problem. We only
performed our experimentation on the instances which are feasible for
SSCFLP, namely 24 medium sized instances with 16-50 facility locations
and 50 customers, and 12 large instances, with 100 facility locations
and 1000 customers.
Download: cap61-capc4
Real data instance
This data instance was provided by an Italian cookie factory, and
includes 23 facility locations and 104 customers.
Download: Cookie Factory Data
Computational Results
In the following, we report for each problem set the computational results
obtained by three different implementations of the multi-exchange
heuristic, denoted as bfs, dfs and bfs. Each file (in
PDF format) contains the result tables relative to different values of the
parameters K and p. For additional information about the
three implementations and the meaning of the parameters, the reader is
referred to [2].
-
Benchmark Problems by Holmberg et al.
Tables for set I: p1-p24
Tables for set II: p25-p40
Tables for set III: p41-p55
Tables for set IV: p56-p71
The graphs provided below show the impact of the parameter K on
the solution quality, as measured by average percentage deviation,
for the IV set of problems and for two different values of the
parameter p.
Fig.1. Avg. % deviation as a function of K for problem set IV. p =
10.
|
Fig.2. Avg. % deviation as a function of K for problem set IV. p =
5.
|
Benchmark Problems by Beasley
Tables for the medium problems: cap61-cap131
Tables for the large problems: capa1-capc4
Real data instance
Tables for the real-life problem: cookie
factory
The results obtained for this problem can
be better visualized in the graphs provided below, which show how the percent
deviations and the execution times vary as a function of the parameter K.
Fig.3. Avg. % deviation as a function of
K. p = 10
|
Fig.4. Avg. % deviation as a function of
K. p = 5
|
Fig.5. Execution time as a function of
K. p = 10
|
Fig.6. Execution time as a function of
K. p = 5
|
Multi-exchange heuristics for the capacitated vertex p-center
problem
Solution Method Outline
In order to design multi-exchange based heuristics for CVPCP, we propose a
new way of defining the customer improvement graph. We employ two
alternative notions of move profitability, and propose several cycle
detection heuristics for finding profitable moves. Also, we show how a
recentering operation can be embedded in the cycle search heuristics to
improve the performance of the overall methodology. Finally, we allow
facility location adjustments through the use of relocation mechanisms,
which optimally relocate a facility relatively to a given subset of
customers.
Benchmark Instances
The multi-exchange heuristic for CVPCP was tested on three sets of benchmark
instances.
Benchmark Problems by Beasley
This set of problems is part of the data set collection provided by
Beasley [3] for the capacitated p-median problem. It comprises 2 groups
of 10 instances, with 50 demand nodes and 5 facilities to be located,
and 100 nodes and 10 facilities, respectively.
Download: p1-p20
Benchmark Problems by Lorena
This set of problems was made available by Lorena for testing
heuristics for the capacitated p-median problem [6]. It comprises real
data referring to the central area of Sao Jose dos Campos City. The
set includes 6 large instances ranging from 100 to 402 customers, and
from 10 to 40 centers.
Download: SJC1-SJC4b
Benchmark Problems by Galvao and ReVelle
The two problems in this set were randomly generated by Galvao and ReVelle
for the maximal covering location problem. Since the original data files,
with 100 and 150 nodes respectivelly, did not contain information about the
location capacities, we generated the capacities for each problem in two
different ways. The first way assigns equal capacity to each site. The
second way assigns to each location one of 3 possible capacity values (low,
medium and high) with probability 0.4, 0.4 and 0.2 respectivelly. In both
cases, the capacity values were chosen by taking into account the number of
centers p, so that in the resulting problems the capacities were
neither too low (unfeasible) or too high (trivial). For each problem and
for each capacity pattern, we considered two values of p, thus
obtaining a total number of 8 instances for this set.
Download: G100p5-G150p15
Computational Results
In the following, we report for each problem set the computational results
obtained by different combinations of the implementation options. In
particular, each table compares the results obtained with the four cycle
detection heuristics, denoted as 1S, tS, 1B and
tB. Each file (in PDF format) contains the result tables for each
combination of the two restart mechanisms, the three recentering operations
and the three implementations of the set of candidate nodes Q. For
each problem set, we provide two similarly structured files of results,
which refer respectivelly to the restricted relocation mechanism (our
original relocation strategy) and to the more general relocation mechanism
(the relocation extension suggested by an anonymous referee). For
additional information about the different implementation options, the
reader is referred to [7].
-
Benchmark Problems by Beasley
The quality of the solutions found by the multi-exchange heuristics for
this set of problems is validated by direct comparison with the optimal
solutions obtained with the commercial CPLEX 7.0 mixed-integer
optimizer.
Tables for the problems p1-p20 (restricted relocation)
Tables for the problems p1-p20 (relocation)
-
Benchmark Problems by Lorena
For these large scale problems, it was not possible to find
satisfactory solutions with CPLEX within a reasonable computational
time. The percent deviation for this set was hence computed with
respect to the best solution found by some implementation of our heuristics.
Tables for the problems SJC1-SJC4b (restricted relocation)
Tables for the problems SJC1-SJC4b (relocation)
-
Benchmark Problems by Galvao and ReVelle
For this set, the percent deviation was computed with respect to the
best solutions found by CPLEX. Note that for the largest problems (the
one with 150 nodes) the optimality of the solutions was not
proved within the maximum execution time we allowed (48 hours). Those
problems are indicated in the tables with an asterisk.
Tables for the problems G100p5-G150p15 (restricted relocation)
Tables for the problems G100p5-G150p15 (relocation)
Some additional tests are also reported for two problems characterized by
p/n ratios larger than 10%.
Tables for the problems G100p15,G150p20 (restricted relocation)
Tables for the problems G100p15,G150p20 (relocation)
Bibliography
[1] R.K. Ahuja, J.B. Orlin, D. Sharma (2000). Very large-scale
neighborhood search. International Transactions in Operational
Research, 7, 301-317.
[2] R.K. Ahuja, J.B. Orlin, S. Pallottino, M.P. Scaparra,
M.G. Scutellà (2002). A multi-exchange heuristic for the single source
capacitated facility location problem. Technical Report 02-11, Dip. di
Informatica, Università di Pisa (to appear in Management Science).
[3] J.E. Beasley (1990). OR-Library: Distributing test problems by
electronic mail. Journal of Operational Research Society, 41,
1069-1072.
[4] R.D. Galvao, C. ReVelle (1996). A Lagrangean heuristic for the
maximum covering location problem. European Journal of Operational
Research, 88, 114-123.
[5] K. Holmberg, M. Ronnqvist, D. Yuan (1999). An exact algorithm for
the capacitated facility location problem with single
sourcing. European Journal of Operational Research, 113,
544-559.
[6] L.A.N. Lorena, E.L.F. Senne (2004). A column generation approach
to capacitated p-median problems. Computers and Operations
Research, 31(6), 863-876.
[7] M.P. Scaparra, S. Pallottino, M.G. Scutellà (2004). Large scale
local search heuristics for the Capacitated Vertex p-Center Problem.
Networks, 43(4), 241-255.
Last updated: 12/10/2003