×

zbMATH — the first resource for mathematics

New models for shortest path problem with fuzzy arc lengths. (English) Zbl 1152.90674
Summary: This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, \(\alpha \)-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some examples are given to illustrate its effectiveness.

MSC:
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bellman, E., On a routing problem, Quart. appl. math., 16, 87-90, (1958) · Zbl 0081.14403
[2] Dijkstra, E.W., A note on two problems in connection with graphs, Numer. math., 1, 269-271, (1959) · Zbl 0092.16002
[3] Dreyfus, S., An appraisal of some shortest path algorithms, Oper. res., 17, 395-412, (1969) · Zbl 0172.44202
[4] Frank, H., Shortest paths in probability graphs, Oper. res., 17, 583-599, (1969) · Zbl 0176.48301
[5] Fu, L.; Rilett, L.R., Expected shortest paths in dynamic and stochastic traffic networks, Transport. res., 32, 7, 499-516, (1998)
[6] Hall, R., The fastest path through a network with random time-dependent travel time, Transport. sci., 20, 3, 182-188, (1986)
[7] Loui, P., Optimal paths in graphs with stochastic or multidimensional weights, Comm. ACM, 26, 670-676, (1983) · Zbl 0526.90085
[8] Mirchandani, B.P., Shortest distance and reliability of probabilistic networks, Comput. oper. res., 3, 347-676, (1976)
[9] Murthy, I.; Sarkar, S., A relaxation-based pruning technique for a class of stochastic shortest path problems, Transport. sci., 30, 3, 220-236, (1996) · Zbl 0879.90093
[10] Dubois, D.; Prade, H., Fuzzy sets and systems: theory and applications, (1980), Academic Press New York · Zbl 0444.94049
[11] Klein, C.M., Fuzzy shortest paths, Fuzzy set. syst., 39, 27-41, (1991) · Zbl 0728.90090
[12] Yager, R., Paths of least resistance on possibilistic production systems, Fuzzy set. syst., 19, 121-132, (1986) · Zbl 0601.90018
[13] Lin, K.; Chen, M., The fuzzy shortest path problem and its most vital arcs, Fuzzy set. syst., 58, 343-353, (1994) · Zbl 0804.90138
[14] Okada, S.; Soper, T., A shortest path problem on a network with fuzzy arc lengths, Fuzzy set. syst., 109, 1, 129-140, (2000) · Zbl 0956.90070
[15] Okada, S., Fuzzy shortest path problems incorporating interactivity among paths, Fuzzy set. syst., 142, 3, 335-357, (2004) · Zbl 1045.90092
[16] Liu, B., Theory and practice of uncertain programming, (2002), Physica-Verlag Heidelberg · Zbl 1029.90084
[17] Liu, B., Uncertainty theory: an introduction to its axiomatic foundations, (2004), Springer-Verlag Berlin · Zbl 1072.28012
[18] Liu, B.; Liu, Y.K., Expected value of fuzzy variable and fuzzy expected value model, IEEE trans. fuzzy syst., 10, 445-450, (2002)
[19] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows, (1993), Prentice-Hall Englewood CliRs, NJ · Zbl 1201.90001
[20] Murty, K.G., Network programming, (1992), Prentice-Hall Englewood CliRs, NJ
[21] Liu, B., Toward fuzzy optimization without mathematical ambiguity, Fuzzy optim. decis. making, 1, 1, 43-63, (2002) · Zbl 1068.90618
[22] Liu, B., Minimax chance constrained programming models for fuzzy decision systems, Inform. sci., 112, 1-4, 25-38, (1998) · Zbl 0965.90058
[23] Liu, B.; Iwamura, K., Chance constrained programming with fuzzy parameters, Fuzzy set. syst., 94, 2, 227-237, (1998) · Zbl 0923.90141
[24] Liu, B.; Iwamura, K., A note on chance constrained programming with fuzzy coefficients, Fuzzy set. syst., 100, 1-3, 229-233, (1998) · Zbl 0948.90156
[25] Liu, B., Dependent-chance programming with fuzzy decisions, IEEE trans. fuzzy syst., 7, 3, 354-360, (1999)
[26] Liu, B., Dependent-chance programming in fuzzy environments, Fuzzy set. syst., 109, 1, 97-106, (2000) · Zbl 0955.90153
[27] Holland, J., Adaptatin in natural and artificial system, (1975), University of Michigan Press Ann Arbor, MI
[28] Gen, M.; Cheng, R., Genetic algorithms and engineer optimization, (2000), John Wiley and Sons, Inc. New York
[29] Cherkassky, B.V.; Goldberg, A.V.; Radzik, T., Shortest paths algorithms: theory and experimental evaluation, Math. prog., 73, 129-174, (1996) · Zbl 0853.90111
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.