Solving fuzzy shortest path problem by genetic algorithm

Indonesian Operations Research Association - International Conference on Operations Research 2017

Syarif, A.^1 ; Muludi, K.^1 ; Adrian, R.^1 ; Gen, M.^2

Department of Computer Science, Faculty of Mathematics, Natural Sciences Lampung University, Jl. Brodjonegoro No. 1, Bandar Lampung

35145, Indonesia^1

Fuzzy Logic Institute, Tokyo, Japan^2

关键词: Decision makers;    Fuzzy approach;    Fuzzy shortest path problems;    Mathematical optimizations;    Network design problems;    Ranking fuzzy numbers;    Shortest path problem;    Triangular fuzzy numbers;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/332/1/012003/pdf
DOI  :  10.1088/1757-899X/332/1/012003

来源: IOP

【 摘 要 】

Shortest Path Problem (SPP) is known as one of well-studied fields in the area Operations Research and Mathematical Optimization. It has been applied for many engineering and management designs. The objective is usually to determine path(s) in the network with minimum total cost or traveling time. In the past, the cost value for each arc was usually assigned or estimated as a deteministic value. For some specific real world applications, however, it is often difficult to determine the cost value properly. One way of handling such uncertainty in decision making is by introducing fuzzy approach. With this situation, it will become difficult to solve the problem optimally. This paper presents the investigations on the application of Genetic Algorithm (GA) to a new SPP model in which the cost values are represented as Triangular Fuzzy Number (TFN). We adopts the concept of ranking fuzzy numbers to determine how good the solutions. Here, by giving his/her degree value, the decision maker can determine the range of objective value. This would be very valuable for decision support system in the real world applications.Simulation experiments were carried out by modifying several test problems with 10-25 nodes. It is noted that the proposed approach is capable attaining a good solution with different degree of optimism for the tested problems.