A Fuzzy Variable H Strategy Based Ripple-Spreading Algorithm to Find the <i>k</i> 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 <i>k</i> shortest paths problem (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>−</mo><mi>SPP</mi></mrow></semantics></math></inline-formula>). Initially, each node may generate <i>k</i> 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 <i>h</i> ripples (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>h</mi><mo><</mo><mi>k</mi></mrow></semantics></math></inline-formula>). While this reduces optimality, it significantly improves efficiency. Further, we introduce a fuzzy variable <i>H</i> 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 <i>h</i>, 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>−</mo><mi>SPP</mi></mrow></semantics></math></inline-formula>.