DynoPath: A Dynamic Online Grid-Based Centralized Sorting Algorithm

High-throughput sorting facilities require significant investment in costly resources, including labor, space, and equipment. The rapid growth of e-commerce coupled with economic and technological advancements in recent decades has intensified the demand for sorting technologies with increased throughput and improved cost/performance ratio. In this paper, we investigate sorting systems that utilize grids of four-way conveyors, where items can move freely in up to four cardinal directions from each array cell to its neighbors. In such systems, items enter the grid at designated input cells, and they are routed in a sequence of steps to their target output cells and eventually, to their destination bins. The grid-based approach enables multiple items to move simultaneously, offering the potential for significantly higher throughput compared with traditional conveyor-based sorting systems. However, operating grid-based sorting systems requires solving complex, real-time, parallel decision-making challenges. A naive, myopic operational policy is susceptible to possible deadlocks, where items block each other from reaching their destinations. To address this, we propose a novel centralized online algorithm that ensures deadlock-free operation. The algorithm models item movements within the grid using a time-expanded graph. Upon an item’s arrival, its route and schedule are determined, and the graph is immediately updated to preclude conflicts with future items. Extensive experiments demonstrate that our centralized algorithm achieves higher throughput than previously proposed distributed algorithms. Moreover, it scales effectively, enabling real-time operation of large grids with thousands of cells, which makes it suitable for modern high-throughput sorting facilities.

Funding: This research was supported by the Israel Science Foundation [Grant 2236/21]. I. Estrugo was supported by a scholarship from the Shlomo Shmeltzer Institute for Smart Transportation at Tel-Aviv University.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0033.