A Novel Approach for Finding a Shortest Path in a Mixed Fuzzy Network

Ali Tajdin, Iraj Mahdavi, Nezam Mahdavi-Amiri, Bahram Sadeghpour-Gildeh, Reza Hassanzadeh

.

DOI: 10.4236/wsn.2010.22020                

Abstract

We present a novel approach for computing a shortest path in a mixed fuzzy network, network having various fuzzy arc lengths. First, we develop a new technique for the addition of various fuzzy numbers in a path using -cuts. Then, we present a dynamic programming method for finding a shortest path in the network. For this, we apply a recently proposed distance function for comparison of fuzzy numbers. Four examples are worked out to illustrate the applicability of the proposed approach as compared to two other methods in the literature as well as demonstrate the novel feature offered by our algorithm to find a fuzzy shortest path in mixed fuzzy networks with various settings for the fuzzy arc lengths.

Keywords

Fuzzy Numbers, -Cut; Shortest Path, Dynamic Programming

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. E. Moore, “Method and application of interval analysis,” SIAM, Philadelphia, 1997. M. Delgado, J. L. Verdegay, and M. A. Vila, “A procedure for ranking fuzzy numbers using fuzzy relations,” Fuzzy Sets and Systems, Vol. 26, pp. 49–62, 1988.
[2]	M. Delgado, J. L. Verdegay, and M. A. Vila, “A procedure for ranking fuzzy numbers using fuzzy relations,” Fuzzy Sets and Systems, Vol. 26, pp. 49–62, 1988.
[3]	H. Ishibuchi and H. Tanaka, “Multi-objective programming in optimization of the interval objective function,” European Journal of Operational Research, Vol. 48, pp. 219–225, 1990.
[4]	J. K. Sengupta, “Optimal decision under uncertainty,” Springer, New York, 1981.
[5]	T. Shaocheng, “Interval number and fuzzy number linear programming,” Fuzzy Sets and Systems, Vol. 66, pp. 301–306. 1994.
[6]	A. Sengupta, T. K. Pal, “Theory and methodology on comparing interval numbers,” European Journal of Operational Research, Vol. 127, 28–43, 2000.
[7]	D. Dubois and H. Prade, “Ranking fuzy numbers in the setting of possibility theory,” Information Sciences, Vol. 30, pp. 183–224, 1983.
[8]	S. H. Chen, “Ranking fuzzy numbers with maximizing set and minimizing set,” Fuzzy Sets and Systems, Vol. 17, pp. 113–129, 1985.
[9]	G. Bortolan and R. Degani, “A review of some methods for ranking fuzzy subsets,” Fuzzy Sets and Systems, Vol. 15, pp. 1–19, 1985.
[10]	C.-H. Cheng, “A new approach for ranking fuzzy numbers by distance method,” Fuzzy Sets and Systems, Vol. 95, pp. 307–317, 1998.
[11]	M. Blue, B. Bush, and J. Puckett, “Unified approach to fuzzy graph problems,” Fuzzy Sets and Systems, Vol. 125, pp. 355–368, 2002.
[12]	L. T. Koczy, “Fuzzy graphs in the evaluation and optimization of networks,” Fuzzy Sets and Systems, Vol. 46, pp. 307–319, 1992.
[13]	C. M. Klein, “Fuzzy Shortest Paths,” Fuzzy Sets and Systems, Vol. 39, pp. 27–41, 1991.
[14]	Y. Li, M. Gen, and K. Ida, “Solving fuzzy shortest path problem by neural networks,” Computers Industrial Engineering, Vol. 31, pp. 861–865, 1996.
[15]	K. Lin and M. Chen, “The fuzzy shortest path problem and its most vital arcs,” Fuzzy Sets and Systems, Vol. 58, pp. 343–353, 1994.
[16]	S. Okada and M. Gen, “Order relation between intervals and its application to shortest path problem,” Computers & Industrial Engineering, Vol. 25, 147–150, 1993.
[17]	S. Okada and M. Gen, “Fuzzy shortest path problem,” Computers & Industrial Engineering, Vol. 27, pp. 465– 468, 1994.
[18]	S. Okada and T. Soper, “A shortest path problem on a network with fuzzy arc lengths,” Fuzzy Sets and Systems, Vol. 109, pp. 129–140, 2000.
[19]	L. A. Zadeh, “Fuzzy sets as a basis for a theory of possibility,” Fuzzy Sets and Systems, Vol. 1, pp. 3–28, 1978.
[20]	R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan, “Faster algorithms for the shortest path problem,” Technical Report CS-TR-154-88, Department of Computer Science, Princeton University, 1988.
[21]	A. Andersson, T. Hagerup, S. Nilsson, and R. Raman, “Sorting in linear time?” In Proceedings of 27th ACM Symposium on Theory of Computing, pp. 427–436, 1995.
[22]	A. V. Goldberg, “Scaling algorithms for the shortest paths problem,” In: Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 1993.
[23]	Y. Asano and H. Imai, “Practical efficiency of the linear-time algorithm for the single source shortest path problem,” Journal of the Operations Research Society of Japan, Vol. 43, pp. 431–447, 2000.
[24]	Y. Han, “Improved algorithm for all pairs shortest paths,” Information Processing Letters, Vol. 91, pp. 245–250, 2004.
[25]	S. Saunders, T. Takaoka, “Improved shortest path algorithms for nearly acyclic graphs,” Electronic Notes in Theoretical Computer Science, Vol. 42, pp. 1–17, 2001.
[26]	S. Chanas, “Fuzzy optimization in networks,” In: J. Kacprzyk, S. A. Orlovski (Eds.), Optimization Models Using Fuzzy Sets and Possibility Theory, D. Reidel, Dordrecht, pp. 303–327, 1987.
[27]	B. Sadeghpour-Gildeh, D. Gien, Q. La Distance-Dp, et al. “Cofficient de Corrélation entre deux Variables Aléatoires floues,” Actes de LFA’01, pp. 97–102, Monse- Belgium, 2001.
[28]	I. Mahdavi, R. Nourifar, A. Heidarzade, and N. Mahdavi- Amiri, “A dynamic programming approach for finding shortest chains in a fuzzy network,” Applied Soft Computing, Vol. 9, No. 2, pp. 503–511, 2009.
[29]	R. W. Floyd, Algorithm 97, Shortest path, CACM 5, pp. 345, 1962.
[30]	T.-N. Chuang, and J.-Y. Kung, The fuzzy shortest path length and the corresponding shortest path in a network, Computers & Operations Research, Vol. 32, 1409–1428, 2005.
[31]	M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithm,” J. ACM 34, Vol. 3, pp. 596–615, 1987.
[32]	F. Hernandes, M. T. Lamata, J. L. Verdegay, and A. Yamakami, “The shortest path problem on networks with fuzzy parameters,” Fuzzy Sets and Systems, Vol. 158, pp. 1561–1570, 2007.