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 (4WCs), 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 are transferred 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 to 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 (TEG). Upon an item's arrival, its route and schedule are determined, and the graph is immediately updated to preclude conflict 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, making it suitable for modern high-throughput sorting facilities.