• Previous Article
    Decision-making in a retailer-led closed-loop supply chain involving a third-party logistics provider
  • JIMO Home
  • This Issue
  • Next Article
    Performance analysis and optimization research of multi-channel cognitive radio networks with a dynamic channel vacation scheme
doi: 10.3934/jimo.2021017

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

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

* Corresponding author: Jafar Fathali

Received  June 2020 Revised  November 2020 Published  December 2020

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.

Citation: Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021017
References:
[1]

B. AlizadehE. 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.  Google Scholar

[2]

B. AlizadehR. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

O. BermanZ. DreznerA. 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.  Google Scholar

[7]

R. W. BultermanF. W. Van-Der-SommenG. Zwaan T. VerhoeffA. 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.  Google Scholar

[8]

R. E. BurkardC. Pleschiutschnig and J. Z. Zhang, Inverse median problems, Discrete Optimization, 1 (2004), 23-39.  doi: 10.1016/j.disopt.2004.03.003.  Google Scholar

[9]

R. E. BurkardC. 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.  Google Scholar

[10]

M. C. CaiX. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, arXiv preprint, arXiv: 1803.10332, 2018. Google Scholar

[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.  Google Scholar

[15]

M. Gavalec and O. Hudec, Balanced location on a graph, Optimization, 35 (1995), 367-372.  doi: 10.1080/02331939508844156.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

P. B. Mirchandani and R. Francis, Discrete Location Theory, J. Wiley, 1990.  Google Scholar

[24]

M. NazariJ. FathaliM. 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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

S. OmidiJ. 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.  Google Scholar

[28]

V. H. PhamK. 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.  Google Scholar

[29]

T. SayarJ. 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.   Google Scholar

[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.  Google Scholar

show all references

References:
[1]

B. AlizadehE. 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.  Google Scholar

[2]

B. AlizadehR. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

O. BermanZ. DreznerA. 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.  Google Scholar

[7]

R. W. BultermanF. W. Van-Der-SommenG. Zwaan T. VerhoeffA. 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.  Google Scholar

[8]

R. E. BurkardC. Pleschiutschnig and J. Z. Zhang, Inverse median problems, Discrete Optimization, 1 (2004), 23-39.  doi: 10.1016/j.disopt.2004.03.003.  Google Scholar

[9]

R. E. BurkardC. 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.  Google Scholar

[10]

M. C. CaiX. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, arXiv preprint, arXiv: 1803.10332, 2018. Google Scholar

[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.  Google Scholar

[15]

M. Gavalec and O. Hudec, Balanced location on a graph, Optimization, 35 (1995), 367-372.  doi: 10.1080/02331939508844156.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

P. B. Mirchandani and R. Francis, Discrete Location Theory, J. Wiley, 1990.  Google Scholar

[24]

M. NazariJ. FathaliM. 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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[27]

S. OmidiJ. 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.  Google Scholar

[28]

V. H. PhamK. 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.  Google Scholar

[29]

T. SayarJ. 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.   Google Scholar

[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.  Google Scholar

Figure 1.  The tree $ T $ with 10 verteices
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
$ 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
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
$ 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
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
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
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
$ 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
[1]

Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281

[2]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[3]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[4]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361

[5]

Todd Hurst, Volker Rehbock. Optimizing micro-algae production in a raceway pond with variable depth. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021027

[6]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[7]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[8]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (27)
  • HTML views (78)
  • Cited by (0)

Other articles
by authors

[Back to Top]