# Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers

arXiv: https://arxiv.org/abs/1912.00253 · HTML: https://mlsanity.com/paper/1912.00253/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2019.

## Built on by (most cited first, 13 of 13)

- [Multi-Robot Coordination and Layout Design for Automated Warehousing](https://mlsanity.com/paper/2305.06436/) (2023)
- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Guidance Graph Optimization for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2402.01446/) (2024)
- [Arbitrarily Scalable Environment Generators via Neural Cellular Automata](https://mlsanity.com/paper/2310.18622/) (2023)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution](https://mlsanity.com/paper/2403.18145/) (2024)
- [Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems](https://mlsanity.com/paper/2510.03472/) (2025)
- [A Competitive Analysis of Online Multi-Agent Path Finding](https://mlsanity.com/paper/2106.11454/) (2021)
- [Lifelong Scalable Multi-Agent Realistic Testbed and A Comprehensive Study on Design Choices in Lifelong AGV Fleet Management Systems](https://mlsanity.com/paper/2602.15721/) (2026)
- [Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2602.23468/) (2026)
- [Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation](https://mlsanity.com/paper/2203.10540/) (2022)
- [GRAND: Guidance, Rebalancing, and Assignment for Networked Dispatch in Multi-Agent Path Finding](https://mlsanity.com/paper/2512.03194/) (2025)
- [Stress-Relief Annealing: Polynomial-Time Simulation-Free Layout Optimization for Automated Warehouses](https://mlsanity.com/paper/2608.01024/) (2026)

## Abstract (arXiv)

In this paper, we study the one-shot and lifelong versions of the Target Assignment and Path Finding problem in automated sortation centers, where each agent needs to constantly assign itself a sorting station, move to its assigned station without colliding with obstacles or other agents, wait in the queue of that station to obtain a parcel for delivery, and then deliver the parcel to a sorting bin. The throughput of such centers is largely determined by the total idle time of all stations since their queues can frequently become empty. To address this problem, we first formalize and study the one-shot version that assigns stations to a set of agents and finds collision-free paths for the agents to their assigned stations. We present efficient algorithms for this task based on a novel min-cost max-flow formulation that minimizes the total idle time of all stations in a fixed time window. We then demonstrate how our algorithms for solving the one-shot problem can be applied to solving the lifelong problem as well. Experimentally, we believe to be the first researchers to consider real-world automated sortation centers using an industrial simulator with realistic data and a kinodynamic model of real robots. On this simulator, we showcase the benefits of our algorithms by demonstrating their efficiency and effectiveness for up to 350 agents.