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

Yingfei Zhang, Xiaobing Hu (), Hang Li, Gongpeng Zhang, Chi Zhang and Mark S. Leeson
Additional contact information
Yingfei Zhang: College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China
Xiaobing Hu: College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China
Hang Li: College of Safety Science and Engineering, Civil Aviation University of China, Tianjin 300300, China
Gongpeng Zhang: Collaborative Innovation Center of Etourism, Beijing Union University, Beijing 100101, China
Chi Zhang: Beijing College of Politics and Law, Beijing 102628, China
Mark S. Leeson: School of Engineering, University of Warwick, Coventry CV4 7AL, UK

Mathematics, 2024, vol. 12, issue 23, 1-26

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

Keywords: k shortest paths problem; ripple-spreading; optimality; computational efficiency; fuzzy variable strategy H T (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/23/3670/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/23/3670/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:23:p:3670-:d:1527728

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().