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 multiexchange neighborhood, which was recently introduced by Ahuja et al. [1], is a generalization of the more traditional twoexchange neighborhood. The twoexchange neighborhood of a solution comprises all the solutions which can be obtained from that solution by exchanging the assignment of two elements. Similarly, the multiexchange 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 multiexchange neighborhood can be prohibitively expensive. In order to reduce the computational effort needed to explore the neighborhood, the problem of detecting improving multiexchange 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 subsetdisjoint, meaning that they can not involve nodes associated to the same partition subset. Two major issues need to be addressed when implementing multiexchange 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 costdecreasing, subsetdisjoint cycles on the improvement graph. This problem, which is known to be NPcomplete on general graphs, can be approached in different ways, such as through variants of the wellknown labelcorrecting algorithm for shortest paths, or through implicit enumeration.
We have chosen two classes of wellknown and notoriuosly difficult location problems (which belong to the category of partitioning problems) to investigate the conceptual issues involved in the design of multiexchange algorithms: the Single Source Capacitated Facility Location Problem (SSCFLP) and the Capacitated Vertex pCenter Problem (CVPCP). These two classes of problems were chosen to provide evidences of the versatility of the multiexchange approach to handle problems with different objectives. SSCFLP, in fact, is characterized by a fixedcharged 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 multiexchange 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: singlecustomer multiexchanges, detected on a suitably defined customer improvement graph, and multicustomer multiexchanges, 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 costdecreasing solutions. Restart mechanisms are also considered to escape local optimality.
The multiexchange heuristic was tested on two varieties of benchmark instances available in the literature, and on a reallife 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: p1p71
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 1650 facility locations
and 50 customers, and 12 large instances, with 100 facility locations
and 1000 customers.
Download: cap61capc4
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 multiexchange 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: p1p24
Tables for set II: p25p40
Tables for set III: p41p55
Tables for set IV: p56p71
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: cap61cap131
Tables for the large problems: capa1capc4
Real data instance
Tables for the reallife 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 pmedian 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: p1p20
Benchmark Problems by Lorena
This set of problems was made available by Lorena for testing heuristics for the capacitated pmedian 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: SJC1SJC4b
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: G100p5G150p15
Benchmark Problems by Beasley
The quality of the solutions found by the multiexchange heuristics for this set of problems is validated by direct comparison with the optimal solutions obtained with the commercial CPLEX 7.0 mixedinteger optimizer.
Tables for the problems p1p20 (restricted relocation)
Tables for the problems p1p20 (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 SJC1SJC4b (restricted relocation)
Tables for the problems SJC1SJC4b (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 G100p5G150p15 (restricted relocation)
Tables for the problems G100p5G150p15 (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 multiexchange heuristic for the single source capacitated facility location problem. Management Science 50(6), 749760.
[3] J.E. Beasley (1990). ORLibrary: Distributing test problems by electronic mail. Journal of Operational Research Society, 41, 10691072.
[4] R.D. Galvao, C. ReVelle (1996). A Lagrangean heuristic for the maximum covering location problem. European Journal of Operational Research, 88, 114123.
[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, 544559.
[6] L.A.N. Lorena, E.L.F. Senne (2004). A column generation approach to capacitated pmedian problems. Computers and Operations Research, 31(6), 863876.
[7] M.P. Scaparra, S. Pallottino, M.G. Scutellà (2004). Large scale local search heuristics for the Capacitated Vertex pCenter Problem. Networks, 43(4), 241255.