×

zbMATH — the first resource for mathematics

\(k\)-balanced center location problem: a new multi-objective facility location problem. (English) Zbl 1458.90426
Summary: Balancing workload among a set of facility centers is one of the practical objectives in location problems. In this paper, we introduce a multi-objective optimization facility location problem which considers two goals: minimizing the maximum distance between each client and its closest center, and maximizing workload balance among the centers. To achieve the second goal, we define two objectives, minimizing the maximum number of clients allocated to each center, and minimizing the difference between the maximum and minimum number of clients allocated to each center. We prove the hardness of finding even one Pareto optimal solution in the resulted multi-objective problem. Also, we propose a simple iterative algorithm based on the Voronoi diagram to solve the problem. We show the efficiency of the proposed algorithm using test problems and compare the results with a robust multi-objective evolutionary algorithm.
Reviewer: Reviewer (Berlin)
MSC:
90B80 Discrete location and assignment
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Daskin, M. S., Network and Discrete Location: Models, Algorithms and Applications, (2001), John Wiley: John Wiley New York
[2] Farahani, R. Z.; SteadieSeifi, M.; Asgari, N., Multiple criteria facility location problems: a survey, Appl. Math. Modell., 34, 7, 1689-1709, (2010) · Zbl 1193.90143
[3] Davoodi, M.; Mohades, A.; Rezaei, J., Solving the constrained p-center problem using heuristic algorithms, Appl. Soft Comput., 11, 4, 3321-3328, (2011)
[4] Bortnikov, E.; Khuller, S.; Li, J.; Mansour, Y.; Naor, J. S., The load‐distance balancing problem, Networks, 59, 1, 22-29, (2012) · Zbl 1242.68004
[5] Kleinberg, J.; Rabani, Y.; Tardos, É., Fairness in routing and load balancing, (Foundations of Computer Science, 1999. 40th Annual Symposium on, (1999), IEEE), 568-578
[6] Kalcsics, J.; Nickel, S.; Schröder, M., Towards a unified territory design approach, Appl. Algorithms GIS Integr., 13, 1-56, (2005), Top
[7] Barilan, J.; Kortsarz, G.; Peleg, D., How to allocate network centers, J. Algorithms, 15, 3, 385-415, (1993) · Zbl 0784.68012
[8] Fernandes, C. G.; de Paula, S. P.; Pedrosa, L. L., Improved approximation algorithms for capacitated fault-tolerant k-center, Algorithmica, 80, 3, 1041-1072, (2018) · Zbl 1408.68033
[9] Nagarajan, V.; Schieber, B.; Shachnai, H., The euclidean k-supplier problem, (International Conference on Integer Programming and Combinatorial Optimization, (2013), Springer: Springer Berlin, Heidelberg) · Zbl 1377.90053
[10] Megiddo, N.; Supowit, K. J., On the complexity of some common geometric location problems, SIAM J. Comput., 13, 1, 182-196, (1984) · Zbl 0534.68032
[11] Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L., Optimal packing and covering in the plane are NP-complete, Inf. Process. Lett., 12, 3, 133-137, (1981) · Zbl 0469.68053
[12] Megiddo, N., Linear-time algorithms for linear programming in R^3 and related problems, SIAM J. Comput., 12, 4, 759-776, (1983) · Zbl 0521.68034
[13] Ben-Moshe, B.; Bhattacharya, B.; Shi, Q., Efficient algorithms for the weighted 2-center problem in a cactus graph, (International Symposium on Algorithms and Computation, (2005), Springer: Springer Berlin Heidelberg), 693-703 · Zbl 1175.05125
[14] Hwang, R. Z.; Lee, R. C.T.; Cheng, R. C., The slab dividing approach to solve the Euclidean p-center problem, Algorithmica, 9, 1, 1-22, (1983) · Zbl 0766.68136
[15] Drezner, Z., The p-center problem - heuristics and optimal algorithms, J. Oper. Res. Soc., 35, 8, 741-748, (1984) · Zbl 0544.90024
[16] Daskin, M. S., A new approach to solving the vertex p-center problem to optimality: algorithm and computational results, Commun. Oper. Res. Soc. Jpn., 45, 9, 428-436, (2000)
[17] Vazirani, V. V., Approximation Algorithms, (2013), Springer Science & Business Media · Zbl 1005.68002
[18] Bello, L.; Blanquero, R.; Carrizosa, E., On minimax-regret Huff location models, Comput. Oper. Res., 38, 1, 90-97, (2011) · Zbl 1231.90263
[19] Roostapour, V.; Kiarazm, I.; Davoodi, M., Deterministic algorithm for 1-median 1-center two-objective optimization problem, Top. Theor. Comput. Sci., LNCS, 9541, 164-178, (2016) · Zbl 06562108
[20] Marín, A., The discrete facility location problem with balanced allocation of customers, Eur. J. Oper. Res., 210, 1, 27-38, (2011) · Zbl 1207.90071
[21] Filipović, V.; Kratica, J.; Savić, A.; Dugošija, D., The modification of genetic algorithms for solving the balanced location problem, (Proceedings Of The Fifth Balkan Conference In Informatics, (2012), ACM), 243-246
[22] Kratica, J.; Leitner, M.; Ljubić, I., Variable neighborhood search for solving the balanced location problem, Electr. Notes Discrete Math., 39, 21-28, (2012) · Zbl 1268.90149
[23] Mišković, S.; Zorica, S., Memetic algorithm for the balanced resource location problem with preferences, (Information, Intelligence, Systems and Applications (IISA), 2015 6th International Conference on, (2015), IEEE)
[24] Barbati, M.; Piccolo, C., Equality measures properties for location problems, Optim. Lett., 10, 5, 1-18, (2016)
[25] Barbati, M., Models and Algorithms for Facility Location Problems with Equity Considerations, (2013), PhD thesis
[26] Barbati, M.; Bruno, G.; Marín, A., Balancing the arrival times of users in a two-stage location problem, Ann. Oper. Res., 1-16, (2015)
[27] Zhou, G.; Hokey, M.; Mitsuo, G., The balanced allocation of customers to multiple distribution centers in the supply chain network: a genetic algorithm approach, Comput. Ind. Eng., 43, 1, 251-261, (2002)
[28] Miettinen, K. M., Nonlinear Multiobjective Optimization, (1999), Kluwer academic · Zbl 0949.90082
[29] Khuller, S.; Sussmann, Y. J., The capacitated k-center problem, SIAM J. Discrete Math., 13, 3, 403-418, (2000) · Zbl 0947.05073
[30] Ö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
[31] Alimonti, P.; Kann, V., Some APX-completeness results for cubic graphs, Theor. Comput. Sci., 237, 1, 123-134, (2000) · Zbl 0939.68052
[32] Masuyama, S.; Ibaraki, T.; Hasegawa, T., The computational complexity of the m-center problems on the plane, IEICE TRANSACTIONS (1976-1990), 64, 2, 57-64, (1981)
[33] Coello, C. C.A.; van Veldhuizen, D. A.; Lamont, G. B., Evolutionary Algorithms For Solving Multi-Objective Problems, 242, (2002), Kluwer Academic: Kluwer Academic New York · Zbl 1130.90002
[34] de Berg, M.; Cheong, O.; van Kreveld, M.; Overmans, M., Computational Geometry: Algorithms and Applications, (2008), Springer-Verlag: Springer-Verlag Berlin
[35] Deb, K., Multi-Objective Optimization using Evolutionary Algorithms, (2001), Wiley · Zbl 0970.90091
[36] Karasakal, E.; Silav, A., A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage, Top, 24, 1, 206-232, (2016) · Zbl 1338.90373
[37] Gowda, I.; Kirkpatrick, D.; Lee, D.; Naamad, A., Dynamic Voronoi diagrams, IEEE Trans. Inf. Theory, 29, 5, 724-731, (1983) · Zbl 0516.94030
[38] Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast elitist non-dominated sorting genetic algorithm for multi-objective: NSGA-II, (Proceedings of the Parallel Problem Solving from Nature VI Conference, (2000), Springer-Verlag), 846-858
[39] Jensen, M. T., Reducing the run-time complexity of multi-objective EAs: the NSGA-II and other algorithm, IEEE Trans. Evol. Comput., 7, 5, 503-515, (2003)
[40] Fränti, P.; Sieranoja, S., K-means properties on six clustering benchmark datasets, Appl. Intell., 1-17, (2017)
[41] Davoodi, M.; Mohades, A.; Rezaei, J., A genetic algorithm for the constrained coverage problem, Applications of Soft Computing, 347-356, (2009), Springer-Verlag: Springer-Verlag Berlin Heidelberg, AISC 58
[42] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multi-objective evolutionary algorithms: empirical results, Evol. Comput., 8, 2, 173-195, (2000)
[43] Schott, J. R., Fault Tolerant Design Using Single and Multi-Criteria Genetic Algorithms, (1995), Department of Aeronautics and Astronautics, Massachusetts Institute of Technology: Department of Aeronautics and Astronautics, Massachusetts Institute of Technology Boston, MA, Master’s Thesis
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.