Last update: 08/11/2021 (the original page has been moved to the CommaLAB web site, although a redirect has been kept)
The online supplement of papers [2] and [7] (cf. the Bibliography) is available here.
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 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 with 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.
Here two classes of well-known and notoriouosly difficult location problems (which belong to the category of partitioning problems) are considered: the Single Source Capacitated Facility Location Problem (SSCFLP) and the Capacitated Vertex p-Center Problem (CVPCP). These two classes of problems 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 and some benchmark instances. 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
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
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à (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.