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.
Solving the multiagent pathfinding problem with time-expanded networks.
Tommaso Adamo;Gianpaolo Ghiani;Emanuela Guerriero
2025-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
