The capacitated single-source p-center problem in the presence of fixed cost and multilevel capacities using VNS and aggregation technique
DOI:
https://doi.org/10.2298/YJOR170110021IKeywords:
Capacitated p-center Problem, Mathematical Model, Matheuristic, VNSAbstract
In this study, the discrete p-center problem with the presence of multilevel capacities and fixed (opening) cost of a facility under a limited budget is investigated. A mathematical model of the problem is produced, where we seek the location of open facilities, their corresponding capacities, and the allocation of the customers to the open facilities in order to minimise the maximum distance between customers and their assigned facilities. Two matheuristic approaches are also proposed to deal with larger instances. The first approach is a hybridisation of a clustering-based technique, an exact method, while the second one is based on Variable Neighbourhood Search (VNS). Computational experiments show that the proposed methods produce interesting and competitive results on newly and randomly generated datasets.References
Albareda-Sambola, M., Daz, J.A., and Fernandez, E., Lagrangean duals and exact solution to the capacitated p-center problem, European Journal of Operational Research, 201 (2010) 71-81.
An, H., Bhaskara, A., Chekuri, C., Gupta, S., Madan, V., and Svensson, O., Centrality of trees for capacitated k-center, Mathematical Programming, 154 (2015) 29-53.
Bar-Ilan, J., Kortsarz, G., and Peleg, D., How to allocate network centers, Journal of Algorithms, 15 (1993) 385-415.
Bashiri, M., Mirzaei, M., and Randall, M., Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution, Applied Mathematical Modelling, 37 (2013) 3513-3525.
Brimberg, J., and Mladenovic, N., A variable neighbourhood algorithm for solving the continuous location-allocation problem, Studies of Locational Analysis, 10 (1996) 1-12.
Brimberg, J., and Salhi, S., A continuous location-allocation problem with zone dependent fixed cost, Annals of Operations Research, 136 (2005) 99-115.
Chechika, S., and Peleg, D., The fault-tolerant capacitated k-center problem, Theoretical Computer Science, 566 (2015) 12-25.
Cooper, L., Heuristic methods for location-allocation problems, SIAM Review, 6 (1964) 37-53.
Cooper, L., The transportation-location problem, Operations Research, 20 (1972) 94-108.
Cygan, M., Hajiaghayi, M., Khuller, S., LP rounding for k-centers with non-uniform hard capacities, In Proceeding 53rd IEEE Symposium on Foundations of Computer Science, (FOCS) (2012) 273-282.
Elshaikh, A., Salhi, S., and Nagy, G., The continuous p-centre problem: An investigation into variable neighbourhood search with memory, European Journal of Operational Research, 241 (2015) 606-621.
Francis, R.L., Lowe, T.J., Rayco, M.B., and Tamir, A., Aggregation error for location models: survey and analysis, Annals of Operations Research, 167 (2009) 171-208.
Hakimi, S.L., Optimum locations of switching centers and the absolute centers and medians of a graph, Operation Research, 12 (1964) 450-459.
Hansen, P., and Mladenovic, N., Variable neighbourhood search for the p-median, Location Science, 5 (1997) 207-225.
Hansen, P., and Mladenovic, N., Variable neighbourhood search: Principles and applications, European Journal of Operational Research, 130 (2001) 449-467.
Hansen, P., Mladenovic, N., and Perez, J.A.M., Variable neighbourhood search: methods and applications, Annals of Operations Research, 175 (2010) 367-407.
Irawan, C.A., Salhi, S., and Scaparra, M.P., An Adaptive Multiphase Approach for Large Unconditional and Conditional p-Median Problems, European Journal of Operational Research, 237 (2014) 590-605.
Irawan, C.A., and Salhi, S., Aggregation and non-aggregation techniques for large facility location problems- A survey, Yugoslav Journal of Operations Research, 25 (2015) 1-11.
Irawan, C.A., Salhi, S., and Drezner, D., Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and conditional vertex p-centre problems, Journal of Heuristics, 22 (2016) 507-537.
Jaeger, M., and Goldberg, J., A polynomial algorithm for the equal capacity p-center problem on trees, Transportation Science, 28 (1994) 167-175.
Kariv, O., and Hakimi, S.L., An algorithmic approach for the vertex p-center problem. Part I: The p-centers, SIAM Journal on Applied Mathematics, 37 (1979) 513-538.
Khuller, S., and Sussmann, Y.J., The capacitated k-center problem, SIAM Journal on Discrete Mathematics, 13 (2000) 403-418.
Mladenovic, N., Labbe, M., and Hansen, P., Solving the p-center problem with tabu search and variable neighbourhood search, Networks, 42 (2003) 48-64.
Ozsoy, F.A., and Pnar, M.C., An exact algorithm for the capacitated vertex p-center problem, Computers & Operations Research, 33 (2006) 1420-1436.
Quevedo-Orozco, D.R., and Ros-Mercado, R.Z., A New Heuristic for the Capacitated Vertex p-Center Problem, in: C. Bielza, A. Salemrn, A. Alonso-Betanzos, J.I. Hidalgo, L. Martnez, A. Troncoso, et al., (eds.) Advances in artificial intelligence. Lecture notes in artificial intelligence, Heidelberg, Germany: Springer, 8109 (2013) 279-288.
Quevedo-Orozco, D.R., and Ros-Mercado, R.Z., Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent, Computers & Operations Research, 62 (2015) 133-144.
Salhi, S., Heuristic Search: The Emerging Science of Problem Solving, Springer, Cham, Switzerland, 2017.
Scaparra, M.P., Pallottino, S., Scutella, M.G., Large-scale local search heuristics for the capacitated vertex p-center problem, Networks, 43 (2004) 241-255.
Downloads
Published
Issue
Section
License
Copyright (c) 2018 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
