Linear time optimal approaches for MAX-profit inverse 1-Mmdian location problems. (English) Zbl 1404.90088
Summary: This paper is concerned with a new variant of the inverse 1-median location problem in which the aim is to modify the customer weights such that a predetermined facility location becomes a 1-median location and the total profit obtained via the weight improvements is maximized. We develop novel combinatorial approaches with linear time complexities for solving the problem on tree networks and in the plane under the rectilinear and Chebyshev norms.
References:
| [1] | 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 |
| [2] | Alizadeh, B.; Burkard, RE, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58, 190-200, (2011) · Zbl 1236.90094 |
| [3] | Alizadeh, B.; Burkard, RE, Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees, Discrete Applied Mathematics, 159, 706-716, (2011) · Zbl 1220.90104 |
| [4] | Alizadeh, B.; Burkard, RE, A linear time algorithm for inverse obnoxious center location problems on networks, Central European Journal of Operations Research, 21, 585-594, (2013) · Zbl 1339.90188 |
| [5] | Alizadeh, B.; Burkard, RE; Pferschy, U., Inverse 1-center location problems with edge length augmentation on trees, Computing, 86, 331-343, (2009) · Zbl 1180.90163 |
| [6] | Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Operations Research, 28, 1130-1154, (1980) · Zbl 0449.90064 |
| [7] | Baroughi Bonab, F.; Burkard, RE; Alizadeh, B., Inverse Median location problems with variable coordinates, Central European Journal of Operations Research, 18, 365-381, (2010) · Zbl 1204.90059 |
| [8] | Baroughi Bonab, F.; Burkard, RE; Gassner, E., Inverse \(p\)-Median problems with variable edge lengths, Mathematical Methods of Operations Research, 73, 263-280, (2011) · Zbl 1216.49032 |
| [9] | Berman, O.; Ingco, DI; Odoni, A., Improving the location of minmax facility through network modification, Networks, 24, 31-41, (1994) · Zbl 0799.90074 |
| [10] | Burkard, RE; Galavii, M.; Gassner, E., The inverse Fermat-Weber problem, European Journal of Operational Research, 206, 11-17, (2010) · Zbl 1188.90209 |
| [11] | Burkard, RE; 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 |
| [12] | Burkard, RE; Gassner, E.; Hatzl, J., Reverse 2-Median problems on trees, Discrete Applied Mathematics, 156, 1963-1976, (2008) · Zbl 1216.90072 |
| [13] | Burkard, RE; Pleschiutschnig, C.; Zhang, J., Inverse Median problems, Discrete Optimization, 1, 23-39, (2004) · Zbl 1087.90038 |
| [14] | Burkard, RE; Pleschiutschnig, C.; Zhang, J., The inverse 1-Median problem on a cycle, Discrete Optimization, 5, 242-253, (2008) · Zbl 1177.90245 |
| [15] | Daskin, MS, Network and Discrete Location: Modeles, Algorithms and Applications, (1995), Wiley, New York · Zbl 0870.90076 |
| [16] | Drezner, Z.; Hamacher, HW, Facility Location: Applications and Theory, (2004), Springer, Berlin |
| [17] | Francis, RL; McGinnis, LF; White, JA, Facility Layout and Location: An Analytical Approach, (1992), Prentice Hall, Englewood Cliffs |
| [18] | Galavii, M., The inverse 1-Median problem on a tree and on a path, Electronic Notes in Discrete Mathematics, 36, 1241-1248, (2010) · Zbl 1274.90305 |
| [19] | Gassner, E., The inverse 1-Maxian problem with edge length modification, Journal of Combinatorial Optimization, 16, 50-67, (2008) · Zbl 1180.90165 |
| [20] | Gassner, E., An inverse approach to convex ordered Median problems in trees, Journal of Combinatorial Optimization, 23, 261-273, (2012) · Zbl 1243.90223 |
| [21] | Goldman, AJ, Optimal center location in simple networks, Transportation Science, 5, 212-221, (1971) |
| [22] | Guan, XC; Zhang, BW, Inverse 1-Median problem on trees under weighted Hamming distance, Journal of Global Optimization, 54, 75-82, (2012) · Zbl 1273.90237 |
| [23] | Hatzl, J., The 1-Median problem in \(\mathbb{R}^d\) with the Chebyshev-norm and its inverse problem, Electronic Notes in Discrete Mathematics, 36, 1137-1144, (2010) · Zbl 1274.90313 |
| [24] | Hua, LK, Application of mathematical models to wheat harvesting, Chinese Mathematics, 2, 539-560, (1962) |
| [25] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems, (2004), Springer, Berlin · Zbl 1103.90003 |
| [26] | Mirchandani, PB; Francis, RL, Discrete Location Theory, (1990), Wiley, New York · Zbl 0718.00021 |
| [27] | Nguyen, KT, Reverse 1-center problem on weighted trees, Optimization, 65, 253-264, (2016) · Zbl 1332.90052 |
| [28] | Nguyen, KT, Inverse 1-Median problem on block graphs with variable vertex weights, Journal of Optimization Theory and Applications, 168, 944-957, (2016) · Zbl 1338.90085 |
| [29] | Nguyen, KT; Anh, LQ, Inverse \(k\)-centrum problem on trees with variable vertex weights, Mathematical Methods of Operations Research, 82, 19-30, (2015) · Zbl 1330.90120 |
| [30] | Nguyen, KT; Chassein, A., Inverse eccentric vertex problem on networks, Central European Journal of Operations Research, 23, 687-698, (2014) · Zbl 1339.90286 |
| [31] | Nguyen, KT; Chassein, A., The inverse convex ordered 1-Median problem on trees under Chebyshev norm and Hamming distance, European Journal of Operational Research, 247, 774-781, (2015) · Zbl 1346.90712 |
| [32] | Nguyen, KT; Chi, NTL, A model for the inverse 1-Median problem on trees under uncertain costs, Opuscula Mathematica, 36, 513-523, (2016) · Zbl 1338.90086 |
| [33] | Nguyen, KT; Sepasian, AR, The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, Journal of Combinatorial Optimization, 32, 872-884, (2016) · Zbl 1354.90113 |
| [34] | Nguyen, KT; Vui, PT, The inverse \(p\)-Maxian problem on trees with variavle edge lengths, Taiwanese Journal of Mathematics, 20, 1437-1449, (2016) · Zbl 1357.90023 |
| [35] | Nickel, S.; Puerto, J., Location Theory: A Unified Approach, (2005), Springer, Berlin · Zbl 1229.90001 |
| [36] | Sepasian, AR; Rahbarnia, F., An \(\mathcal{O}(n \log n)\) algorithm for the inverse 1-Median problem on trees with variable vertex weights and edge reductions, Optimization, 64, 595-602, (2015) · Zbl 1308.90028 |
| [37] | Wang, Q.; Bai, Y., An efficient algorithm for reverse 2-Median problem on a cycle, Journal of Networks, 5, 1169-1176, (2010) |
| [38] | Yang, X.; Zhang, J., Inverse center location problem on a tree, Journal of System Science and Complexity, 21, 651-664, (2008) · Zbl 1180.90171 |
| [39] | Zhang, JZ; Liu, ZH; Ma, ZF, Some reverse location problems, European Journal of Operational Research, 124, 77-88, (2000) · Zbl 0960.90056 |
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.
