DynoPath: A Dynamic Online Grid-Based Centralized Sorting Algorithm

References

• Bauer A, Maier G, Reith-Braun M, Kruggel-Emden H, Pfaff F, Gruna R, Hanebeck U, Längle T (2022) Towards a feed material adaptive optical belt sorter: A simulation study utilizing a DEM-CFD approach. Powder Tech. 411:117917.Crossref, Google Scholar
• Boysen N, Fedtke S, Weidinger F (2018) Optimizing automated sorting in warehouses: The minimum order spread sequencing problem. Eur. J. Oper. Res. 270(1):386–400.Crossref, Google Scholar
• Boysen N, Schwerdfeger S, Ulmer MW (2023) Robotized sorting systems: Large-scale scheduling under real-time conditions with limited lookahead. Eur. J. Oper. Res. 310(2):582–596.Crossref, Google Scholar
• Boysen N, Briskorn D, Fedtke S, Schmickerath M (2019) Automated sortation conveyors: A survey from an operational research perspective. Eur. J. Oper. Res. 276(3):796–815.Crossref, Google Scholar
• Bozer YA, Hsieh YJ (2005) Throughput performance analysis and machine layout for discrete-space closed-loop conveyors. IIE Trans. 37(1):77–89.Crossref, Google Scholar
• Bozer YA, Quiroz MA, Sharp GP (1988) An evaluation of alternative control strategies and design issues for automated order accumulation and sortation systems. Material Flow 4(4):265–282.Google Scholar
• Briskorn D, Emde S, Boysen N (2017) Scheduling shipments in closed-loop sortation conveyors. J. Scheduling 20(1):25–42.Crossref, Google Scholar
• Bukchin Y, Raviv T (2022) A comprehensive toolbox for load retrieval in puzzle-based storage systems with simultaneous movements. Transportation Res. Part B Methodological 166:348–373.Crossref, Google Scholar
• Chen TL, Chen JC, Huang CF, Chang PC (2021) Solving the layout design problem by simulation-optimization approach—A case study on a sortation conveyor system. Simulation Model. Practice Theory 106:102192.Crossref, Google Scholar
• Chen Y, Xu X, Zou B, De Koster R, Gong Y (2025) Assigning parcel destinations to drop-off points in a congested robotic sorting system. Naval Res. Logist. 72(2):220–241.Crossref, Google Scholar
• Damani M, Luo Z, Wenzel E, Sartoretti G (2021) Primal2: Pathfinding via reinforcement and imitation multi-agent learning-lifelong. IEEE Robotics Automation Lett. 6(2):2666–2673.Crossref, Google Scholar
• Fang Y, De Koster M, Roy D, Yu Y (2025) Dynamic robot routing and destination assignment policies for robotic sorting systems. Transportation Sci. 59(3):603–627.Link, Google Scholar
• Fedtke S, Boysen N (2017) Layout planning of sortation conveyors in parcel distribution centers. Transportation Sci. 51(1):3–18.Link, Google Scholar
• Gallien J, Weber T (2010) To wave or not to wave? Order release policies for warehouses with an automated sorter. Manufacturing Service Oper. Management 12(4):642–662.Link, Google Scholar
• Gao J, Li Y, Li X, Yan K, Lin K, Wu X (2024) A review of graph-based multi-agent pathfinding solvers: From classical to beyond classical. Knowledge-Based Systems 283:111121.Crossref, Google Scholar
• Geinzer CM, Meszaros JP (1990) Modeling high volume conveyor sorting systems. 1990 Winter Simulation Conf. Proc. (IEEE, Piscataway, NJ), 714–719.Google Scholar
• Gue KR, Kim BS (2007) Puzzle-based storage systems. Naval Res. Logist. 54(5):556–567.Crossref, Google Scholar
• Gue KR, Furmans K, Seibold Z, Uludağ O (2014) GridStore: A puzzle-based storage system with decentralized control. IEEE Trans. Automation Sci. Engrg. 11(2):429–438.Crossref, Google Scholar
• Hao G (2020) GridHub: A grid-based, high-density material handling system. PhD thesis, University of Louisville, Louisville, KY.Google Scholar
• Huang Y, Shen Z (2023) Flow-based integrated assignment and path-finding for mobile robot sorting systems. Preprint, submitted March 7, https://arxiv.org/abs/2303.04070.Google Scholar
• Jarrah AI, Qi X, Bard JF (2016) The destination-loader-door assignment problem for automated package sorting centers. Transportation Sci. 50(4):1314–1336.Link, Google Scholar
• Johnson ME (1997) The impact of sorting strategies on automated sortation system performance. IIE Trans. 30(1):67–77.Crossref, Google Scholar
• Johnson ME, Meller RD (2002) Performance analysis of split-case sorting systems. Manufacturing Service Oper. Management 4(4):258–274.Link, Google Scholar
• Kim JB, Choi HB, Hwang GY, Kim K, Hong YG, Han YH (2020) Sortation control using multi-agent deep reinforcement learning in N-grid sortation system. Sensors 20(12):3401.Crossref, Google Scholar
• Li J, Tinka A, Kiesel S, Durham JW, Kumar TS, Koenig S (2021) Lifelong multi-agent path finding in large-scale warehouses. Proc. AAAI Conf. Artificial Intelligence (AAAI-21), vol. 35, no. 13 (AAAI Press, Palo Alto, CA), 11272–11281.Google Scholar
• Lienert T, Fottner J (2017) No more deadlocks-applying the time window routing method to shuttle systems. Proc. Eur. Council Model. Simulation (ECMS) (European Council for Modelling and Simulation, Regensburg, Germany), 169–175.Google Scholar
• Meller RD (1997) Optimal order-to-lane assignments in an order accumulation/sortation system. IIE Trans. 29(4):293–301.Crossref, Google Scholar
• Okumura K, Machida M, Défago X, Tamura Y (2022) Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence 310:103752.Crossref, Google Scholar
• Russell ML, Meller RD (2003) Cost and throughput modeling of manual and automated order fulfillment systems. IIE Trans. 35(7):589–603.Crossref, Google Scholar
• Sartoretti G, Kerr J, Shi Y, Wagner G, Kumar TS, Koenig S, Choset H (2019) Primal: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robotics Automation Lett. 4(3):2378–2385.Crossref, Google Scholar
• Seibold Z (2016) Logical Time for Decentralized Control of Material Handling Systems, vol. 89 (KIT Scientific Publishing, Karlsruhe, Germany).Google Scholar
• Sharon G, Stern R, Felner A, Sturtevant NR (2015) Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219:40–66.Crossref, Google Scholar
• Standley T (2010) Finding optimal solutions to cooperative pathfinding problems. Fox D, Gomes CP, eds. Proc. AAAI Conf. Artificial Intelligence, vol. 24, no. 1 (AAAI Press, Palo Alto, CA), 173–178.Google Scholar
• Stern R, Sturtevant N, Felner A, Koenig S, Ma H, Walker T, Li J, et al. (2019) Multi-agent pathfinding: Definitions, variants, and benchmarks. Proc. Internat. Sympos. Combin. Search (SoCS), vol. 10, no. 1 (AAAI Press, Palo Alto, CA), 151–158.Google Scholar
• Švancara J, Vlk M, Stern R, Atzmon D, Barták R (2019) Online multi-agent pathfinding. Proc. AAAI Conf. Artificial Intelligence (AAAI-19), vol. 33, no. 1 (AAAI Press, Palo Alto, CA), 7732–7739.Google Scholar
• ter Mors AW (2010) The world according to MARP. Dissertation, Technische Universiteit Delft, Delft, Netherlands.Google Scholar
• Wang K-HC, Botea A (2008) Fast and memory-efficient multi-agent pathfinding. Proc. Internat. Conf. Automated Planning Scheduling (ICAPS-08), vol. 8 (AAAI Press, Palo Alto, CA), 380–387.Google Scholar
• Wang Y, Zhou C (2010) A model and an analytical method for conveyor systems in distribution centers. J. Systems Sci. Systems Engrg. 19(4):408–429.Crossref, Google Scholar
• Xu X, Chen Y, Zou B, Gong Y (2022) Assignment of parcels to loading stations in robotic sorting systems. Transportation Res. Part E Logist. Transportation Rev. 164:102808.Crossref, Google Scholar
• Zang H, Zhang Y, Jiang H, Chen Z, Harabor D, Stuckey PJ, Li J (2025) Online guidance graph optimization for lifelong multi-agent path finding. Proc. AAAI Conf. Artificial Intelligence (AAAI-25), vol. 39, no. 14 (AAAI Press, Palo Alto, CA), 14726–14735.Google Scholar
• Zou B, De Koster R, Gong Y, Xu X, Shen G (2021) Robotic sorting systems: Performance estimation and operating policies analysis. Transportation Sci. 55(6):1430–1455.Link, Google Scholar