Artículos de revistas
An Algorithm For The Shortest Path Problem On A Network With Fuzzy Parameters Applied To A Tourist Problem
Registro en:
9783540769729
Studies In Fuzziness And Soft Computing. , v. 224, n. , p. 307 - 320, 2008.
14349922
10.1007/978-3-540-76973-6_20
2-s2.0-37749030334
Autor
Hernandes F.
Lamata M.T.
Verdegay J.L.
Yamakami A.
Institución
Resumen
In problems of graphs involving uncertainties, the shortest path problem is one of the most studied topics as it has a wide range of applications in different areas (e.g. telecommunications, transportation, manufacturing, etc.) and therefore warrants special attention. However, due to its high computational complexity, previously published algorithms present peculiarities and problems that need to be addressed (e.g. they find costs without an existing path, they determine a fuzzy solution set but do not give any guidelines to help the decision-maker choose the best path, they can only be applied in graphs with fuzzy non-negative parameters, etc.). Therefore, in this chapter is presented an iterative algorithm with a generic order relation that solves the cited disadvantages. This algorithm is applied in a tourist problem. It has been implemented using certain order relations, where some can find a set of fuzzy path solutions while others find only the shortest path. © 2008 Springer-Verlag Berlin Heidelberg. 224
307 320 Dubois, D., Prade, H., Ranking fuzzy numbers in the setting of possibility theory (1983) Information Sciences, 30, pp. 183-224 Dubois, D., Prade, H., (1980) Fuzzy sets and systems: Theory and applications, , Academic Press, New York Takahashi, M.T., (2004) Contribuições ao estudo de grafos fuzzy: Teoria e aplicações, , in Portuguese, Thesis, State University of Campinas, Campinas, Brazil Klein, C.M., Fuzzy shortest paths (1991) Fuzzy Sets and Systems, 39, pp. 27-41 Okada, S., Gen, M., Order relation between intervals and its application to shortest path problem (1993) Proceedings of the 15th Annual Conference on Computers and Industrial Engineering, 25, pp. 147-150 Okada, S., Gen, M., Fuzzy shortest path problem (1994) Proceedings of the 16th Annual Conference on Computers and Industrial Engineering, 27, pp. 465-468 Okada, S., Soper, T., A shortest path problem on a network with fuzzy arc lengths (2000) Fuzzy Sets and Systems, 109, pp. 129-140 Blue, M., Bush, B., Puckett, J., Unified approach to fuzzy graph problems (2002) Fuzzy Sets and Systems, 125, pp. 355-368 Eppstein, D., Finding the k-shortest paths (1994) Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 154-165 Okada, S., Fuzzy shortest path problems incorporating interactivity among paths (2004) Fuzzy Sets and Systems, 142 (3), pp. 335-357 Nayeem, S.M.A., Pal, M., Shortest path problem on a network with imprecise edge weight (2005) Fuzzy Optimization and Decision Making, 4, pp. 293-312 Ahuja, R.K., Magnanti, T.L., Orlin, J.B., (1993) Network flows, , Prentice Hall, Englewood Cliffs Hernandes, F., Lamata, M.T., Verdegay, J.L., Yamakami, A., A generic algorithm for the shortest path problem on a network with fuzzy parameters (2006) Proceedings of the International Symposium on Fuzzy Rough Sets, , Santa Clara, Cuba Hernandes, F., Lamata, M.T., Verdegay, J.L., Yamakami, A., The shortest Path Problem on Networks with Fuzzy Parameters (2007) Fuzzy Sets and Systems, 158, pp. 1561-1570 Bellman, R.E., On a routing problem (1958) Quarterly Applied Mathematics, 16, pp. 87-90 Yager, R.R., Ranking fuzzy subsets over the unit interval (1978) Proceedings of the CDC, pp. 1435-1437 Yager, R.R., On choosing between fuzzy subsets (1980) Kybernetes, 9, pp. 151-154 Yager, R.R., A procedure for ordering fuzzy subsets of the unit interval (1981) Information Sciences, 24, pp. 143-161 García, M.S., Lamata, M.T., (2007) A modification of the index of Liou and Wang for ranking fuzzy numbers, , International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems Liou, T.-S., Wang, M.-J., Ranking fuzzy numbers with integral value (1992) Fuzzy Sets and Systems, 50, pp. 247-255 Gondran, M., Minoux, M., (1984) Graphs and algorithms, , John Wiley and Sons, New York