Inverse Balanced Facility Location Problem in the Plane

Nemati, Sina; Fathali, Jafar; Poureidi, Abolfazl

doi:10.30473/coam.2026.76242.1350

- فلوچارت مراحل ورود و ثبت نام در سامانه نشریات علمی وزارت عتف

- راه اندازی سیستم مدیریت نشریات علمی دانشگاه پیام نور

تعداد نشریات	49
تعداد شماره‌ها	1,264
تعداد مقالات	10,909
تعداد مشاهده مقاله	22,310,504
تعداد دریافت فایل اصل مقاله	14,992,004

	Inverse Balanced Facility Location Problem in the Plane
Control and Optimization in Applied Mathematics
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 18 اسفند 1404 اصل مقاله (593.5 K)
نوع مقاله: Research Article
شناسه دیجیتال (DOI): 10.30473/coam.2026.76242.1350
نویسندگان
Sina Nemati؛ Jafar Fathali^* ؛ Abolfazl Poureidi
Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran
چکیده
Classical inverse location models aim to modify problem parameters such that pre-specified facility locations become optimal with respect to a given objective. This paper addresses a fundamentally different variant: the inverse balanced facility location problem in the Euclidean plane, in which parameters are adjusted so as to achieve an equitable distribution of client demand between two given facilities. Specifically, given a set of n weighted points in the plane and two predetermined facility locations, the objective is to minimally modify either the weights or the coordinates of the client points such that the absolute difference in total demand assigned to each facility-referred to as the unbalancing number-is minimized. For the weight-modification case, we establish that the planar problem is structurally equivalent to its network counterpart and is therefore solvable in O(n Log n) time under any L_p norm, via an existing linear programming formulation. For the coordinate-modification case under the Euclidean norm, we exploit the isometric property of orthogonal rotations to prove that thetwo-dimensional problem reduces, without loss of generality, to a one-dimensional problem along the perpendicular bisector of the segment joining the two facilities. Leveraging this reduction, we design three novel greedy algorithms-IFLP1, IFLP2, and IFLP3-that prioritize minimization of the unbalancing number, minimization of the total transfer cost, and a hybrid criterion balancing both objectives, respectively. Under uniform weights and identical modification costs, all three algorithms are proven to yield optimal solutions and operate within O(n²) time complexity. Extensive computational experiments on standard benchmark datasets and randomly generated instances demonstrate that IFLP1 achieves the lowest CPU time and smallest unbalancing number, while IFLP3 yields superior performance in termsof total transfer cost and is recommended for practical applications
تازه های تحقیق
The inverse balanced two-facility location problem in the Euclidean plane is formally introduced and studied for the first time. The weight-modification variant in the plane is proven to be equivalent to its network counterpart, solvable in O(n log n) time under any L_p- norm. A coordinate-reduction theorem is established: exploiting the isometric property of Euclidean rotations, the planar problem reduces to an equivalent one-dimensional problem without loss of generality. Three greedy algorithms (IFLP1, IFLP2, IFLP3) are proposed for the coordinate-modification case, targeting the unbalancing number, transfer cost, and a hybrid criterion, respectively. Under uniform weights and identical modification costs, all three algorithms are proven optimal with O(n²) time complexity. Experimental results on standard benchmarks and synthetic datasets confirm that IFLP1 minimizes CPU time and unbalancing number, while IFLP3 achieves the lowest transfer cost and is recommended for practical use. A sensitivity analysis reveals that initial facility weight imbalance is the primary driver of computational effort and transfer cost, with no systematic dependence on facility index selection.
کلیدواژه‌ها
Facility location؛ Inverse facility location؛ Balanced allocation؛ Greedy algorithm؛ Coordinate modification؛ Euclidean plane

مراجع
[1] Baroughi-Bonab F., Burkard R.E., Alizadeh B. (2010). “Inverse median location problems with variable coordinates”. Central European Journal of Operations Research, 18, 365– 381. DOI: https://doi.org/10.1007/s10100-009-0114-2 [2] Beasley J.E. (1990). “OR-Library: Distributing test problems by electronic mail”. Journal of the Operational Research Society, 41, 1069–1072. DOI: https://doi.org/10. 1057/jors.1990.166 [3] Berman O., Drezner Z., Tamir A., Wesolowsky G.O. (2009). “Optimal location with equitable loads”. Annals of Operations Research, 167, 307–325. DOI: https://doi.org/ 10.1007/s10479-008-0339-9 [4] Burkard R.E., Galavii M., Gassner E. (2010). “The inverse Fermat-Weber problem”. European Journal of Operational Research, 206, 11–17. DOI: https://doi.org/10.1016/j.ejor.2010.01.046 [5] Barbati M., Piccolo C. (2015). “Equality measures properties for location problems”. Optimization Letters, 10, 903–920. DOI: https://doi.org/10.1007/ s11590-015-0968-2 [6] Burkard R.E., Pleschiutschnig C., Zhang J.Z. (2004). “Inverse median problems”. Discrete Optimization, 1, 23–39. DOI: https://doi.org/10.1016/j.disopt.2004.03. 003 [7] Burkard R.E., Pleschiutschnig C., Zhang J.Z. (2008). “The inverse 1-median problem on a cycle”. Discrete Optimization, 5, 242–253. DOI: https://doi.org/10.1016/j. disopt.2006.11.008 [8] Eiselt H.A., Laporte G. (1995). “Objectives in location problems”. In: Drezner Z. (Ed.), Facility Location: A Survey of Applications and Methods. Springer, Berlin, 151–180. DOI: https://doi.org/10.1007/978-1-4612-5355-6_9 [9] Fathali J. (2022). “A row generation method for the inverse continuous facility location problems”. Computers & Industrial Engineering, 171, 108482. DOI: https://doi.org/ 10.1016/j.cie.2022.108482 [10] Fathali J., Zaferanieh M. (2023). “The balanced 2-median and 2-maxian problems on a tree”. Journal of Combinatorial Optimization, 45, 69. DOI: https://doi.org/10. 1007/s10878-023-00997-9 [11] Galavii M. (2010). “The inverse 1-median problem on a tree and on a path”. Electronic Notes in Discrete Mathematics, 36, 1241–1248. DOI: https://doi.org/10.1016/j. endm.2010.05.157 [12] Gavalec M., Hudec O. (1995). “Balanced location on a graph”. Optimization, 35, 367–372. DOI: https://doi.org/10.1080/02331939508844156 [13] Gholami M., Fathali J. (2021). “Mathematical models for the variable weights version of the inverse minimax circle location problem”. Journal of Mathematical Modeling, 9, 137–144. DOI: https://doi.org/10.22124/jmm.2020.16786.1455 [14] Gholami M., Fathali J. (2022). “The inverse minisum circle location problem”. Yugoslav Journal of Operations Research, 32, 153–165. DOI: https://doi.org/10. 2298/YJOR200715027G [15] Gholami M., Fathali J. (2022). “Inverse minimax circle location problem with variable coordinates”. AUT Journal of Mathematics and Computing, 3, 137–146. DOI: https: //doi.org/10.22060/ajmc.2022.20756.1075 [16] Golpayegani M., Fathali J. (2026). “Greedy algorithms for the inverse center line location problem”. Expert Systems with Applications, 296, 129064. DOI: https://doi.org/10. 1016/j.eswa.2025.129064 [17] Guan X.C., Zhang B.W. (2012). “Inverse 1-median problem on trees under weighted Hamming distance”. Journal of Global Optimization, 54, 75–82. DOI: https://doi.org/10. 1007/s10898-011-9742-x [18] Landete M., Marin A. (2014). “Looking for edge-equitable spanning trees”. Computers & Operations Research, 41, 44–52. DOI: https://doi.org/10.1016/j.cor.2013.07. 023 [19] Lejeune M.A., Prasad S.Y. (2013). “Effectiveness-equity models for facility location problems on tree networks”. Networks, 62, 243–254. DOI: https://doi.org/10.1002/net.21510 [20] Marin A. (2011). “The discrete facility location problem with balanced allocation of customers”. European Journal of Operational Research, 210, 27–38. DOI: https://doi. org/10.1016/j.ejor.2010.10.012 [21] Marsh M.T., Schilling D.A. (1994). “Equity measurement in facility location analysis: A review and framework”. European Journal of Operational Research, 74, 1–17. DOI: https://doi.org/10.1016/0377-2217(94)90200-3 [22] Nazari M., Fathali J. (2023). “Inverse and reverse 2-facility location problems with equality measures on a network”. Iranian Journal of Mathematical Sciences and Informatics, 18, 211–225. DOI: https://doi.org/10.52547/ijmsi.18.1.211 [23] Nguyen K.T., Hung N.T., Nguyen-Thu H., Le T.T., Pham V.H. (2019). “On some inverse 1-center location problems”. Optimization, 68, 999–1015. DOI: https://doi.org/10. 1080/02331934.2019.1571056 [24] Omidi S., Fathali J. (2022). “Inverse single facility location problem on a tree with balancing on the distance of server to clients”. Journal of Industrial and Management Optimization, 18, 1247–1259. DOI: https://doi.org/10.3934/jimo.2021017 [25] Omidi S., Fathali J., Nazari M. (2020). “Inverse and reverse balanced facility location problems with variable edge lengths on trees”. OPSEARCH, 57, 261–273. DOI: https: //doi.org/10.1007/s12597-019-00428-6 [26] Sayar T., Fathali J., Ghiyasi M. (2024). “The inverse 1-median problem on a tree with transferring the weight of vertices”. Transactions on Combinatorics, 13, 335–350. DOI: https://doi.org/10.22108/toc.2023.136964.2047 [27] Tour-Savadkoohi N., Fathali J. (2025). “Inverse single facility location problem in the plane with variable coordinates”. arXiv:2503.07016 [math.OC]. DOI: https://doi. org/10.48550/arXiv.2503.07016 [28] Wu L., Lee J., Zhang J., Wang Q. (2013). “The inverse 1-median problem on tree networks with variable real edge lengths”. Mathematical Problems in Engineering, Article ID 313868. DOI: https://doi.org/10.1155/2013/313868
آمار تعداد مشاهده مقاله: 13 تعداد دریافت فایل اصل مقاله: 3

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Inverse Balanced Facility Location Problem in the Plane