New integer optimization models and decomposition-based algorithms for the multi-agent pathfinding problem with time-spacing constraints

The multi-agent pathfinding problem (MAPF) is the problem of finding conflict-free paths for agents moving on a graph. Recently, as MAPF applications have been growing, time-spacing constraints have been introduced to address more realistic scenarios. These constraints prohibit multiple agents from occupying the same vertex within a given time window, thereby addressing timing deviations and allowing bounded agent autonomy in executing planned movements. However, studies on MAPF with time-spacing constraints (MAPF-TS) are still in their early stages. This paper examines MAPF-TS through the lens of integer optimization. We prove that some behaviors of agents that may appear in a solution are unnecessary in terms of feasibility and optimality. It enables us to propose a new integer optimization model for the set of feasible solutions without these behaviors. The new model uses fewer constraints than the existing one while providing a tighter LP bound. We also propose new valid inequalities which are facet-defining for a major substructure of MAPF-TS. We devise two decomposition-based algorithms for MAPF-TS: a Lagrangian relaxation-based algorithm (LAG) and a branch-price-and-cut algorithm (BPC). A comprehensive computational experiments demonstrate that both algorithms effectively handle large-scale instances which are unsolvable by existing methods. In particular, BPC excels in computing lower bounds close to the optimal objective value, while LAG demonstrates strength in finding high-quality feasible solutions.