  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.
