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

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

• 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

[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.

Back to - Torna al O.R. Group of Pisa

Last updated: 12/10/2003