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

Abstract

Shortest path problems in graph theory are applicable in areas like emergency services, mapping software, and computer networks. Fuzzy arc weights introduce uncertainty, typically managed with α-cuts and least squares methods. This research introduces a novel Hybrid Ant Colony Optimization algorithm that incorporates genetic algorithm mutation behaviors, governed by a no-repetition criterion akin to a Tabu list. This differentiates it from other methods by integrating controlled mutations and a Tabu List, which prevents infinite loops and ensures effective diversification among ants. This strategy allows for thorough exploration of the solution space, achieving optimal results for complex graph-based fuzzy arc weighted shortest path problems. The algorithm's blend of exploration and exploitation shows significant promise, with performance tested against other metaheuristics like Ant Colony Optimization, Artificial Bee Colony, Genetic Algorithm, and Particle Swarm Optimization on three challenging graph examples. The new algorithm proves highly effective, converging about 49 % faster than its competitors, making it a superior choice for practical applications that involve fuzzy arc weights.

Keywords

• Ant colony optimization
• Hybrid ant colony optimization
• Shortest path problems
• Fuzzy arc weights
• Fuzzy numbers
• Metaheuristic algorithms