An Algorithm for the Shortest Path Problem on a Network with Fuzzy Parameters Applied to a Tourist Problem
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 spec
- PDF / 214,636 Bytes
- 14 Pages / 430 x 660 pts Page_size
- 41 Downloads / 220 Views
2
3
Dpto. de Ciˆencia da Computa¸ca ˜o, Universidade Estadual do Centro-Oeste C.P. 3010, 85015-430, Guarapuava-PR, Brazil [email protected] Dpto. de Ciencias de la Computaci´ on e I. A., E.T.S. de Ingenier´ıa Inform´ atica, Universidad de Granada E-18071, Granada, Spain {mtl,verdegay}@decsai.ugr.es Dpto. de Telem´ atica, Faculdade de Engenharia El´etrica e de Computa¸ca ˜o Universidade Estadual de Campinas C.P. 6101, 13083-970, Campinas-SP, Brazil [email protected]
Summary. 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.
1 Introduction The problem of finding the shortest path from a specified source node to the other nodes is a fundamental matter that appears in many applications, for example: transportation, routing, communications and recently in supply chain management. Let G = (V, E) be a graph, where V is the set of vertices and E is the set of edges. A path between two nodes is an alternating sequence of vertices and edges starting and ending with the vertices. The length (cost) of a path is the sum of the weights of the edges on the path. However, since there can be more than one path between two vertices, there is then the problem of finding a path with the minimum cost between these two specified vertices. In classical graph theory, the weight of each edge is a crisp number. However, most applications for this R. Bello et al. (Eds.): Granular Computing, STUDFUZZ 224, pp. 307–320, 2008. c Springer-Verlag Berlin Heidelberg 2008 springerlink.com
308
F. Hernandes et al.
problem have parameters that are not naturally precise, i.e. costs, capacities, demands, etc, and in such cases, fuzzy numbers based on fuzzy set theory (see [1]) can be applied. This problem is called fuzzy shortest path problem. In the fuzzy shortest path problem, the final costs (time) are fuzzy numbers, which is difficult to find a smaller path than all the other existing paths. It is therefore often hard to find a fuzzy cost, which is strictly smaller than the other costs. In this chapter we will apply the fuzzy shortest path problem in a tourist problem, where the uncertainties are in the time (parameters of the arcs
Data Loading...
