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 medium- and large-sized instances. Additionally, we provide several managerial insights.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete.

Funding: This work was partly supported by the Ministero dell’Università e della Ricerca (MUR) of Italy [Grant 12-I-13147-10] (Decreto Ministeriale n. 1062 del 10-08-2021 - PON Ricerca e Innovazione 14-20).

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0951) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0951). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.