×

zbMATH — the first resource for mathematics

Mathematical models and search algorithms for the capacitated \(p\)-center problem. (English) Zbl 1451.90087
Summary: The capacitated \(p\)-center problem requires one to select \(p\) facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. The problem is well known in the field of facility location, because of the many applications that it can model. In this paper, we solve it by means of search algorithms that iteratively seek the optimal distance by solving tailored subproblems. We present different mathematical formulations for the subproblems and improve them by means of several valid inequalities, including an effective one based on a 0-1 disjunction and the solution of subset sum problems. We also develop an alternative search strategy that finds a balance between traditional sequential search and binary search. This strategy limits the number of feasible subproblems to be solved and, at the same time, avoids large overestimates of the solution value, which are detrimental for the search. We evaluate the proposed techniques by means of extensive computational experiments on benchmark instances from the literature and new larger test sets. All instances from the literature with up to 402 vertices and integer distances are solved to proven optimality, including 13 open cases, and feasible solutions are found in 10 minutes for instances with up to 3,038 vertices.
Reviewer: Reviewer (Berlin)
MSC:
90B80 Discrete location and assignment
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albareda-Sambola M, Díaz J, Fernández E (2010) Lagrangean duals and exact solution to the capacitated p-center problem. Eur. J. Oper. Res. 201(1):71-81.Crossref, Google Scholar · Zbl 1177.90241
[2] Balas E (1973) Disjunctive programming. Ann. Discrete Math. 5(2):3-51.Google Scholar · Zbl 0409.90061
[3] Boccia M, Sforza A, Sterle C, Vasilyev I (2008) A cut and branch approach for the capacitated p-median problem based on Fenchel cutting planes. J. Math. Model. Algorithms 7(1):43-58.Crossref, Google Scholar · Zbl 1170.90521
[4] Boschetti M, Hadjconstantinou E, Mingozzi A (2002) New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem. IMA J. Management Math. 13(2):95-119.Crossref, Google Scholar · Zbl 1097.90546
[5] Boyd E (1993) Generating Fenchel cutting planes for knapsack polyhedra. SIAM J. Optim. 3(4):734-750.Crossref, Google Scholar · Zbl 0797.90067
[6] Boyd E (1994) Fenchel cutting planes for integer programs. Oper. Res. 42(1):53-64.Link, Google Scholar · Zbl 0809.90104
[7] Calik H, Tansel B (2013) Double bound method for solving the p-center location problem. Comput. Oper. Res. 40(12):2991-2999.Crossref, Google Scholar · Zbl 1348.90384
[8] Ceselli A, Righini G (2005) A branch-and-price algorithm for the capacitated p-median problem. Networks 45(3):125-142.Crossref, Google Scholar · Zbl 1101.68722
[9] Chen D, Chen R (2009) New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems. Comput. Oper. Res. 36(5):1646-1655.Crossref, Google Scholar · Zbl 1177.90246
[10] Daskin M (1995) Network and Discrete Location: Models, Algorithms, and Applications (Wiley, New York).Crossref, Google Scholar
[11] Daskin M (2000) A new approach to solving the vertex p-center problem to optimality: Algorithm and computational results. Comm. Oper. Res. Soc. Japan 45(9):428-436.Google Scholar
[12] Davidović T, Ramljak D, Šelmić M, Teodorović D (2011) Bee colony optimization for the p-center problem. Comput. Oper. Res. 38(10):1367-1376.Crossref, Google Scholar · Zbl 1208.90103
[13] Davoodi M, Mohades A, Rezaei J (2011) Solving the constrained p-center problem using heuristic algorithms. Appl. Soft Comput. 11(4):3321-3328.Crossref, Google Scholar
[14] Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1-20.Crossref, Google Scholar · Zbl 1346.90700
[15] Drezner Z, Hamacher H, eds. (2002) Facility Location: Applications and Theory (Springer, Berlin).Crossref, Google Scholar
[16] Elloumi S, Labbé M, Pochet Y (2004) A new formulation and resolution method for the p-center problem. INFORMS J. Comput. 16(1):84-94.Link, Google Scholar · Zbl 1239.90103
[17] Espejo I, Marín A, Rodríguez-Chía A (2015) Capacitated p-center problem with failure foresight. Eur. J. Oper. Res. 247(1):229-244.Crossref, Google Scholar · Zbl 1346.90488
[18] Fast C, Hicks I (2017) A branch decomposition algorithm for the p-median problem. INFORMS J. Comput. 29(3):474-488.Link, Google Scholar · Zbl 1386.90071
[19] García S, Labbé M, Marín A (2011) Solving large p-median problems with a radius formulation. INFORMS J. Comput. 23(4):546-556.Link, Google Scholar · Zbl 1243.90091
[20] Hakimi S (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3):450-459.Link, Google Scholar · Zbl 0123.00305
[21] Hochbaum D, Shmoys D (1985) A best possible heuristic for the k-center problem. Math. Oper. Res. 10(2):180-184.Link, Google Scholar · Zbl 0565.90015
[22] Ilhan T, Özsoy F, Pınar M (2002) An efficient exact algorithm for the vertex p-center problem and computational experiments for different set covering subproblems. Technical report, Optimization Online, http://www.optimization-online.org/DB_HTML/2002/12/588.html.Google Scholar
[23] Irawan C, Salhi S, Drezner Z (2015) Hybrid meta-heuristics with VNS and exact methods: Application to large unconditional and conditional vertex p-centre problems. J. Heuristics 22(4):507-537.Crossref, Google Scholar
[24] Jaeger M, Goldberg J (1994) Technical note—A polynomial algorithm for the equal capacity p-center problem on trees. Transportation Sci. 28(2):167-175.Link, Google Scholar · Zbl 0807.90076
[25] Kaparis K, Letchford A (2008) Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem. Eur. J. Oper. Res. 186(1):91-103.Crossref, Google Scholar · Zbl 1138.90016
[26] Kariv O, Hakimi S (1979) An algorithmic approach to network location problems. I: The p-centers. SIAM J. Appl. Math. 37(3):513-538.Crossref, Google Scholar · Zbl 0432.90074
[27] Laporte G, Nickel S, Saldanha da Gama F, eds. (2015) Location Science (Springer, Berlin).Crossref, Google Scholar · Zbl 1329.90003
[28] Lorena L, Senne E (2004) A column generation approach to capacitated p-median problems. Comput. Oper. Res. 31(6):863-876.Crossref, Google Scholar · Zbl 1048.90132
[29] Marianov V, ReVelle C (1995) Facility Location: A Survey of Applications and Methods (Springer-Verlag, New York).Google Scholar
[30] Masuyama S, Ibaraki T, Hasegawa T (1981) The computational complexity of the m-center problems on the plane. IEICE Trans. E64(2):57-64.Google Scholar
[31] Mihelič J, Robič B (2003) Approximation algorithms for the k-center problem: An experimental evaluation. Leopold-Wildburger U, Rendl F, Wäscher G, eds. Operations Research Proceedings 2002 (Springer, Berlin), 371-376.Google Scholar · Zbl 1162.90496
[32] Minieka E (1970) The m-center problem. SIAM Rev. 12(1):138-139.Crossref, Google Scholar · Zbl 0193.24204
[33] Mladenović N, Labbé M, Hansen P (2003) Solving the p-center problem with tabu search and variable neighborhood search. Networks 42(1):48-64.Crossref, Google Scholar · Zbl 1036.90046
[34] Özsoy F, Pınar M (2006) An exact algorithm for the capacitated vertex p-center problem. Comput. Oper. Res. 33(5):1420-1436.Crossref, Google Scholar · Zbl 1126.90039
[35] Plesník J (1987) A heuristic for the p-center problems in graphs. Discrete Appl. Math. 17(3):263-268.Crossref, Google Scholar · Zbl 0637.05020
[36] Quevedo-Orozco D (2017) Personal communication with authors via email, April 14.Google Scholar
[37] Quevedo-Orozco D, Ríos-Mercado R (2015) Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent. Comput. Oper. Res. 62(October):133-144.Crossref, Google Scholar · Zbl 1348.90412
[38] Reese J (2006) Solution methods for the p-median problem: An annotated bibliography. Networks 48(3):125-142.Crossref, Google Scholar · Zbl 1133.90357
[39] Scaparra M, Pallottino S, Scutellà M (2004) Large-scale local search heuristics for the capacitated vertex p-center problem. Networks 43(4):241-255.Crossref, Google Scholar · Zbl 1053.90085
[40] Valério de Carvalho J (2002) LP models for bin packing and cutting stock problems. Eur. J. Oper. Res. 141(2):253-273.Crossref, Google Scholar · Zbl 1059.90095
[41] Vasilyev I, Boccia M, Hanafi S (2016) An implementation of exact knapsack separation. J. Global Optim. 66(1):127-150.Crossref, Google Scholar · Zbl 1355.90051
[42] Yaman H (2006) Formulations and valid inequalities for the heterogeneous vehicle routing problem. Math. Programming 106(2):365-390.Crossref, · Zbl 1134.90527
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.