A Dynamic Programming Approach forFinding Shortest Chains in a Fuzzy Network

Graph theory has numerous applications to problems in systems analysis, operations research, transportation, and economics. In many cases, however, some aspects of a graph-theoretic problem may be uncertain. For example, the vehicle travel time or vehicle capacity on a road network may not be known exactly. In such cases, it is natural to make use of the fuzzy set theory to deal with the uncertainty. Here, we are concerned with finding shortest chains in a graph with fuzzy distance for every edge. We propose a dynamic programming approach to solve the fuzzy shortest chain problem using a suitable ranking method. Two illustrative examples are worked out to demonstrate the proposed algorithm. The shortest path problems are popular problems in graph theory with many practical applications; e.g., in transportation, routing, and communication. They include such problems as finding the shortest path between two given vertices of a graph, finding the shortest paths from a given vertex to all other vertices, and finding the shortest paths between all pairs of vertices. While geographical distances can be stated deterministically, costs or times can fluctuate with traffic conditions, payload, and so on. In the last two cases, deterministic values for representing the edge weights cannot be used. A typical approach for considering these uncertainties in the edge weights is to utilize fuzzy numbers. Numerous papers have been published for solving fuzzy graph problems [10,12,16,18,24]. The fuzzy shortest path problem was first analyzed by Dubois and Prade [7]. They used Floyd's algorithm and Ford's algorithm [9, 11] to treat these problems. While the shortest path length can be obtained by their approach, but the corresponding path in the network may not exist. Klein [15] proposed a dynamic programming recursion-based fuzzy algorithm. But, this algorithm may result in a dominated solution that is not acceptable as a shortest path. Lin and Chen [17] found the fuzzy shortest path length in a network by means of a fuzzy linear programming approach. Another algorithm for this problem was presented by Okada and Gen [22, 23] as a generalization of Djikstra’s algorithm. In this algorithm, the weights of the arcs are considered to be interval numbers and are defined using a partial order between interval numbers. Okada and Soper [21] proposed a fuzzy algorithm, based on multiple labeling methods to offer non-dominated paths to a decision maker. Blue et al. [2] presented an algorithm finding a cut value to limit the number of analyzed paths, and then applied a modified version of the k-shortest path (crisp) algorithm proposed by Eppstein [8]. Okada [20] introduced the concept of the degree of possibility of an arc being on the shortest path. Among the most recent work is the paper by Nayeem and Pal [19] that proposes an algorithm based on the acceptance index introduced by Sengupta and Pal [24] and gives a single fuzzy shortest path or a guideline for choosing the best fuzzy shortest path according to the decision-maker’s viewpoint. Chuang and Kung [5] proposed a fuzzy shortest path length procedure to find a fuzzy shortest path length among all possible paths in a network. It is based on the idea that a crisp number is minimal if and only if any other number is larger than or equal to it. It is apparent that these articles present peculiarities and/or problems that warrant attention. Among the most important, for example, are the following three: They find arc lengths without an existing path; they can determine a fuzzy solution set but do not provide decision-makers with any guidelines for choosing the best path [10]; they find the shortest path between source node and any other node. Here, we propose an iterative algorithm for fuzzy all-pairs shortest paths problem (FAPSPP). The algorithm is based on dynamic programming. Since the fuzzy min operator based on the extension principle leads to non-dominated solutions, we propose another approach to solving the FAPSPP using a suitable ranking method. A comprehensive numerical example is worked out in the Matlab software environment to show the applicability of the proposed model in an uncertain environment.