
-
Previous Article
Decision-making in a retailer-led closed-loop supply chain involving a third-party logistics provider
- JIMO Home
- This Issue
-
Next Article
Design of path planning and tracking control of quadrotor
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 |
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.
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. 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. |
[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. 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. |
[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. 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. |
show all references
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. 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. |
[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. 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. |
[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. 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. |

3 | 1 | 2 | |
3 | 3 | 1 | |
5 | 2 | 2 | |
2 | 1 | 3 | |
8 | 1 | 4 | |
1 | 5 | 3 | |
2 | 3 | 1 | |
3 | 5 | 2 | |
4 | 3 | 4 | |
3 | 4 | 4 |
3 | 1 | 2 | |
3 | 3 | 1 | |
5 | 2 | 2 | |
2 | 1 | 3 | |
8 | 1 | 4 | |
1 | 5 | 3 | |
2 | 3 | 1 | |
3 | 5 | 2 | |
4 | 3 | 4 | |
3 | 4 | 4 |
3 | 1 | 4 | |
3 | 2 | 6 | |
5 | 1 | 7 | |
2 | 1 | 5 | |
8 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
3 | 1 | 7 | |
4 | 2 | 8 | |
3 | 1 | 6 |
3 | 1 | 4 | |
3 | 2 | 6 | |
5 | 1 | 7 | |
2 | 1 | 5 | |
8 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
3 | 1 | 7 | |
4 | 2 | 8 | |
3 | 1 | 6 |
Iteration | ||||||
1 | 8 | 10 | ||||
2 | - | 11 | 9 | |||
3 | - | 23 | 7 | |||
4 | - | 39 | 5 |
Iteration | ||||||
1 | 8 | 10 | ||||
2 | - | 11 | 9 | |||
3 | - | 23 | 7 | |||
4 | - | 39 | 5 |
optimal |
|||
3 | 1 | 4 | |
3 | 2 | 6 | |
1 | 1 | 7 | |
1 | 1 | 5 | |
4 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
1 | 1 | 7 | |
2 | 2 | 8 | |
3 | 1 | 6 |
optimal |
|||
3 | 1 | 4 | |
3 | 2 | 6 | |
1 | 1 | 7 | |
1 | 1 | 5 | |
4 | 4 | 10 | |
1 | 1 | 4 | |
2 | 1 | 5 | |
1 | 1 | 7 | |
2 | 2 | 8 | |
3 | 1 | 6 |
[1] |
Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 |
[2] |
Liping Zhang, Soon-Yi Wu. Robust solutions to Euclidean facility location problems with uncertain data. Journal of Industrial & Management Optimization, 2010, 6 (4) : 751-760. doi: 10.3934/jimo.2010.6.751 |
[3] |
Gbeminiyi John Oyewole, Olufemi Adetunji. Solving the facility location and fixed charge solid transportation problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1557-1575. doi: 10.3934/jimo.2020034 |
[4] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
[5] |
Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044 |
[6] |
Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056 |
[7] |
Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 |
[8] |
Zhimin Liu, Shaojian Qu, Hassan Raza, Zhong Wu, Deqiang Qu, Jianhui Du. Two-stage mean-risk stochastic mixed integer optimization model for location-allocation problems under uncertain environment. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020094 |
[9] |
J. F. Padial. Existence and estimate of the location of the free-boundary for a non local inverse elliptic-parabolic problem arising in nuclear fusion. Conference Publications, 2011, 2011 (Special) : 1176-1185. doi: 10.3934/proc.2011.2011.1176 |
[10] |
Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. doi: 10.3934/jimo.2019061 |
[11] |
Philip Trautmann, Boris Vexler, Alexander Zlotnik. Finite element error analysis for measure-valued optimal control problems governed by a 1D wave equation with variable coefficients. Mathematical Control & Related Fields, 2018, 8 (2) : 411-449. doi: 10.3934/mcrf.2018017 |
[12] |
Kewei Zhang. On equality of relaxations for linear elastic strains. Communications on Pure & Applied Analysis, 2002, 1 (4) : 565-573. doi: 10.3934/cpaa.2002.1.565 |
[13] |
Qinglan Xia, Shaofeng Xu. On the ramified optimal allocation problem. Networks & Heterogeneous Media, 2013, 8 (2) : 591-624. doi: 10.3934/nhm.2013.8.591 |
[14] |
Monika Muszkieta. A variational approach to edge detection. Inverse Problems & Imaging, 2016, 10 (2) : 499-517. doi: 10.3934/ipi.2016009 |
[15] |
Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391 |
[16] |
Liming Zhang, Tao Qian, Qingye Zeng. Edge detection by using rotational wavelets. Communications on Pure & Applied Analysis, 2007, 6 (3) : 899-915. doi: 10.3934/cpaa.2007.6.899 |
[17] |
Dmitry Dolgopyat, Dmitry Jakobson. On small gaps in the length spectrum. Journal of Modern Dynamics, 2016, 10: 339-352. doi: 10.3934/jmd.2016.10.339 |
[18] |
Emmanuel Schenck. Exponential gaps in the length spectrum. Journal of Modern Dynamics, 2020, 16: 207-223. doi: 10.3934/jmd.2020007 |
[19] |
Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 |
[20] |
Lotfi Tadj, Zhe George Zhang, Chakib Tadj. A queueing analysis of multi-purpose production facility's operations. Journal of Industrial & Management Optimization, 2011, 7 (1) : 19-30. doi: 10.3934/jimo.2011.7.19 |
2019 Impact Factor: 1.366
Tools
Article outline
Figures and Tables
[Back to Top]