Research ArticleOpen AccessGoogle Scholar indexed
A Novel Approach for Finding a Shortest Path in a Mixed Fuzzy Network
- 1
- 2
- 3
- 4
- 5
Wireless Sensor Network·Volume 02 (2010)·Pages 148–160·Published 1 March 2010·DOI10.4236/wsn.2010.22020
Copy link · social · email
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.
KeywordsFuzzy Numbers-CutShortest PathDynamic Programming
- 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.
- 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.
- 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.
- J. K. Sengupta, “Optimal decision under uncertainty,” Springer, New York, 1981.
- T. Shaocheng, “Interval number and fuzzy number linear programming,” Fuzzy Sets and Systems, Vol. 66, pp. 301–306. 1994.
- A. Sengupta, T. K. Pal, “Theory and methodology on comparing interval numbers,” European Journal of Operational Research, Vol. 127, 28–43, 2000.
- D. Dubois and H. Prade, “Ranking fuzy numbers in the setting of possibility theory,” Information Sciences, Vol. 30, pp. 183–224, 1983.
- S. H. Chen, “Ranking fuzzy numbers with maximizing set and minimizing set,” Fuzzy Sets and Systems, Vol. 17, pp. 113–129, 1985.
- G. Bortolan and R. Degani, “A review of some methods for ranking fuzzy subsets,” Fuzzy Sets and Systems, Vol. 15, pp. 1–19, 1985.
- C.-H. Cheng, “A new approach for ranking fuzzy numbers by distance method,” Fuzzy Sets and Systems, Vol. 95, pp. 307–317, 1998.
- M. Blue, B. Bush, and J. Puckett, “Unified approach to fuzzy graph problems,” Fuzzy Sets and Systems, Vol. 125, pp. 355–368, 2002.
- L. T. Koczy, “Fuzzy graphs in the evaluation and optimization of networks,” Fuzzy Sets and Systems, Vol. 46, pp. 307–319, 1992.
- C. M. Klein, “Fuzzy Shortest Paths,” Fuzzy Sets and Systems, Vol. 39, pp. 27–41, 1991.
- Y. Li, M. Gen, and K. Ida, “Solving fuzzy shortest path problem by neural networks,” Computers Industrial Engineering, Vol. 31, pp. 861–865, 1996.
- 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.
- S. Okada and M. Gen, “Order relation between intervals and its application to shortest path problem,” Computers & Industrial Engineering, Vol. 25, 147–150, 1993.