The fuzzy shortest path problem and its most vital arcs.

*(English)*Zbl 0804.90138Summary: The shortest path problem is to find the shortest distance between two specified nodes in a network. An arc is called a single most vital arc in the network, if its removal from the network results in the greatest increase in the shortest distance. The availability of arcs plays a key role in network problems. The most vital arcs problems provide a means by which the importance of arc’s availability can be measured. In the traditional shortest path problem, the arc lengths are assumed to be crisp numbers. In this paper, we consider the case that the arc lengths are fuzzy numbers. In particular, we derive the membership function of the shortest distance by using a fuzzy linear programming approach. Based on this result, we then propose an algorithm for finding the single most vital arc in a network.

##### MSC:

90C70 | Fuzzy and other nonstochastic uncertainty mathematical programming |

90C35 | Programming involving graphs or networks |

PDF
BibTeX
XML
Cite

\textit{K.-C. Lin} and \textit{M.-S. Chern}, Fuzzy Sets Syst. 58, No. 3, 343--353 (1993; Zbl 0804.90138)

Full Text:
DOI

##### References:

[1] | Ball, M.O; Golden, B.L; Vohra, R.V, Finding the most vital arcs in a network, Operations research letters, 8, 73-76, (1989) · Zbl 0679.90086 |

[2] | Bazaraa, M.S; Jarvis, J.J; Sherali, H.D, Linear programming and network flows, (1990), John Wiley & Sons New York · Zbl 0722.90042 |

[3] | Bortolan, G; Degani, R, A review of some methods for ranking fuzzy subsets, Fuzzy sets and systems, 15, 1-19, (1985) · Zbl 0567.90056 |

[4] | Chanas, S, Fuzzy optimization in networks, (), 303-327 |

[5] | Chanas, S; Kamburowski, J, The fuzzy shortest route problem, (), 35-41 |

[6] | Chanas, S; Kolodziejczyk, W, Maximum flow in a network with fuzzy arc capacities, Fuzzy sets and systems, 8, 165-173, (1982) · Zbl 0489.90040 |

[7] | Chanas, S; Kolodziejczyk, W, Real-valued flows in a network with fuzzy arc capacities, Fuzzy sets and systems, 13, 139-151, (1984) · Zbl 0549.90039 |

[8] | Chanas, S; Kolodziejczyk, W; Machaj, A, A fuzzy approach to the transportation problem, Fuzzy sets and systems, 13, 211-221, (1984) · Zbl 0549.90065 |

[9] | Chanas, S; Kolodziejczyk, W; Machaj, A, The MIN-cost flow problem - a fuzzy approach, (), 53-61 |

[10] | Corley, H.W; Sha, D.Y, Most vital links and nodes in weighted networks, Operations research letters, 1, 157-160, (1982) · Zbl 0488.90069 |

[11] | Delgado, M; Verdegay, J.L; Vila, M.A, Fuzzy transportation problems: a general analysis, (), 342-358 · Zbl 0636.90059 |

[12] | Dijkstra, E.W, A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269-271, (1959) · Zbl 0092.16002 |

[13] | Dubois, D; Prade, H, Algorithmes de plus courts chemins pour traiter des donnees floues, RAIRO oper. res., 12, 213-227, (1978) · Zbl 0379.90046 |

[14] | Dubois, D; Prade, H, Fuzzy sets and systems: theory and applications, (1980), Academic Press New York · Zbl 0444.94049 |

[15] | Goldfarb, D; Hao, J; Kai, S.-R, Efficient shortest path simplex algorithms, Operations research, 38, 624-628, (1990) · Zbl 0723.90083 |

[16] | K.-C. Lin and M.-S. Chern, The single most vital arc in the most economical path problem - a parametric analysis, to appear in Computers and Operations Research. · Zbl 0789.90085 |

[17] | Liou, T.S; Wang, M.-J, Ranking fuzzy numbers with integral value, Fuzzy sets and systems, 50, 247-255, (1992) · Zbl 1229.03043 |

[18] | Malik, K; Mittal, A.K; Gupta, S.K, The k most vital arcs in the shortest path problem, Operations research letters, 8, 223-227, (1989) · Zbl 0669.90090 |

[19] | Mares, M; Horak, J, Fuzzy quantities in network, Fuzzy sets and systems, 10, 123-134, (1983) · Zbl 0518.90031 |

[20] | Verdegay, J.L, A dual approach to solve the fuzzy linear programming problem, Fuzzy sets and systems, 14, 131-141, (1984) · Zbl 0549.90064 |

[21] | Zimmermann, H.-J, Fuzzy set theory and its applications, (1991), Kluwer Academic Publishers Boston · Zbl 0719.04002 |

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.