出版社：University of Malaya * Faculty of Computer Science and Information Technology
摘要：Shortest path problem is one of the most fundamental and wellknown optimization problems in graph theory due to its various realworld applications. Fuzzy set can manage the uncertainty, associated with the information of a problem, where conventional mathematical models may fail to reveal satisfactory result. In most cases, shortest path problem in fuzzy graph, called fuzzy shortest path problem, uses type1 fuzzy set as arc length. The uncertainty associated with the linguistic description of information is not represented properly by type1 fuzzy set due to inexactness of human perception in the evaluation of membership degrees having crisp values. An interval type2 fuzzy set is able to tackle this type of uncertainty. In this paper, we have proposed an algorithmic approach based on genetic algorithm for finding shortest path from a source node to a destination node in a fuzzy graph with interval type2 fuzzy arc lengths. We have designed a new crossover operator which does not need mutation operation. The purpose of mutation operation has been taken care by the proposed crossover operation. We have compared our algorithm with two other existing genetic algorithms for the fuzzy shortest path problem, where superiority of the proposed algorithm is shown. To the best of our knowledge, no algorithm based on genetic algorithm exists in the literature for fuzzy shortest path problem with interval type2 fuzzy arc lengths. A numerical example is used to illustrate the effectiveness of the proposed approach.
