Home Fuzzy Information and Engineering Article
PDF (3.5 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Article | Open Access

2-Median Problem on a Tree with Grey Parameters

Jafar Fathali1(), Davood Darvishi Salookolaei2
Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood 3619995161, Iran
Department of Mathematics, Payame Noor University, Tehran 193954697, Iran
Show Author Information

Abstract

The purpose of this paper is to find solutions to the 1-median and 2-median problems on a tree network with grey parameters. Generally, the p-median problem asks for finding a set of p facilities on the vertices of a given tree such that the sum of weighted distances from vertices to the closest facility is minimized. First, the 1-median problem with grey weight of vertices and edge lengths is considered, and by showing some properties for this problem, a linear time algorithm is proposed. Then an edge deletion method with time complexity O(n2) is developed to find a solution to the 2-median problem with grey parameters. Moreover, some new concepts of networks with grey parameters are defined in this paper.

Keywords

facility locationgrey number2-median problem1-median problem

References

[1]

S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, Oper. Res., vol. 12, no. 3, pp. 450–459, 1964.

Crossref Google Scholar
[2]

O. Kariv and S. L. Hakimi, An algorithmic approach to network location problems. I: The p-centers, SIAM J. Appl. Math., vol. 37, no. 3, pp. 513–538, 1979.

Crossref Google Scholar
[3]

A. J. Goldman, Optimal center location in simple networks, Transp. Sci., vol. 5, no. 2, pp. 212–221, 1971.

Crossref Google Scholar
[4]

P. B. Mirchandani and A. Oudjit, Localizing 2-medians on probabilistic and deterministic tree networks, Networks, vol. 10, no. 4, pp. 329–350, 1980.

Crossref Google Scholar
[5]

B. Gavish and S. Sridhar, Computing the 2-median on tree networks in O(n lg n) time, Networks, vol. 26, no. 4, pp. 305–317, 1995.

Crossref Google Scholar
[6]

A. Oudjit and M. F. Stallmann, Efficient algorithms for finding 2-medians of a tree, Networks, vol. 77, no. 3, pp. 383–402, 2021.

Crossref Google Scholar
[7]
G. Y. Handler and P. B. Mirchandani, Location on Networks : Theory and Algorithms. Cambridge, MA, USA: MIT Press, 1979.
[8]
P. B. Mirchandani and R. L. Francis, Discrete Location Theory. New York, NY, USA: Wiley, 1990.
[9]
M. S. Daskin, Network and Discrete Location : Models, Algorithms, and Applications. New York, NY, USA: Wiley, 1995.
Crossref
[10]

M. J. Canós, C. Ivorra, and V. Liern, An exact algorithm for the fuzzy p-median problem, Eur. J. Oper. Res., vol. 116, no. 1, pp. 80–86, 1999.

Crossref Google Scholar
[11]
D. Kutangila-Mayoya and J. L. Verdegay, p-median problems in a fuzzy environment, Mathw. Soft Comput., vol. 12, pp. 97–106, 2005.
[12]

F. Taleshian, J. Fathali, and N. A. Taghi-Nezhad, Fuzzy majority algorithms for the 1-median and 2-median problems on a fuzzy tree, Fuzzy Information and Engineering, vol. 10, no. 2, pp. 225–248, 2018.

Crossref Google Scholar
[13]

S. M. A. Nayeem and M. Pal, The p-center problem on fuzzy networks and reduction cost, Iranian Journal of Fuzzy Systems, vol. 5, pp. 1–26, 2008.

Google Scholar
[14]

J. Fathali and A. Jamalian, Locating multiple facilities in convex sets with fuzzy data and block norms, Appl. Math., vol. 3, no. 12, pp. 1950–1958, 2012.

Crossref Google Scholar
[15]

K. Yang, Y. K. Liu, and G. Q. Yang, Solving fuzzy p-hub center problem by genetic algorithm incorporating local search, Appl. Soft Comput., vol. 13, no. 5, pp. 2624–2632, 2013.

Crossref Google Scholar
[16]

J. A. M. Pérez, J. M. M. Vega, and J. L. Verdegay, Fuzzy location problems on networks, Fuzzy Sets Syst., vol. 142, no. 3, pp. 393–405, 2004.

Crossref Google Scholar
[17]

F. Taleshian and J. Fathali, A mathematical model for fuzzy p-median problem with fuzzy weights and variables, Adv. Oper. Res., vol. 2016, pp. 1–13, 2016.

Crossref Google Scholar
[18]

F. Taleshian, J. Fathali, and N. A. Taghi-Nezhad, Finding the absolute and vertex center of a fuzzy tree, Transp. Lett., vol. 14, no. 6, pp. 591–599, 2022.

Crossref Google Scholar
[19]

J. L. Deng, Control problems of grey systems, Syst. Contr. Lett., vol. 1, no. 5, pp. 288–294, 1982.

Crossref Google Scholar
[20]

G. Huang, B. W. Baetz, and G. G. Patry, A grey linear programming approach for municipal solid waste management planning under uncertainty, Civ. Eng. Syst., vol. 9, no. 4, pp. 319–335, 1992.

Crossref Google Scholar
[21]

G. H. Huang and R. D. Moore, Grey linear programming, its solving approach, and its application, Int. J. Syst. Sci., vol. 24, no. 1, pp. 159–172, 1993.

Crossref Google Scholar
[22]

G. H. Huang, B. W. Baetz, and G. G. Patry, Grey fuzzy integer programming: An application to regional waste management planning under uncertainty, Socio Econ. Plan. Sci., vol. 29, no. 1, pp. 17–38, 1995.

Crossref Google Scholar
[23]

Q. X. Li, The cover solution of grey linear programming, J. Grey Syst., vol. 19, pp. 309–320, 2007.

Google Scholar
[24]

S. H. Nasseria, A. Yazdani, and D. Darvishi, A primal simplex algorithm for solving linear programming problem with grey cost coefficients, J. New Res. Math., vol. 1, no. 4, pp. 121–141, 2016.

Google Scholar
[25]

H. Nasseri and D. Darvishi, Duality results on grey linear programming problems, J. Grey Syst., vol. 30, no. 3, pp. 127–142, 2018.

Google Scholar
[26]

D. Darvishi and P. Babaei, Grey prediction in linear programming problems, Int. J. Appl. Oper. Res., vol. 9, pp. 11–18, 2019.

Google Scholar
[27]

D. D. Salookolaei and S. H. Nasseri, A dual simplex method for grey linear programming problems based on duality results, Grey Syst. Theory Appl., vol. 10, no. 2, pp. 145–157, 2020.

Crossref Google Scholar
[28]

D. Darvishi, S. Liu, and J. Y. L. Forrest, Grey linear programming: A survey on solving approaches and applications, Grey Syst. Theory Appl., vol. 11, no. 1, pp. 110–135, 2021.

Crossref Google Scholar
[29]

J. Fathali, Grey median problem and vertex optimality, Stat., Optim. Inf. Comput., vol. 11, no. 3, pp. 670–676, 2023.

Crossref Google Scholar
[30]

D. Darvishi, J. Forrest, and S. Liu, A comparative analysis of grey ranking approaches, Grey Syst. Theory Appl., vol. 9, no. 4, pp. 472–487, 2019.

Crossref Google Scholar
[31]
S. F. Liu and J. Y. L. Forrest, Grey Information : Theory and Practical Applications. London, UK: Springer-Verlag, 2006.
Fuzzy Information and Engineering
Volume 15 Issue 4,
December 2023
Pages 362-377
DOI: 10.26599/FIE.2023.9270027
Cite this article:
Fathali J, Salookolaei DD. 2-Median Problem on a Tree with Grey Parameters. Fuzzy Information and Engineering, 2023, 15(4): 362-377. https://doi.org/10.26599/FIE.2023.9270027
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return