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

Seyoung Oh and Kyungsik Lee

European Journal of Operational Research, 2026, vol. 329, issue 2, 378-390

Abstract: 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.

Keywords: Routing; Multi-agent pathfinding; Time-spacing constraints; Integer optimization; Decomposition-based algorithm (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725005934
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:329:y:2026:i:2:p:378-390

DOI: 10.1016/j.ejor.2025.07.068

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().