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:

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.

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



  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.

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


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.