Task assignment strategies for capacitated agents engaged in lifelong pickup and delivery tasks

Date

2025-11-01

Author

Çilden, Evren
Polat, Faruk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

2387
views

0
downloads

Cite This

In this study, we tackled the task assignment problem in the capacity-enhanced version of Multi-Agent Pickup and Delivery (MAPD), a lifelong variant of the classical Multi-Agent Path Finding (MAPF) problem. Capacity-enhanced agents can carry multiple items, allowing them to operate several tasks simultaneously by visiting a sequence of pickup and delivery locations (i.e. waypoints) to fulfill their assignments. When determining the next task of the agent from the available options, a method encountered in the literature is to select the task with the nearest pickup location to the agent's current location. In this research, we suggest that improving task assignments of capacitated agents can significantly enhance the solution quality of multi-agent route plans in lifelong pickup and delivery scenarios. We propose novel task assignment strategies that incorporate waypoints as a factor in the task selection process. We devised three groups of task assignment methods based on Closeness Centrality, Hausdorff Distance, and Cost Estimation within the context of the complete Token Passing with Multiple Capacity (TPMC) algorithm. We evaluated the methods in small and large-scale automated warehouse simulations, assessing their effectiveness in terms of makespan against the contemporary task selection method and one another. As a result of our experiments, the Closeness Centrality class of heuristics failed to enhance solution quality in large majority of cases. The Average Hausdorff Distance heuristic achieved good outcomes in scenarios with higher capacity agents. The Cost-Based Estimation method demonstrated significant improvements across all scenarios.

URI

https://hdl.handle.net/11511/115949

Collections

Department of Computer Engineering, Article