Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms

Edward Lam (), Peter J. Stuckey () and Daniel Harabor ()
Additional contact information
Edward Lam: Department of Data Science and Artificial Intelligence, Monash University, Clayton, Victoria 3168, Australia
Peter J. Stuckey: Department of Data Science and Artificial Intelligence, Monash University, Clayton, Victoria 3168, Australia
Daniel Harabor: Department of Data Science and Artificial Intelligence, Monash University, Clayton, Victoria 3168, Australia

Transportation Science, 2025, vol. 59, issue 1, 104-124

Abstract: Given a set of agents and a set of pickup-delivery requests located on a two-dimensional grid map, the multi-agent pickup and delivery problem assigns the requests to the agents such that every agent moves from its start location to the locations of its assigned requests and finally, to its end location without colliding into other agents and that the sum of arrival times is minimized. This paper proposes two exact branch-and-cut-and-price algorithms for the problem. The first algorithm performs a three-level search. A high-level master problem selects an optimal sequence of requests and a path for every agent from a large collection. A mid-level sequencing problem and a low-level navigation problem are solved simultaneously to incrementally enlarge the collection of request sequences and paths. The second algorithm first solves the sequencing problem to find a set of request sequences and then solves the navigation problem to determine if paths compatible with the request sequences exist. Experimental results indicate that the integrated algorithm solves more instances with higher congestion, and the deferred algorithm solves more instances with lower congestion and could scale to 100 agents and 100 requests, significantly higher than a state-of-the-art suboptimal approach.

Keywords: multi-agent pickup and delivery; multi-agent path finding; automated guided vehicle; conflict-free routing; vehicle routing problem; column generation; combinatorial Benders cuts (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0268 (application/pdf)

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:inm:ortrsc:v:59:y:2025:i:1:p:104-124

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().