Title: A distributed design of ripple-spreading algorithms for path optimisation problems

Authors: Tian-Qi Wang; Gong-Peng Zhang; Xiao-Bing Hu; Hongji Yang

Addresses: CAUC-ENAC Joint Research Centre of Applied Mathematics for Air Traffic Management, Civil Aviation University of China, Tianjin, China; Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin, China ' Collaborative Innovation Centre of eTourism, Beijing Union University, Beijing, China ' CAUC-ENAC Joint Research Centre of Applied Mathematics for Air Traffic Management, Civil Aviation University of China, Tianjin, China; School of Engineering, University of Warwick, Coventry, England, UK ' School of Informatics, Leicester University, Leicester, England, UK

Abstract: As a relatively new nature-inspired algorithm, Ripple-Spreading Algorithm (RSA) exhibits some advantageous features when resolving various Path Optimisation Problems (POPs) against both traditional deterministic algorithms and evolutionary approaches, e.g., RSA is a multi-agent, bottom-up, simulation model full of flexibility for modifications (like many evolutionary approaches), and it can guarantee optimality (like many deterministic algorithms). Towards real applications to large-scale POPs, RSA still needs to improve its computational efficiency. We used it to take some measures in order to achieve a trade-off between computational efficiency and optimality. This paper, for the first time without sacrificing optimality, proposes a way to significantly improve the computational efficiency of RSA. This is done by taking advantage of the multi-agent nature of RSA, i.e., a multi-agent model is naturally friendly to distributed design and parallel computing. Therefore, this paper reports a distributed design of RSA for POPs. Preliminary experimental results clearly demonstrate the effectiveness and efficiency of the new design of RSA.

Keywords: ripple-spreading algorithm; distributed design; parallel computation; paths optimisation; computational efficiency.

DOI: 10.1504/IJCAT.2021.116014

International Journal of Computer Applications in Technology, 2021 Vol.65 No.3, pp.209 - 221

Received: 07 Sep 2020
Accepted: 27 Oct 2020
Published online: 06 Jul 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article