A Fuzzy Variable H Strategy Based Ripple-Spreading Algorithm to Find the k Shortest Paths

Ripple-spreading Algorithm (RSA) is a relatively new, nature-inspired, multi-agent based method for path optimization. This paper demonstrates that by modifying the micro-level behaviors of nodes and ripples, RSA achieves good scalability for solving the k shortest paths problem (k-SPP). Initially, each node may generate k or more ripples to guarantee optimality. To improve computational efficiency for large-scale problems, we propose an approximate RSA (ARSA), where nodes generate no more than h ripples (1 <= h<k). While this reduces optimality, it significantly improves efficiency. Further, we introduce a fuzzy variable H strategy, FVHSRSA, to strike a better balance between optimality and efficiency. The optimality/efficiency of ARSA may still suffer if it uses a constant h too small/large. This strategy allows nodes closer to the destination to generate more ripples, while nodes farther away use fewer ripples. By dynamically adjusting h, FVHSRSA achieves a better trade-off between optimality and efficiency. Comprehensive experiments on 4 common network categories validate the effectiveness and efficiency of FVHSRSA in solving the k-SPP.