×

A hypergraph multi-exchange heuristic for the single-source capacitated facility location problem. (English) Zbl 1380.90165

Summary: In this paper, we introduce a large-scale neighborhood search procedure for solving the single-source capacitated facility location problem (SSCFLP). The neighborhood structures are induced by innovative split multi-customer multi-exchanges, where clusters of customers assigned to one facility can be moved simultaneously to multiple destination facilities and vice versa. To represent these exchanges, we use two types of improvement hypergraphs. The improvement hypergraphs are built dynamically and the moving customers associated with each hyperedge are selected by solving heuristically a suitably defined mixed-integer program. We develop a hypergraph search framework, including forward and backward procedures, to identify improving solutions efficiently. Our proposed algorithm can obtain improving moves more quickly and even find better solutions than a traditional multi-exchange heuristic [R. K. Ahuja et al., Manage. Sci. 50, No. 6, 749–760 (2004; Zbl 1232.90257)]. In addition, when compared with the kernel search algorithm [G. Guastaroba and M. G. Speranza, Eur. J. Oper. Res. 238, No. 2, 438–450 (2014; Zbl 1338.90215)], which at present is the most effective for solving SSCFLP, our algorithm is not only competitive but can find better solutions or even the best known solution to some very large scale benchmark instances from the literature.

MSC:

90B80 Discrete location and assignment
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Addis, B.; Carello, G.; Ceselli, A., Combining very large scale and ILP based neighborhoods for a two-level location problem, European Journal of Operational Research, 231, 3, 535-546 (2013) · Zbl 1317.90161
[2] Agar, M.; Salhi, S., Lagrangean heuristics applied to a variety of large capacitated plant location problems, Journal of Operational Research Society, 49, 10, 1072-1084 (1998) · Zbl 1140.90419
[3] Ahuja, R. K.; Cunha, C. B., Very large-scale neighborhood search for the k-constraint multiple knapsack problem, Journal of Heuristics, 11, 5-6 Spec. Iss., 465-481 (2005) · Zbl 1122.90394
[4] Ahuja, R. K.; Ergun, O.; Orlin, J. B.; Punnen, A. P., A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics, 123, 1-3, 75-102 (2002) · Zbl 1014.68052
[5] Ahuja, R. K.; Orlin, J. B.; Pallottino, S.; Scaparra, M. P.; Scuttellà, M. G., A multi-exchange heuristic for the single-source capacitated facility location problem, Management Science, 50, 6, 749-760 (2004) · Zbl 1232.90257
[6] Ahuja, R. K.; Orlin, J. B.; Sharma, D., Multi-exchange neighborhood search algorithms for the capacitated minimum spanning tree problem, Mathematical Programming, 91, 71-97 (2001) · Zbl 1051.90019
[7] Ambrosino, D.; Sciomachen, A.; Scutellà, M. G., A heuristic based on multi-exchange techniques for a regional fleet assignment location-routing problem, Computers and Operations Research, 36, 2, 442-460 (2009) · Zbl 1157.90340
[8] Avella, P.; Boccia, M., A cutting plane algorithm for the capacitated facility location problem, Computational Optimization and Applications, 43, 1, 39-65 (2009) · Zbl 1170.90432
[9] Barcelo, J.; Casanova, J., A heuristic Lagrangean algorithm for the capacitated plant location problem, European Journal of Operational Research, 15, 212-226 (1984) · Zbl 0544.90025
[10] Beasley, J. E., OR-Library: Distributing test problems by electronic mail, Journal of Operational Research Society, 41, 11, 1069-1072 (1990)
[11] Beasley, J. E., Lagrangean heuristics for location problems, European Journal of Operational Research, 65, 3, 383-399 (1993) · Zbl 0768.90045
[12] Berge, C., Graphs and hypergraphs (1993), Elsevier · Zbl 0483.05029
[13] Borndörfer, R.; Heismann, O., The hypergraph assignment problem, Discrete Optimization, 15, 15-25 (2015) · Zbl 1308.90143
[14] Cambini, R.; Gallo, G.; Scutellà, M. G., Flows on hypergraphs, Mathematical Programming, 78, 2, 195-217 (1997) · Zbl 0889.90143
[15] Chen, C. H.; Ting, C. J., Combining Lagrangean heuristic and ant colony system to solve the single source capacitated facility location problem, Transportation Research Part E: Logistics and Transportation Review, 44, 6, 1099-1122 (2008)
[16] Contreras, I. A.; Diaz, J. A., Scatter search for single source capacitated facility location problem, Annals of Operations Research, 157, 1, 73-89 (2008) · Zbl 1153.90481
[17] Cortinhal, M. J.; Captivo, M. E., Upper and lower bounds for the single source capacitated location problem, European Journal of Operational Research, 151, 2, 333-351 (2003) · Zbl 1053.90051
[18] Delmaire, H.; Diaz, J. A.; Fernandez, E.; Ortega, M., Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem, Infor-Information Systems and Operational Research, 37, 3, 194-225 (1999) · Zbl 07677590
[19] Diaz, J. A.; Fernandez, E., A branch-and-price algorithm for the single source capacitated plant location problem, Journal of Operational Research Society, 53, 3, 728-740 (2002) · Zbl 1130.90354
[20] Filho, V. J.M. F.; Galvao, R. D., A tabu search heuristic for the concentrator location problem, Location Science, 6, 1-4, 189-209 (1998)
[21] Frangioni, A.; Necciari, E.; Scutellà, M. G., A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems, Journal of Combinatorial Optimization, 8, 2, 195-220 (2004) · Zbl 1133.90337
[22] Gallo, G.; Longo, G.; Pallottino, S., Directed hyperpaths and applications, Discrete Applied Mathematics, 42, 2-3, 177-201 (1993) · Zbl 0771.05074
[23] Galvao, R. D.; Marianov, V., Lagrangean relaxation-based techniques for solving facility location problems, Foundations of location analysis, International Series in Operations Research & Management Science, 155, 391-420 (2011), Springer · Zbl 1388.90066
[24] Guastaroba, G.; Speranza, M. G., A heuristic for BILP problems: The single source capacitated facility location problem, European Journal of Operational Research, 238, 2, 438-450 (2014) · Zbl 1338.90215
[25] Hindi, H.; Pienkosz, K., Efficient solution of large scale, single-source, capacitated plant location problems, Journal of Operational Research Society, 50, 3, 268-274 (1999) · Zbl 1054.90588
[26] Ho, S. C., An iterated tabu search heuristic for the single source capacitated facility location problem, Applied Soft Computing Journal, 27, 169-178 (2015)
[27] Holmberg, K.; Ronnqvist, M.; Yuan, D., An exact algorithm for the capacitated facility location problems with single sourcing, European Journal of Operational Research, 113, 3, 544-559 (1999) · Zbl 0947.90059
[28] Klincewicz, J.; Luss, H., A Lagrangean relaxation heuristic for capacitated facility location with single-source constraints, Journal of Operational Research Society, 37, 5, 495-500 (1986) · Zbl 0588.90025
[29] Klose, A.; Drexl, A., Facility location models for distribution system design, European Journal of Operational Research, 162, 1, 4-29 (2005) · Zbl 1132.90345
[30] Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location science (2015), Springer · Zbl 1329.90003
[31] Neebe, A. W.; Rao, M. R., An algorithm for the fixed-charge assigning users to sources problem, Journal of the Operational Research Society, 34, 11, 1107-1113 (1983) · Zbl 0521.90075
[32] Nguyen, S.; Pallottino, S., Equilibrium traffic assignment for large scale transit networks, European Journal of Operational Research, 37, 2, 176-186 (1988) · Zbl 0649.90049
[33] Öncan, T.; Kabadi, S.; Nair, K. P.K.; Punnen, A. P., VLSN search algorithms for partitioning problems using matching neighbourhoods, Journal of the Operational Research Society, 59, 3, 388-398 (2008) · Zbl 1145.90426
[34] Pirkul, H., Efficient algorithm for the capacitated concentrator location problem, Computers & Operations Research, 14, 3, 197-208 (1987) · Zbl 0617.90019
[35] Rahman, A.; Poirel, C. L.; Badger, D. J.; Estep, C.; Murali, T. M., Reverse engineering molecular hypergraphs, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10, 5, 1113-1124 (2013)
[36] Rainwater, C.; Geunes, J.; Romeijn, H. E., A facility neighborhood search heuristic for capacitated facility location with single-source constraints and flexible demand, Journal of Heuristics, 18, 2, 297-315 (2012) · Zbl 1358.90068
[37] Ronnqvist, M.; Holt, J.; Tragantalerngsak, S., A repeated matching heuristic for the single-source capacitated facility location problem, European Journal of Operational Research, 116, 1, 51-68 (1999) · Zbl 1009.90064
[38] Scaparra, M. P.; Pallottino, S.; Scutellà, M. G., Large-scale local search heuristics for the capacitated vertex p-center problem, Networks, 43, 4, 241-255 (2004) · Zbl 1053.90085
[39] Sridharan, R., A Lagrangean heuristic for the capacitated plant location problem with single source constraints, European Journal of Operational Research, 66, 3, 305-312 (1991) · Zbl 0771.90062
[40] Talluri, K. T., Swapping applications in a daily airline fleet assignment, Transportation Science, 30, 3, 237-248 (1996) · Zbl 0879.90138
[41] Thompson, P. M.; Orlin, J. B., The theory of cyclic transfers, Working paper (1989), Massachusetts Institute of Technology
[42] Thompson, P. M.; Psaraftis, H. N., Cyclic transfer algorithms for multivehicle routing and scheduling problems, Operations Research, 41, 5, 935-946 (1993) · Zbl 0797.90021
[43] Torres, A. F.; Araoz, J. D., Combinatorial models for searching in knowledge bases, Acta Cient, Venezolana, 39, 387-394 (1988) · Zbl 0668.68115
[44] Wasserman, S.; Faust, K., Social network analysis: Methods and applications (1999), Cambridge University Press: Cambridge University Press New York
[45] Yang, Z.; Chu, F.; Chen, H., A cut-and-solve based algorithm for the single-source capacitated facility location problem, European Journal of Operational Research, 221, 3, 521-532 (2012) · Zbl 1253.90143
[46] Zorzi, M.; Rao, R. R., Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance, IEEE Transactions on Mobile Computing, 2, 4, 337-348 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.