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

doi:10.1016/j.ejor.2025.07.068

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

2025-08-12

0

PRE

AI

DOI：10.1016/j.ejor.2025.07.068

Original

Original request for help

Save

Abstract

En 中文

• Multi-agent pathfinding problem with time-spacing constraints is tackled. • Proposes a new integer program with fewer constraints and tighter LP bound. • Derives new facet-defining valid inequalities for a substructure of the problem. • Two decomposition-based exact algorithms for large-scale instances are devised. • The computational performance of proposed algorithms is investigated.

Keywords:

multi-agent pathfinding

time-spacing constraints

integer programming

valid inequalities

decomposition algorithms

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

Abstract

Journal

Organization