TY - JOUR
T1 - A Local-Search-Based Heuristic for Coalition Formation in Urgent Missions
AU - Guo, Miao
AU - Xin, Bin
AU - Wang, Yipeng
AU - Chen, Jie
N1 - Publisher Copyright:
© 2024 IEEE.
PY - 2024
Y1 - 2024
N2 - This article focuses on the coalition formation (CF) problem in urgent missions, e.g., disaster rescue, where coalition members should reach mission locations quickly. A mathematical model is first constructed to minimize the latest arrival time of coalition members, considering the capability requirements of missions, nonredundant agents in coalitions, etc. Then, incorporating the benefits in both the diversity of random search and the effectiveness of utilizing problem knowledge, a local-search-based heuristic is put forward to solve the CF problem. An initial solution is incrementally constructed by prioritizing agents with shorter movement times for missions with higher-remaining capability requirements. Additionally, two types of neighborhood search operators, namely, the tabu-based one-to-one swap and the destroy and repair operators, are proposed to search the solution space from two perspectives, i.e., 'adjustment' and 'reconstruction.' To solve the problem effectively and efficiently, the former excludes certain agent-exchange combinations that do not improve the current solution, while the latter consists of multiple heuristic rules extracted from the correlation among different model elements. Experimental results have demonstrated that the proposed method surpasses several advanced methods across various scenarios regarding multiple factors, such as the number of agents, the number of missions, and the demand-supply ratio on capabilities.
AB - This article focuses on the coalition formation (CF) problem in urgent missions, e.g., disaster rescue, where coalition members should reach mission locations quickly. A mathematical model is first constructed to minimize the latest arrival time of coalition members, considering the capability requirements of missions, nonredundant agents in coalitions, etc. Then, incorporating the benefits in both the diversity of random search and the effectiveness of utilizing problem knowledge, a local-search-based heuristic is put forward to solve the CF problem. An initial solution is incrementally constructed by prioritizing agents with shorter movement times for missions with higher-remaining capability requirements. Additionally, two types of neighborhood search operators, namely, the tabu-based one-to-one swap and the destroy and repair operators, are proposed to search the solution space from two perspectives, i.e., 'adjustment' and 'reconstruction.' To solve the problem effectively and efficiently, the former excludes certain agent-exchange combinations that do not improve the current solution, while the latter consists of multiple heuristic rules extracted from the correlation among different model elements. Experimental results have demonstrated that the proposed method surpasses several advanced methods across various scenarios regarding multiple factors, such as the number of agents, the number of missions, and the demand-supply ratio on capabilities.
KW - Coalition formation (CF)
KW - heuristic
KW - local search
KW - mission requirements
UR - http://www.scopus.com/inward/record.url?scp=85207040649&partnerID=8YFLogxK
U2 - 10.1109/TSMC.2024.3443860
DO - 10.1109/TSMC.2024.3443860
M3 - Article
AN - SCOPUS:85207040649
SN - 2168-2216
VL - 54
SP - 6924
EP - 6935
JO - IEEE Transactions on Systems, Man, and Cybernetics: Systems
JF - IEEE Transactions on Systems, Man, and Cybernetics: Systems
IS - 11
ER -