×

zbMATH — the first resource for mathematics

Classical and inverse median location problems under uncertain environment. (English) Zbl 1436.90074
Summary: In this paper, we first consider the classical \(p\)-median location problem on a network in which the vertex weights and the distances between vertices are uncertain variables. The uncertainty distribution of the optimal objective value of the \(p\)-median problem is given and the concepts of the \(\alpha\)-\(p\)-median, the most \(p\)-median and the expected \(p\)-median are introduced. Then, it is shown that the uncertain \(p\)-median problem is NP-hard on general networks. However, if the underlying network is a tree, an efficient algorithm for the uncertain 1-median problem with linear time complexity is proposed. Finally, we investigate the inverse 1-median problem on a tree with uncertain vertex weights and present a programming model for the problem. Then, it is shown that the proposed model can be reformulated into a deterministic programming model.
MSC:
90B80 Discrete location and assignment
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alp, O.; Erkut, E.; Drezner, Z., An efficient genetic algorithm for the p-median problem, Ann. Oper. Res., 10, 1387-1395 (2003)
[2] Baroughi, F.; Burkard, RE; Gassner, E., Inverse p-median problems with variable edge lengths, Math. Meth. Oper. Res., 73, 263-280 (2011) · Zbl 1216.49032
[3] Benkoczi, R.; Bhattacharya, B., A new template for solving p-median problems for trees in sub-quadratic time (extended abstract), Lect. Notes. Comput. Sci., 3669, 271-282 (2005) · Zbl 1162.90539
[4] Bongartz, I.; Calamai, P. H.; Conn, A. R., A projection method for p norm location-allocation problems, Math. Program., 66, 283-312 (1994) · Zbl 0829.90085
[5] Brimberg, J.; Drezner, Z., A new heuristic for solving the p-median problem in the plane, Comput. Oper. Res, 40, 427-437 (2013) · Zbl 1349.90557
[6] Burkard, RE; Krarup, J., A linear algorithm for the pos/neg-weighted 1-median problem on a cactus, Computing, 60, 193-215 (1998) · Zbl 0904.90098
[7] Burkard, RE; Pleschiutschnig, C.; Zhan, J., Inverse median problems, Discrete. Optim., 1, 23-39 (2004) · Zbl 1087.90038
[8] Burkard, RE; Pleschiutschnig, C.; Zhan, J., The inverse 1-median problem on a cycle, Discrete. Optim., 5, 242-253 (2008) · Zbl 1177.90245
[9] Chen, R., Solution of minisum and minimax location-allocation problems with Euclidean distances, Nav. Res. Logist. Q., 30, 449-459 (1983)
[10] Cooper, L., Location-allocation problems, Oper. Res., 11, 331-343 (1963) · Zbl 0113.14201
[11] Cooper, L., Heuristic methods for location-allocation problems, SIAM. Rev., 6, 37-53 (1964) · Zbl 0956.90014
[12] Daskin, MS, Network and discrete location: models, algorithms and applications (2013)
[13] Drezner, Z., The planar two-center and two-median problems, Trans. Sci., 18, 351-361 (1984)
[14] Drezner, Z.; Brimberg, J.; Mladenovic, N.; Salhi, S., New heuristic algorithms for solving the planar p-median problem, Comput. Oper. Res., 62, 296-304 (2015) · Zbl 1348.90388
[15] Eilon, S.; Watson-Gandy, CDT, Christofides N. Distribution management: mathematical modeling and practical analysis (1971), Hafner: New York, Hafner
[16] Eiselt, HA; Marianov, V., Foundations of location analysis. Operations Research and Management Science (2011), New York: Springer, New York · Zbl 1351.90007
[17] Gao, Y., Uncertain models for single facility location problems on networks, Appl. Math. Model., 36, 2592-2599 (2012) · Zbl 1246.90083
[18] Gao, Y.; Qin, Z., A chance constrained programming approach for uncertain p-hub center location problem, Comput. Ind. Eng., 102, 10-20 (2016)
[19] Galavii, M. T., he inverse 1-median problem on a tree and on a path, Electron. Notes Disrete. Math., 36, 1241-1248 (2010) · Zbl 1274.90305
[20] Gassner, E., The inverse 1-maxian problem with edge length modification, J. Comb. Optim., 16, 50-67 (2008) · Zbl 1180.90165
[21] Gavish, B.; Sridhar, S., Computing the 2-median on tree networks in O(n log n) time, Networks, 26, 305-317 (1995) · Zbl 0856.90065
[22] Goldman, AJ, Optimal center location in simple networks, Transp. Sci., 5, 212-221 (1971)
[23] Guan, X.; Zhang, B., Inverse 1-median problem on trees under weighted Hamming distance, J. Global. Optim., 54, 75-82 (2012) · Zbl 1273.90237
[24] Guan, X.; Zhang, B., Inverse 1-median problem on trees under weighted l1_∞ norm, Lect. Notes Comput. Sci., 6124, 150-160 (2010) · Zbl 1286.90082
[25] Hakimi, SL, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res., 12, 450-459 (1964) · Zbl 0123.00305
[26] Hakimi, SL, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Oper. Res., 13, 462-475 (1965) · Zbl 0135.20501
[27] Huang, X.; Hao, D., Modelling uncapacitated facility location problem with uncertain customers positions, J. Intell. Fuzzy. Sys., 28, 2569-2577 (2015)
[28] Hatzl, J., 2-balanced ows and the inverse 1-median problem in the Chebyshev space, Discrete. Optim., 9, 137-148 (2012) · Zbl 1254.90100
[29] Hua, L., Applications of mathematical models for wheat harvesting, Chin. Mathematics., 2, 77-91 (1962)
[30] Kariv, O.; Hakimi, SL, An algorithmic approach to network location problem, Part 2: the p-median, SIAM. J. Appl. Math., 37, 539-560 (1979) · Zbl 0432.90075
[31] Liu, B., Some research problems in uncertainty theory, J. Uncertain. Syst., 3, 3-10 (2009)
[32] Liu, B., Uncertainty Theory (2007), Berlin: Springer-Verlag, Berlin
[33] Liu, B., Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty (2010), Berlin: Springer-Verlag, Berlin
[34] Liu, YH; Ha, MH, Expected value of function of uncertain variables, J. Uncertain. Syst., 4, 3, 181-186 (2010)
[35] Liu, X., Uncertain programming model for location problem of multi-product logistics distribution centers, Appl. Math. Sci., 9, 6543-6558 (2015)
[36] Love, RF, Facilities location: models and methods (1988)
[37] Love, RF, One dimensional facility location-allocation using dynamic programming, Manage. Sci., 22, 614-617 (1976) · Zbl 0318.90054
[38] Love, RF; Morris, JG, A computation procedure for the exact solution of location-allocation problems with rectangular distances, Nav. Res. Logist. Q., 22, 441-453 (1975) · Zbl 0338.90057
[39] Mirchandani, PB, The p-median problem and generalizations. in Discrete location theory (1990), New York: Wiley-Interscience, New York
[40] Nguyen, KT, Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory. Appl., 168, 944-957 (2016) · Zbl 1338.90085
[41] Nguyen, KT; Chi, NTL, A model for the inverse 1-median problem on trees under uncertain costs, Opusc. Math., 36, 513-523 (2016) · Zbl 1338.90086
[42] Peng, Z.; Iwamura, K., A sufficient and necessary condition of uncertainty distribution, J. Interdiscip. Math., 2, 539-560 (2010)
[43] Qin, Z.; Gao, Y., Uncapacitated p-hub location problem with fixed costs and uncertain ows, J. Intell. Manuf., 28, 705-716 (2017)
[44] Sepasian, AR; Rahbarnia, F., An 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
[45] Schobel, A.; Scholz, D., The big cube small cube solution method for multi-dimensional facility location problems, Comput. Oper. Res., 37, 115-122 (2010) · Zbl 1171.90451
[46] Sherali, HD; Shetty, CM, The rectilinear distance location-allocation problem, AIIE. Trans., 9, 136-143 (1997)
[47] Sherali, HD; Tuncbilek, CH, A squared Euclidean distance location-allocation problem, Nav. Res. Logist., 39, 447-469 (1992) · Zbl 0763.90061
[48] Tamir, A., An O(pn^2) algorithm for the p-median and related problems on tree graphs, Oper. Res. Lett., 19, 59-64 (1996) · Zbl 0865.90089
[49] Wang, KE; Yang, Q., Hierarchical facility location for the reverse logistics network design under uncertainty, J. Uncertain. Syst., 8, 255-270 (2014)
[50] Wen, M. Q Z.; Kang, R.; Yang, Y., The capacitated facility location-allocation problem under uncertain environment, J. Intell. Fuzzy. Syst., 29, 2217-2226 (2015) · Zbl 1361.90043
[51] Zhang, B.; Peng, J.; Li, S., Covering location problem of emergency service facilities in an uncertain environment, Appl. Math. Model., 51, 429-447 (2017) · Zbl 07166270
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.