Task group allocation for multi-load agent pickup and delivery problem

This paper focuses on the Multi-Load Agent Pickup and Delivery (MLAPD) problem, in which the multi-load agent set needs to complete a set of dynamically arriving tasks while minimizing the service time. Compared with the general Multi-Agent Pickup and Delivery problem, in which each agent only completes one task once time, multi-load agents in the MLAPD problem can carry multiple tasks simultaneously, which greatly improves work efficiency in practice. However, the different completion times of multiple tasks will affect each other, which makes it difficult to find reasonable schedules for multi-load agents. Existing works ignore such influence among different tasks. To address this issue, in this paper, we propose a Task Group Allocation (TGA) algorithm to assign suitable tasks to the multi-load agents while considering the influence between these tasks. Specifically, we first quantify the carpooling scores among multiple tasks by using the Get Carpooling Scores (GCS) algorithm. Then, we present a K-Capacity Hierarchical Clustering (KCHC) algorithm to divide the set of tasks into groups with guarantee, in which tasks in the same group have little influence on each other. Finally, we use the TGA algorithm to allocate task groups to suitable agents to minimize the service time. Experimental results show that the TGA algorithm outperforms the state-of-the-art task allocation algorithms in terms of service time and makespan.