×
Tajdin, Ali; Mahdavi, Iraj; Mahdavi-Amiri, Nezam; Sadeghpour-Gildeh, Bahram

Computing a fuzzy shortest path in a network with mixed fuzzy arc lengths using \(\alpha \)-cuts. (English) Zbl 1201.90196

Comput. Math. Appl. 60, No. 4, 989-1002 (2010).
Summary: We are concerned with the design of a model and an algorithm for computing a shortest path in a network having various types of fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using \(\alpha \)-cuts by proposing a linear least squares model to obtain membership functions for the considered additions. Then, using a recently proposed distance function for comparison of fuzzy numbers, we present a dynamic programming method for finding a shortest path in the network. Examples are worked out to illustrate the applicability of the proposed model.

Cited in 2 Documents

MSC:

90C35 Programming involving graphs or networks
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming

Keywords:

fuzzy numbers; \(\alpha \)-cut; distance function; shortest path; linear least squares; regression; dynamic programming

Software:

Algorithm 97
Cite Review PDF
Full Text: DOI

References:

[1] Chuang, T.-N.; Kung, J.-Y., The fuzzy shortest path length and the corresponding shortest path in a network, Comput. Oper. Res., 32, 1409-1428 (2005) · Zbl 1122.90437
[2] M.T. Takahashi, Contribuições ao estudo de grafos fuzzy: teoria e algoritmos, Ph.D. Thesis, Faculdade de Engenharia Elétrica e de Computação, UNICAMP, 2004.; M.T. Takahashi, Contribuições ao estudo de grafos fuzzy: teoria e algoritmos, Ph.D. Thesis, Faculdade de Engenharia Elétrica e de Computação, UNICAMP, 2004.
[3] Lin, C.; Chern, M. S., The fuzzy shortest path problem and its most vital arcs, Fuzzy Sets and Systems, 58, 343-353 (1993) · Zbl 0804.90138
[4] Nayeem, S. M.A.; Pal, M., Shortest path problem on a network with imprecise edge weight, Fuzzy Optim. Decis. Mak., 4, 293-312 (2005) · Zbl 1117.90052
[5] Okada, S.; Soper, T., A shortest path problem on a network with fuzzy arc lengths, Fuzzy Sets and Systems, 109, 129-140 (2000) · Zbl 0956.90070
[6] Dubois, D.; Prade, H., Fuzzy Sets and Systems: Theory and Applications (1980), Academic Press: Academic Press New York · Zbl 0444.94049
[7] D. Eppstein, Finding the \(k\); D. Eppstein, Finding the \(k\)
[8] Klein, C. M., Fuzzy shortest paths, Fuzzy Sets and Systems, 39, 27-41 (1991) · Zbl 0728.90090
[9] S. Okada, M. Gen, Order relation between intervals and its applications to shortest path problem, in: Proc. 15th Annu. Conf. on Computers and Industrial Engineering, vol. 25, 1993, pp. 156-167.; S. Okada, M. Gen, Order relation between intervals and its applications to shortest path problem, in: Proc. 15th Annu. Conf. on Computers and Industrial Engineering, vol. 25, 1993, pp. 156-167.
[10] S. Okada, M. Gen, Fuzzy shortest path problem, in: Proc. 16th Ann. Conf. on Computers and Industrial Engineering, vol. 27, 1994, pp. 231-247.; S. Okada, M. Gen, Fuzzy shortest path problem, in: Proc. 16th Ann. Conf. on Computers and Industrial Engineering, vol. 27, 1994, pp. 231-247.
[11] Dubois, D.; Prade, H., Ranking fuzzy numbers in the setting of possibility theory, Inform. Sci., 30, 183-224 (1983) · Zbl 0569.94031
[12] Blue, M.; Bush, B.; Puckett, J., Unified approach to fuzzy graph problems, Fuzzy Sets and Systems, 125, 355-368 (2002) · Zbl 1014.90077
[13] Okada, S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy Sets and Systems, 142, 3, 335-357 (2004) · Zbl 1045.90092
[14] Sengupta, A.; Pal, T. K., On comparing interval numbers, European J. Oper. Res., 127, 29-43 (2000) · Zbl 0991.90080
[15] Moreno, J. A.; Moreno, J. M.; Verdegay, J. L., Fuzzy location problems on networks, Fuzzy Sets and Systems, 142, 393-405 (2004) · Zbl 1045.90039
[16] Mahdavi, I.; Nourifar, R.; Heidarzade, A.; Mahdavi Amiri, N., A dynamic programming approach for finding shortest chains in a fuzzy network, Appl. Soft Comput., 9, 503-511 (2009)
[17] B. Sadeghpour Gildeh, D. Gien, La distance-Dp, q et le cofficient de corrélation entre deux variables aléatoires floues, Actes de LFA’2001, Monse, Belgium, 2001, pp. 97-102.; B. Sadeghpour Gildeh, D. Gien, La distance-Dp, q et le cofficient de corrélation entre deux variables aléatoires floues, Actes de LFA’2001, Monse, Belgium, 2001, pp. 97-102.
[18] Floyd, R. W., Algorithm 97, shortest path, Commun. ACM, 5, 345 (1962)
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.