Optimal algorithms for some inverse uncapacitated facility location problems on networks. (English) Zbl 1498.90126
Summary: This paper is concerned with two variants of the inverse uncapacitated facility location problem with service cost modifications on tree networks under the rectilinear norm. In the first variant, the aim is to modify the underlying service costs in the cheapest possible way with respect to modification bounds such that a set of predetermined facility locations becomes optimal under the new parameters. Two types of this problem are investigated. The second variant asks to modify the service costs within an associated budget until the predetermined facility locations become as close as possible to the customers. Two types of this problem are also studied. We develop exact optimal algorithms for solving the problems under investigation. By an example, the efficiency of the proposed algorithms is illustrated.
MSC:
| 90B80 | Discrete location and assignment |
| 90B10 | Deterministic network models in operations research |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Afrashteh, E.; Alizadeh, B.; Baroughi, F.; Nguyen, K. T., Linear time optimal approaches for max-profit inverse 1-median location problems, Asia-Pac. J. Oper. Res., 35 (2018) · Zbl 1404.90088 |
| [2] | Afrashteh, E.; Alizadeh, B.; Baroughi, F., Optimal algorithms for integer inverse undesirable p-median location problems on weighted extended star networks, J. Oper. Res. Soc. China (2018) · Zbl 1474.90246 · doi:10.1007/s40305-018-0229-z |
| [3] | Afrashteh, E.; Alizadeh, B.; Baroughi, F., Optimal algorithms for selective variants of the classical and inverse median location problems on trees, Optim. Methods Softw., 37, 1213-1230 (2019) · Zbl 1423.90130 |
| [4] | Alizadeh, B.; Afrashteh, E., Budget-constrained inverse median facility location problem on tree networks, Appl. Math. Comput., 375 (2020) |
| [5] | Alizadeh, B.; Bakhteh, S., A modified firefly algorithm for general inverse p-median location problems under different distance norms, Opsearch, 54, 618-636 (2017) · Zbl 1397.90406 |
| [6] | Alizadeh, B.; Burkard, R. E., Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58, 190-200 (2011) · Zbl 1236.90094 |
| [7] | Alizadeh, B.; Burkard, R. E., Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees, Discrete Appl. Math., 159, 706-716 (2011) · Zbl 1220.90104 |
| [8] | Alizadeh, B.; Burkard, R. E., A linear time algorithm for inverse obnoxious center location problems on networks, Central Eur. J. Oper. Res., 21, 585-594 (2013) · Zbl 1339.90188 |
| [9] | Alizadeh, B.; Etemad, R., Linear time optimal approaches for reverse obnoxious center location problems on networks, Optimization, 65, 2025-2036 (2016) · Zbl 1351.90111 |
| [10] | Alizadeh, B.; Etemad, R., Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theor. Comput. Sci., 707, 36-45 (2018) · Zbl 1396.90092 |
| [11] | Alizadeh, B.; Burkard, R. E.; Pferschy, U., Inverse 1-center location problems with edge length augmentation on trees, Computing, 86, 331-343 (2009) · Zbl 1180.90163 |
| [12] | Alizadeh, B.; Afrashteh, E.; Baroughi, F., Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, J. Optim. Theory. Appl., 178, 914-934 (2018) · Zbl 1410.90115 |
| [13] | Alizadeh, B.; Afrashteh, E.; Baroughi, F., Inverse obnoxious p-median location problems on trees with edge length modifications under different norms, Theor. Comput. Sci., 772, 73-87 (2019) · Zbl 1426.90058 |
| [14] | Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Oper. Res., 28, 1130-1154 (1980) · Zbl 0449.90064 |
| [15] | Baroughi, F.; Burkard, R. E.; Alizadeh, B., Inverse median location problems with variable coordinates, Central Eur. J. Oper. Res., 18, 365-381 (2010) · Zbl 1204.90059 |
| [16] | Baroughi, F.; Burkard, R. E.; Gassner, E., Inverse p-median problems with variable edge lengths, Math. Methods Oper. Res., 73, 263-280 (2011) · Zbl 1216.49032 |
| [17] | Berman, O.; Ingco, D. I.; Odoni, A., Improving the location of minimum facilities through network modification, Ann. Oper. Res., 40, 1-16 (1992) · Zbl 0787.90035 |
| [18] | Burkard, R. E.; Pleschiutschnig, C.; Zhang, J., Inverse median problems, Discrete Optim., 1, 23-39 (2004) · Zbl 1087.90038 |
| [19] | Burkard, R. E.; Gassner, E.; Hatzl, J., A linear time algorithm for the reverse 1-median problem on a cycle, Networks, 48, 16-23 (2006) · Zbl 1103.90082 |
| [20] | Burkard, R. E.; Gassner, E.; Hatzl, J., Reverse 2-median problem on trees, Discrete Appl. Math., 156, 1963-1976 (2008) · Zbl 1216.90072 |
| [21] | Cai, M. C.; Yang, X. G.; Zhang, J. Z., The complexity analysis of the inverese center location problem, J. Global Optim., 15, 213-218 (1999) · Zbl 0978.90065 |
| [22] | Daskin, M. S., Network and Discrete Location: Models, Algorithms and Applications (2013), John Wiley: John Wiley, New Jersey · Zbl 1276.90038 |
| [23] | Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Oper. Res., 26, 992-1009 (1978) · Zbl 0422.90053 |
| [24] | Etemad, R.; Alizadeh, B., Some variants of reverse selective center location problem on trees under the Chebyshev and Hamming norms, Yugosl. J. Oper. Res., 27, 367-384 (2016) · Zbl 1474.90375 |
| [25] | Etemad, R.; Alizadeh, B., Reverse selective obnoxious center location problems on tree graphs, Math. Methods Oper. Res., 87, 431-450 (2018) · Zbl 1391.90372 |
| [26] | Janáček, J.; Buzna, L., An acceleration of Erlenkotter-Körkel’s algorithms for uncapacitated facility location problem, Ann. Oper. Res., 164, 97-109 (2008) · Zbl 1169.90387 |
| [27] | Kolen, A., Solving covering problems and the uncapacitated plant location problem on trees, Eur. J. Oper. Res., 12, 266-278 (1983) · Zbl 0508.90035 |
| [28] | Körkel, M., On the exact solution of large-scale simple plant location problems, Eur. J. Oper. Res., 39, 157-173 (1989) · Zbl 0673.90032 |
| [29] | Krarup, J.; Pruzan, P. M., The simple plant location problem: Survey and synthesis, Eur. J. Oper. Res., 12, 36-81 (1983) · Zbl 0506.90018 |
| [30] | Letchford, A. N.; Miller, S. J., Fast bounding procedures for large instances of the simple plant location problem, Comput. Oper. Res., 39, 985-990 (2012) · Zbl 1251.90243 |
| [31] | Mirchandani, B. P.; Francis, R. L., Discrete Location Theory (1990), John Wiley: John Wiley, New York · Zbl 0718.00021 |
| [32] | Mirzapolis Adeh, I.; Baroughi, F.; Alizadeh, B., A modified particle swarm optimization algorithm for general inverse ordered p-median location problem on networks, Facta Univ. Ser.: Math. Inform., 32, 447-468 (2017) · Zbl 1474.90245 |
| [33] | Nazari, M.; Fathali, J.; Nazari, M.; Varedi, S. M., Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane, Prod. Oper. Manage., 9, 115-137 (2019) |
| [34] | Nguyen, K. T., Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory. Appl., 168, 944-957 (2016) · Zbl 1338.90085 |
| [35] | Nguyen, K. T., The inverse 1-center problem on cycles with variable edge lengths, Central Eur. J. Oper. Res., 27, 263-274 (2019) · Zbl 1464.90084 |
| [36] | Nguyen, K. T.; Sepasian, A. R., The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, J. Comb. Optim., 32, 872-884 (2016) · Zbl 1354.90113 |
| [37] | Pham, V. H.; Nguyen, K. T., Inverse 1-median problem on trees under mixed rectilinear and Chebyshev norms, Theor. Comput. Sci., 795, 119-127 (2019) · Zbl 1517.90126 |
| [38] | Sepasian, A. R., Reverse 1-maxian problem with keeping existing 1-median, Opsearch, 56, 1-13 (2019) · Zbl 07044875 |
| [39] | Sepasian, A. R.; Rahbarnia, F., An \(####\) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64, 595-602 (2015) · Zbl 1308.90028 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
