Dindar ÖzTolga Bugra Altuntas2025-10-0620241553166X, 154758161547-58161553-166X10.3934/jimo.2023119https://www.scopus.com/inward/record.uri?eid=2-s2.0-85184667499&doi=10.3934%2Fjimo.2023119&partnerID=40&md5=baae97f53e7b3b1067a7cbc7dbfe412fhttps://gcris.yasar.edu.tr/handle/123456789/8232The coalition formation problem (CFP) is a crucial component of multi-agent systems (MAS) taking place in various areas in the real world with different variants. This study proposes a parallel metaheuristic algorithm for CFP. Our hybrid method combines two metaheuristic algorithms: the Scatter Search and the Beam Search. While the former ensures that the algorithm thoroughly explores the search space the latter exploits the visited regions. We redesign Scatter Search’s original implementation to perform the time-consuming independent areas of the task in parallel. We employ a perturbation mechanism inside the Beam Search that performs a big jump in the search space when it cannot find any improvement. Moreover we design a problem-specific representation that stores meta-information to save significant computational time. The proposed method is examined in parallel and sequential configurations and compared with an exact solver recent metaheuristic algorithms and the standard implementation of the Scatter Search. The experimental results show that our solution achieves considerable improvements in both configurations. © 2024 Elsevier B.V. All rights reserved.EnglishBeam Search, Coalition Formation Problem, Multi-agent Systems, Parallel Algorithms, Scatter Search, Stochastic Systems, Beam Search, Coalition Formation Problem, Coalition Formations, Hybrid Method, Meta-heuristics Algorithms, Parallel Metaheuristics, Real-world, Scatter Search, Search Spaces, Stochastics, Multi Agent SystemsStochastic systems, Beam search, Coalition formation problem, Coalition formations, Hybrid method, Meta-heuristics algorithms, Parallel metaheuristics, Real-world, Scatter search, Search spaces, Stochastics, Multi agent systemsArticle