A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights

Abstract

The shortest path (SP) problem constitutes one of the most prominent topics in graph theory and has practical applications in many research areas such as transportation, network communications, emergency services, and fire stations services, to name just a few. In most real-world applications, the arc weights of the corresponding SP problems are represented by fuzzy numbers. The current paper presents a fuzzy-based Ant Colony Optimization (ACO) algorithm for solving shortest path problems with different types of fuzzy weights. The weights of the fuzzy paths involving different kinds of fuzzy arcs are approximated using the α-cut method. In addition, a signed distance function is used to compare the fuzzy weights of paths. The proposed algorithm is implemented on three increasingly complex numerical examples and the results obtained compared with those derived from a genetic algorithm (GA), a particle swarm optimization (PSO) algorithm and an artificial bee colony (ABC) algorithm. The results confirm that the fuzzy-based enhanced ACO algorithm could converge in about 50% less time than the alternative metaheuristic algorithms.

Keywords

• Fuzzy shortest path problem
• Ant colony optimization
• Fuzzy numbers
• Fuzzy directed graph