# Multi-Agent Routing and Scheduling Through Coalition Formation

arXiv: https://arxiv.org/abs/2105.00451 · HTML: https://mlsanity.com/paper/2105.00451/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 31 references that are in the map.
- First posted on arXiv 2 May 2021.

## Builds on (most cited first, 1 of 1)

- [An Anytime Algorithm for Optimal Coalition Structure Generation](https://mlsanity.com/paper/1401.3466/) (2014)

## Built on by (most cited first, 1 of 1)

- [Large-scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints](https://mlsanity.com/paper/2106.00379/) (2021)

## Abstract (arXiv)

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.