Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms
Transportation Science · 10.12.2024
DOI: 10.1287/trsc.2023.0268 ↗Kurz gefasst
Fachartikel in der Zeitschrift Transportation Science, online erschienen am 10.12.2024. Verfasst von Edward Lam und 2 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 24 Literaturangaben.
Abstract (Originalsprache)
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. Funding: This research was supported by the Australian Research Council [Discovery Early Career Researcher Award DE240100042 and Discovery Projects DP190100013 and DP200100025] and by Amazon. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0268 .
Zitieren
APA
Lam, E., Stuckey, P. J., & Harabor, D. (2024). Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms. Transportation Science. https://doi.org/10.1287/trsc.2023.0268
Vancouver
Lam E, Stuckey PJ, Harabor D. Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms. Transportation Science. 2024. doi:10.1287/trsc.2023.0268
BibTeX
@article{Lam2024,
author = {Lam, Edward and Stuckey, Peter J. and Harabor, Daniel},
title = {Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price Algorithms},
journal = {Transportation Science},
year = {2024},
doi = {10.1287/trsc.2023.0268}
}
EUVIMED