Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/72447
Type: Artigo de periódico
Title: The shortest path problem on networks with fuzzy parameters
Author: Hernandes, F
Lamata, MT
Verdegay, JL
Yamakami, A
Abstract: Shortest path problem where the costs have vague values is one of the most studied problems in fuzzy sets and systems area. 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.). In this paper, one proposes an iterative algorithm that assumes a generic ranking index for comparing the fuzzy numbers involved in the problem, in such a way that each time in which the decision-maker wants to solve a concrete problem (s)he can choose (or propose) the ranking index that best suits that problem. This algorithm, that solves the above remarked drawbacks, is based on the Ford-Moore-Bellman algorithm for classical graphs, and in concrete it can be applied in graphs with negative parameters and it can detect whether there are negative circuits. For the sake of illustrating the performance of the algorithm in the paper, it has been here developed using only certain order relations, but it is not restricted at all to use these comparison relations exclusively. The proposed algorithm is easy of understanding as the theoretical base of a decision support system oriented to solving this kind of problems. (c) 2007 Elsevier B.V. All rights reserved.
Subject: shortest path problems
Ford-Moore-Bellman algorithm
fuzzy mathematical programming
fuzzy numbers
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/j.fss.2007.02.022
Date Issue: 2007
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000247410100004.pdf182.03 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.