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].
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.
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
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.
![]() |
![]() |
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.
![]() |
![]() |
![]() |
![]() |
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
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)
[2] R.K. Ahuja, J.B. Orlin, S. Pallottino, M.P. Scaparra, M.G. Scutellà (2004). A multi-exchange heuristic for the single source capacitated facility location problem. Management Science 50(6), 749-760.
[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.