×

zbMATH — the first resource for mathematics

Improving the quality of heuristic solutions for the capacitated vertex \(p\)-center problem through iterated greedy local search with variable neighborhood descent. (English) Zbl 1348.90412
Summary: The capacitated vertex \(p\)-center problem is a location problem that consists of placing \(p\) facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.

MSC:
90B80 Discrete location and assignment
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kariv, O.; Hakimi, S. L., An algorithmic approach to network location problems, ithe p-centers, SIAM J Appl Math, 37, 3, 513-538, (1979) · Zbl 0432.90074
[2] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS J Comput, 16, 1, 84-94, (2004) · Zbl 1239.90103
[3] Özsoy, F. A.; Pınar, M.Ç., An exact algorithm for the capacitated vertex p-center problem, Comput Oper Res, 33, 5, 1420-1436, (2006) · Zbl 1126.90039
[4] Albareda-Sambola, M.; Díaz, J. A.; Fernández, E., Lagrangean duals and exact solution to the capacitated p-center problem, Eur J Oper Res, 201, 1, 71-81, (2010) · Zbl 1177.90241
[5] 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
[6] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur J Oper Res, 177, 3, 2033-2049, (2007) · Zbl 1110.90042
[7] Lourenço, H. R.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G. A., Handbook of metaheuristics, (2002), Kluwer Academic Publishers Norwell), 321-353 · Zbl 1116.90412
[8] Ruiz, R.; Stützle, T., An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, Eur J Oper Res, 187, 3, 1143-1159, (2008) · Zbl 1137.90514
[9] Fanjul-Peyro, L.; Ruiz, R., Iterated greedy local search methods for unrelated parallel machine scheduling, Eur J Oper Res, 207, 1, 55-69, (2010) · Zbl 1205.90121
[10] Urlings, T.; Ruiz, R.; Stützle, T., Shifting representation search for hybrid flexible flowline problems, Eur J Oper Res, 207, 2, 1086-1095, (2010) · Zbl 1206.90049
[11] Hansen, P.; Mladenović, N., An introduction to variable neighborhood search, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-heuristics: advances and trends in local search paradigms for optimization, (1999), Kluwer Boston, USA), 433-458 · Zbl 0985.90095
[12] Subramanian, A.; Drummond, L. M.A.; Bentes, C.; Ochi, L. S.; Farias, R., A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Comput Oper Res, 37, 11, 1899-1911, (2010) · Zbl 1188.90041
[13] Martins, A. X.; Duhamel, C.; Souza, M. C.; Saldanha, R. R.; Mahey, P., A VND-ILS heuristic to solve the RWA problem, (Pahl, J.; Reiners, T.; Voß, S., Network optimization. Lecture notes in computer science, vol. 6701, (2011), Springer Berlin, Germany), 577-582
[14] Quevedo-Orozco, D. R.; Ríos-Mercado, R. Z., A new heuristic for the capacitated vertex p-center problem, (Bielza, C.; Salemrón, A.; Alonso-Betanzos, A.; Hidalgo, J. I.; Martínez, L.; Troncoso, A.; etal., Advances in artificial intelligence. Lecture notes in artificial intelligence, vol. 8109, (2013), Springer Heidelberg, Germany), 279-288
[15] Beasley, J. E., OR-librarydistributing test problems by electronic mail, J Oper Res Soc, 41, 11, 1069-1072, (1990)
[16] ReVelle, C. S.; Eiselt, H. A., Location analysisa synthesis and survey, Eur J Oper Res, 165, 1, 1-19, (2005) · Zbl 1112.90362
[17] Lorena, L. A.N.; Senne, E. L.F., A column generation approach to capacitated p-Median problems, Comput Oper Res, 31, 6, 863-876, (2004) · Zbl 1048.90132
[18] Ceselli, A.; Righini, G., A branch-and-price algorithm for the capacitated p-Median problem, Networks, 45, 3, 125-142, (2005) · Zbl 1101.68722
[19] Reinelt G. The traveling salesman: computational solutions for TSP applications. Lecture notes in computer science, vol. 840. Heidelberg: Springer; 1994.
[20] Loosemore S, Stallman RM, McGrath R, Oram A, Drepper U. The GNU C library reference manual: for version 2.17. Free Software Foundation; 2012.
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.