Solving the Multiagent Pathfinding Problem with Time-Expanded Networks

The Multiagent Pathfinding Problem involves determining optimal, collision-free routes for a fleet of multiple autonomous vehicles from current positions to prescribed (goal) positions within a transportation or logistics facility such as a port terminal or a warehouse. This paper describes an exact algorithm for the problem, in which a sequence of reduced Mixed Integer Programming problems is solved iteratively on suitably defined time-expanded networks until an optimal solution is found. Computational results show that our approach outperforms a state-of-the-art solution algorithm on various mediumand large-sized instances. Additionally, we provide several managerial insights.