Multi-Agent Routing and Scheduling Through Coalition Formation
This addresses efficient task allocation for emergency responders, such as firefighters, by providing a scalable heuristic and benchmark, though it is incremental as it builds on existing optimization problems.
The paper tackles the problem of multi-agent routing and scheduling with coalition formation to maximize profits and minimize time penalties in real-time domains like disaster response, achieving solutions up to 3.25 times better than the Earliest Deadline First approach in scenarios with up to 150 agents and 3000 tasks.
In task allocation for real-time domains, such as disaster response, a limited number of agents is deployed across a large area to carry out numerous tasks, each with its prerequisites, profit, time window and workload. To maximize profits while minimizing time penalties, agents need to cooperate by forming, disbanding and reforming coalitions. In this paper, we name this problem Multi-Agent Routing and Scheduling through Coalition formation (MARSC) and show that it generalizes the important Team Orienteering Problem with Time Windows. We propose a binary integer program and an anytime and scalable heuristic to solve it. Using public London Fire Brigade records, we create a dataset with 347588 tasks and a test framework that simulates the mobilization of firefighters. In problems with up to 150 agents and 3000 tasks, our heuristic finds solutions up to 3.25 times better than the Earliest Deadline First approach commonly used in real-time systems. Our results constitute the first large-scale benchmark for the MARSC problem.