×

zbMATH — the first resource for mathematics

Intelligent-guided adaptive search for the maximum covering location problem. (English) Zbl 1391.90387
Summary: Computational intelligence techniques are part of the search process in several recent heuristics. One of their main benefits is the use of an adaptive memory to guide the search towards regions with promising solutions. This paper follows this approach proposing a variation of a well-known iteration independent metaheuristic. This variation adds a learning stage to the search process, which can improve the quality of the solutions found. The proposed metaheuristic, named intelligent-guided adaptive search (IGAS), provides an efficient solution to the maximum covering facility location problem. Computational experiments conducted by the authors showed that the solutions found by IGAS were better than the solutions obtained by popular methods found in the literature.

MSC:
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
90B40 Search theory
90C27 Combinatorial optimization
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Church, R.; ReVelle, C., The maximal covering location problem, Pap Reg Sci Assoc, 32, 101-118, (1974)
[2] Senne, E. L.F.; Pereira, M. A.; Lorena, L. A.N., A decomposition heuristic for the maximal covering location problem, Adv Oper Res, 2010, 1-12, (2010)
[3] Rodriguez, F.; Blum, C.; Lozano, M.; García-Martínez, C., Iterated greedy algorithms for the maximal covering location problem, (Hao, J.-K.; Middendorf, M., Evolutionary computation in combinatorial optimization. Lecture notes in computer science, vol. 7245, (2012), Springer Berlin, Heidelberg), 172-181 · Zbl 1292.90173
[4] Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of np-completeness, (1979), W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039
[5] Chung, C.-H., Recent applications of the maximal covering location planning (MCLP) model, J Oper Res Soc, 37, 735-746, (1986) · Zbl 0601.90043
[6] Shilling, D. A.; Jayaraman, V.; Barkhi, R., A review of covering problems in facility location, Locat Sci, 1, 25-55, (1993) · Zbl 0923.90108
[7] Lee, J. M.; Lee, Y. H., Tabu based heuristics for the generalized hierarchical covering location problem, Comput Ind Eng, 58, 638-645, (2010)
[8] Moore, G. C.; ReVelle, C., The hierarchical service location problem, Manag Sci, 28, 775-780, (1982) · Zbl 0482.90023
[9] IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual Version 12 Release 6, IBM, 2014.
[10] Feo, T.; Resende, M., A probabilistic heuristic for a computationally difficult set covering problem, Oper Res Lett, 8, 67-71, (1989) · Zbl 0675.90073
[11] Feo, T. A.; Resende, M. G., Greedy randomized adaptive search procedures, J Glob Optim, 6, 109-133, (1995) · Zbl 0822.90110
[12] Resende, M. G.C., Computing approximate solutions of the maximum covering problem with GRASP, J Heuristics, 4, 161-171, (1998) · Zbl 0913.90202
[13] Fritzke B. A growing neural gas network learns topologies. Advances in neural information processing systems, vol. 7. MIT Press; 1995. p. 625-32.
[14] Qin, A.; Suganthan, P., Robust growing neural gas algorithm with application in cluster analysis, Neural Netw, 17, 1135-1148, (2004) · Zbl 1079.68596
[15] Martí, L.; García, J.; Berlanga, A.; Coello, C. A.C.; Molina, J. M., MB-gngaddressing drawbacks in multi-objective optimization estimation of distribution algorithms, Oper Res Lett, 39, 150-154, (2011) · Zbl 1218.90178
[16] Karasakal, O.; Karasakal, E. K., A maximal covering location model in the presence of partial coverage, Comput Oper Res, 31, 1515-1526, (2004) · Zbl 1107.90028
[17] Farahani, R. Z.; Asgari, N.; Heidari, N.; Hosseininia, M.; Goh, M., Covering problems in facility locationa review, Comput Ind Eng, 62, 368-407, (2012)
[18] Adenso-Díaz, B.; Rodríguez, F., A simple search heuristic for the mclpapplication to the location of ambulance bases in a rural region, Omega, 25, 181-187, (1997)
[19] Galvão, R. D.; ReVelle, C., A Lagrangian heuristic for the maximal covering location problem, Eur J Oper Res, 88, 114-123, (1996) · Zbl 0913.90200
[20] Galvão, R. D.; Espejo, L. G.A.; Boffey, B., A comparison of Lagrangian and surrogate relaxations for the maximal covering location problem, Eur J Oper Res, 124, 377-389, (2000) · Zbl 0967.90068
[21] Downs, B. T.; Camm, J. D., An exact algorithm for the maximal covering problem, Nav Res Logist, 43, 435-461, (1996) · Zbl 0846.90076
[22] Arakaki RGI, Lorena LAN. A constructive genetic algorithm for the maximal covering location problem. In: Proceedings of the 4th metaheuristics international conference, MIC; 2001. p. 13-7.
[23] Lorena, L. A.; Pereira, M. A., A Lagrangian/surrogate heuristic for the maximal covering location problem using Hillman’s edition, Int J Ind Eng, 9, 57-67, (2002)
[24] ReVelle, C.; Scholssberg, M.; Williams, J., Solving the maximal covering location problem with heuristic concentration, Comput Oper Res, 35, 427-435, (2008), Part Special Issue: Location Modeling Dedicated to the memory of Charles S. ReVelle · Zbl 1141.90472
[25] Xia L, Xie M, Xu W, Shao J, Yin W, Dong J. An empirical comparison of five efficient heuristics for maximal covering location problems. In: Service operations, logistics and informatics (SOLI), Chicago, IEEE/INFORMS international conference. IEEE, Chicago; 2009. p. 747-53.
[26] Zarandi, M. F.; Davari, S.; Sisakht, S. H., The large scale maximal covering location problem, Sci Iran, 18, 1564-1570, (2011)
[27] Festa, P.; Resende, M. G.C., An annotated bibliography of GRASP part iiapplications, Int Trans Oper Res, 16, 131-172, (2009) · Zbl 1168.90582
[28] Festa, P.; Resende, M. G.C., An annotated bibliography of GRASP part ialgorithms, Int Trans Oper Res, 16, 1-24, (2009) · Zbl 1153.90553
[29] Ribeiro, M.; Plastino, A.; Martins, S., Hybridization of GRASP metaheuristic with data mining techniques, J Math Model Algorithms, 5, 23-41, (2006) · Zbl 1099.68741
[30] Plastino, A.; Barbalho, H.; Santos, L.; Fuchshuber, R.; Martins, S., Adaptive and multi-mining versions of the DM-GRASP hybrid metaheuristic, J Heuristics, 20, 39-74, (2014)
[31] Laguna, M.; Martí, R., GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS J Comput, 11, 44-52, (1999) · Zbl 1092.90544
[32] Resende, M.; Ribeiro, C., GRASP with path-relinkingrecent advances and applications, (Ibaraki, T.; Nonobe, K.; Yagiura, M., Metaheuristics: progress as real problem solvers, operations research/computer science interfaces series, vol. 32, (2005), Springer US), 29-63
[33] Nascimento, M. C.; Pitsoulis, L., Community detection by modularity maximization using GRASP with path relinking, Comput Oper Res, 40, 3121-3131, (2013) · Zbl 1348.91237
[34] Graham J, Starzyk J. A hybrid self-organizing neural gas based network. In: The international joint conference on neural networks (IJCNN), Hong Kong, IEEE world congress on computational intelligence. IEEE Computer Press, Hong Kong; 2008. p. 3806-13.
[35] (Kohonen, T.; Schroeder, M. R.; Huang, T. S., Self-organizing maps, (2001), Springer-Verlag New York Inc. Secaucus, NJ, USA) · Zbl 0957.68097
[36] Jia, H.; Ordóñez, F.; Dessouky, M. M., Solution approaches for facility location of medical supplies for large-scale emergencies, Comput Ind Eng, 52, 257-276, (2007)
[37] Hutter, F.; Hoos, H. H.; Leyton-Brown, K.; Stützle, T., Paramilsan automatic algorithm configuration framework, J Artif Intell Res, 36, 267-306, (2009) · Zbl 1192.68831
[38] Aiex, R. M.; Resende, M. G.C.; Ribeiro, C. C., TTT plotsa perl program to create time-to-target plots, Optim Lett, 1, 355-366, (2007) · Zbl 1220.90102
[39] Reinelt, G., The traveling salesman: computational solutions for TSP applications, (1994), Springer-Verlag Berlin, Heidelberg
[40] Glover, F., A template for scatter search and path relinking, (Hao, J.-K.; Lutton, E.; Ronald, E.; Schoenauer, M.; Snyers, D., Artificial evolution. Lecture notes in computer science, vol. 1363, (1998), Springer Berlin, Heidelberg), 1-51
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.