Inverse single facility location problem on a tree with balancing on the distance of server to clients

Shahede Omidi; Jafar Fathali

doi:10.3934/jimo.2021017

Article Contents

2022, Volume 18, Issue 2: 1247-1259. Doi: 10.3934/jimo.2021017

This issue Previous Article Branching improved Deep Q Networks for solving pursuit-evasion strategy solution of spacecraft Next Article Solution method for discrete double obstacle problems based on a power penalty approach

Inverse single facility location problem on a tree with balancing on the distance of server to clients

Shahede Omidi and
Jafar Fathali^,

Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran

^* Corresponding author: Jafar Fathali
^* Corresponding author: Jafar Fathali

Received: May 31, 2020

Revised: October 31, 2020

Early access: December 2020

Published: March 2022

Abstract Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by

Abstract

We introduce a case of inverse single facility location problem on a tree where by minimum modifying in the length of edges, the difference of distances between the farthest and nearest clients to a given facility is minimized. Two cases are considered: bounded and unbounded nonnegative edge lengths. In the unbounded case, we show the problem can be reduced to solve the problem on a star graph. Then an $ O(nlogn) $ algorithm is developed to find the optimal solution. For the bounded edge lengths case an algorithm with time complexity $ O(n^2) $ is presented.

Keywords:

Mathematics Subject Classification: Primary: 90B80; Secondary: 90B06.

Citation:

FullText(HTML)

Figure 1. The tree $ T $ with 10 verteices

Download: Full-size image PowerPoint slide

Table 1. The lengths and costs of changing lengths of edges in tree $ T $

$ e_i $	$ l_i $	$ c_i^+ $	$ c_i^- $
$ e_1=(v_1,v_2) $	3	1	2
$ e_2=(v_2,x) $	3	3	1
$ e_3=(x,v_3) $	5	2	2
$ e_4=(v_3,v_{4}) $	2	1	3
$ e_5=(v_{4},v_{5}) $	8	1	4
$ e_6=(x,v_{6}) $	1	5	3
$ e_7=(v_6,v_7) $	2	3	1
$ e_8=(x,v_{8}) $	3	5	2
$ e_9=(v_{8},v_{9}) $	4	3	4
$ e_{10}=(v_{9},v_{10}) $	3	4	4

| Show Table

DownLoad: CSV

Table 2. The edge length bounds of the tree $ T $

$ e_i $	$ l_i $	$ \underline{l_i} $	$ \bar{l_i} $
$ e_1=(v_1,v_2) $	3	1	4
$ e_2=(v_2,x) $	3	2	6
$ e_3=(x,v_3) $	5	1	7
$ e_4=(v_3,v_{4}) $	2	1	5
$ e_5=(v_{4},v_{5}) $	8	4	10
$ e_6=(x,v_{6}) $	1	1	4
$ e_7=(v_6,v_7) $	2	1	5
$ e_8=(x,v_{8}) $	3	1	7
$ e_9=(v_{8},v_{9}) $	4	2	8
$ e_{10}=(v_{9},v_{10}) $	3	1	6

| Show Table

DownLoad: CSV

Table 3. The iterations result for Example 2

Iteration	$ P_1 $	$ P_2 $	$ C_{P_1} $	$ C_{P_2} $	$ f_1 $	$ f_2 $
1	$ \{p_1\} $	$ \{p_2\} $	$ c^-_3=2 $	$ c^+_6=5 $	8	10
2	$ \{p_1\} $	$ \{p_2,p_3\} $	$ c^-_4=3 $	-	11	9
3	$ \{p_1,p_4\} $	$ \{p_2,p_3\} $	$ c^-_5+c^-_8=6 $	-	23	7
4	$ \{p_1,p_4\} $	$ \{p_2,p_3\} $	$ c^-_5+c^-_9=16 $	-	39	5

| Show Table

DownLoad: CSV

Table 4. The optimal edge lengths for Example 2

$ e_i $	optimal $ l_i $	$ \underline{l_i} $	$ \bar{l_i} $
$ e_1=(v_1,v_2) $	3	1	4
$ e_2=(v_2,x) $	3	2	6
$ e_3=(x,v_3) $	1	1	7
$ e_4=(v_3,v_{4}) $	1	1	5
$ e_5=(v_{4},v_{5}) $	4	4	10
$ e_6=(x,v_{6}) $	1	1	4
$ e_7=(v_6,v_7) $	2	1	5
$ e_8=(x,v_{8}) $	1	1	7
$ e_9=(v_{8},v_{9}) $	2	2	8
$ e_{10}=(v_{9},v_{10}) $	3	1	6

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	B. Alizadeh, E. Afrashteh and F. Baroughi, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, Journal of Optimization Theory and Applications, 178 (2018), 914-934. doi: 10.1007/s10957-018-1334-1.
[2]	B. Alizadeh, R. E. Burkard and U. Pferschy, Inverse 1-center location problems with edge length augmentation on trees, Computing, 86 (2009), 331-343. doi: 10.1007/s00607-009-0070-7.
[3]	B. Alizadeh and R. E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011), 190-200. doi: 10.1002/net.20427.
[4]	B. Alizadeh and R. Etemad, Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theoretical Computer Science, 707 (2018), 36-45. doi: 10.1016/j.tcs.2017.10.001.
[5]	M. Barbati and C. Piccolo, Equality measures properties for location problems, Optimization Letters, 10 (2015), 903-920. doi: 10.1007/s11590-015-0968-2.
[6]	O. Berman, Z. Drezner, A. Tamir and G. O. Wesolowsky, Optimal location with equitable loads, Annals of Operations Research, 167 (2009), 307-325. doi: 10.1007/s10479-008-0339-9.
[7]	R. W. Bulterman, F. W. Van-Der-Sommen, G. Zwaan T. Verhoeff, A. J. M. Van-Gasteren and W. H. J. Feijen, On computing a longest path in a tree, Information Processing Letters, 81 (2002), 93-96. doi: 10.1016/S0020-0190(01)00198-3.
[8]	R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, Inverse median problems, Discrete Optimization, 1 (2004), 23-39. doi: 10.1016/j.disopt.2004.03.003.
[9]	R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, The inverse 1-median problem on a cycle, Discrete Optimization, 5 (2008), 242-253. doi: 10.1016/j.disopt.2006.11.008.
[10]	M. C. Cai, X. G. Yang and J. Zhang, The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218. doi: 10.1023/A:1008360312607.
[11]	M. Davoodi, k-Balanced Center Location problem: A new multi-objective facility location problem, Computers & Operations Research, 105 (2019), 68-84. doi: 10.1016/j.cor.2019.01.009.
[12]	H. A. Eiselt and G. Laporte, Objectives in Location Problems, In: Facility Location: A Survey of Applications and Methods (eds. Z. Drezner), Springer, Berlin, (1995), 151–180. doi: 10.1007/978-1-4612-5355-6.
[13]	J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, arXiv preprint, arXiv: 1803.10332, 2018.
[14]	M. Galavii, The inverse 1-median problem on a tree and on a path, Electronic Notes in Discrete Mathematics, 36 (2010), 1241-1248. doi: 10.1016/j.endm.2010.05.157.
[15]	M. Gavalec and O. Hudec, Balanced location on a graph, Optimization, 35 (1995), 367-372. doi: 10.1080/02331939508844156.
[16]	X. C. Guan and B. W. Zhang, Inverse 1-median problem on trees under weighted Hamming distance, Journal of Global Optimization, 54 (2012), 75-82. doi: 10.1007/s10898-011-9742-x.
[17]	G. Y. Handler, Minimax location of a facility in an undirected tree networks, Transportation Sci., 7 (1973), 287-293. doi: 10.1287/trsc.7.3.287.
[18]	C. Heuberger, Inverse combinatorial optimization: a survey on problems, methods, and results, J. Comb. Optim., 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b.
[19]	M. Landete and A. Marin, Looking for edge-equitable spanning trees, Computers & Operations Research, 41 (2014), 44-52. doi: 10.1016/j.cor.2013.07.023.
[20]	M. A. Lejeune and S. Y. Prasad, Effectiveness-equity models for facility location problems on tree networks, Networks, 62 (2013), 243-254. doi: 10.1002/net.21510.
[21]	A. Marin, The discrete facility location problem with balanced allocation of customers, European Journal of Operational Research, 210 (2011), 27-38. doi: 10.1016/j.ejor.2010.10.012.
[22]	M. T. Marsh and D. A. Schilling, Equity measurement in facility location analysis: a review and framework, European Journal of Operational Research, 74 (1994), 1-17. doi: 10.1016/0377-2217(94)90200-3.
[23]	P. B. Mirchandani and R. Francis, Discrete Location Theory, J. Wiley, 1990.
[24]	M. Nazari, J. Fathali, M. Nazari and S. M. Varedi-Koulaei, Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane, Production and Operations Management, 9 (2018), 115-137.
[25]	K. T. Nguyen, Inverse 1-median problem on block graphs with variable vertex weights, Journal of Optimization Theory and Applications, 168 (2016), 944-957. doi: 10.1007/s10957-015-0829-2.
[26]	K. T. Nguyen and A. R. Sepasian, The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, 32 (2016), 872-884. doi: 10.1007/s10878-015-9907-5.
[27]	S. Omidi, J. Fathali and M. Nazari, Inverse and reverse balanced facility location problems with variable edge lengths on trees, OPSEARCH, 57 (2020), 261-273. doi: 10.1007/s12597-019-00428-6.
[28]	V. H. Pham, K. T. Nguyen and T.T. Le, A linear time algorithm for balance vertices on trees, Discrete Optimization, 32 (2018), 37-42. doi: 10.1016/j.disopt.2018.11.001.
[29]	T. Sayar, J. Fathali and M. Ghiyasi, The problem of balancing allocation with regard to the efficiency of servers, Iranian Journal of Operations Research, 9 (2018), 29-47.
[30]	A. R. Sepasian and F. Rahbarnia, An O(nlogn) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015), 595-602. doi: 10.1080/02331934.2013.783033.