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

Abstract

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≤hk). 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.

Keywords

• <i>k</i> shortest paths problem
• ripple-spreading
• optimality
• computational efficiency
• fuzzy variable strategy <i>H_T</i>