隨倉儲空間成本增加，如何提升空間利用率並保持機動性成為重要課題。在推盤式高密度倉儲系統中，因大部分面積皆被承載貨物的推盤所佔據，推盤移動路徑有賴精準的空格位置調配，其移動過程常需先移動其它推盤才得以挪出空間以移動該推盤，宛如數字推盤遊戲一般，此與傳統自動倉儲系統常見的輸送帶或機器手臂的移動方式差異甚大，是一個多元商品網路流量問題。文獻中大多僅探討如何規劃單一推盤的移動路線，而忽略多推盤同時進行移動與是否碰撞等相關議題。
本研究考慮多個出貨推盤之揀貨路徑規劃問題，相較單一出貨推盤的移動，須避免為移動某出貨推盤卻因而導致其他出貨推盤更遠離其原先目的地，亦將「時間維度」納入考量，針對同時可移動的推盤數與碰撞限制等進行更細緻的設定。允許推盤含有多商品品項，需決定選擇哪些推盤送至揀貨點之路徑，以滿足訂單需求品項。本研究以推盤位置分佈為節點，可行移動為節線展開「時空網路」，並分別依「障礙物」與「空格」等不同觀點而設計兩個整數規劃模式。雖然此二整數規劃模式可得精確最佳解，但求解效率有限，為驗證與比較求解效率，本研究再設計「動態規劃演算法」與「滾動式求解演算法」，其中前者可設定求取精確解或估算解；而後者則試圖將原系統劃分成數個規模較小但有部分空間重覆的子系統，以滾動方式一次求解一個子系統，使得欲移動的推盤在每個子系統中得以持續往其目的地移動。
在本研究提出的三種可計算精確最佳解的方法中，依空格數由多至少，其運算效率表現具優勢者依序為「障礙物觀點數學模式」、「空格觀點數學模式」，與「動態規劃演算法」。針對求解空格數較少的大規模系統，上述三種精確解法將耗時過久，較適合使用效率較佳的「滾動式求解演算法」來處理，但其求解品質與運算時間仍會隨空格的位置分佈、子系統範圍劃分方式、以及子系統涵蓋之空格數而有所差異。由測試結果顯示，滾動式求解演算法在處理空格數較多的測資時效能較佳，且能藉由擴增子系統涵蓋範圍來改善求解品質，但需找到合適的子系統範圍劃分方式才能兼具求解效率與效能，建議未來可嘗試優化滾動式演算法子系統劃分邏輯，以及使用滾動式演算法計算之完工時刻為深度優先動態規劃法之初始最大時限來加速求解。

This research discusses the problem of picking path planning in high density puzzle-based storage systems (PBS). The grid storage space is nearly fully occupied by loads (e.g., Autonomous Mobile Robot, AMR) allowed to move in the up, down, left, and right directions on a floor plane. Multiple loads can move simultaneously. This research plans the movement path of loads (including the target loads and the loads to be moved during the process) to minimize the time required for any specified load to move to the picking point. Unlike most literature that only minimizes the number of moving steps of a single target, this study considered movements of multiple loads and targets. When multiple loads can move simultaneously, issues such as waiting time between loads and avoiding collisions must also be considered.
The picking path planning problem can be regarded as a variant of the multi-commodity network flow problem. Two mixed integer programming (MIP) models are developed from the load or space point of view. They can calculate exact optimal solutions but are time-consuming. A dynamic programming algorithm (DP) and a rolling-horizon algorithm are developed to calculate a good solution with acceptable quality and time by parameter adjustments. Numerical analysis results show that when there are fewer spaces (i.e., almost fully occupied by loads), the MIP running time increases, but the DP running time decreases. The solution quality of the rolling-horizon algorithm depends on how the subsystems are divided. A subsystem of a larger space ratio leads to a smaller optimality gap. For future research, we suggest improving the partitioning logic of subsystems and solving the problem by the rolling-horizon algorithm cooperated with DP.

Yalcin, A. (2017). Multi-agent route planning in grid-based storage systems (Doctoral dissertation, Europa-Universität Viadrina Frankfurt).
Taylor, G. D., & Gue, K. R. (2008). The effects of empty storage locations in puzzle-based storage systems. In IIE Annual Conference. Proceedings (p. 519). Institute of Industrial and Systems Engineers (IISE).
Gue, K. R. (2006). Very high density storage systems. IIE Transactions, 38(1), 79-90.
Gue, K. R., & Kim, B. S. (2007). Puzzle‐based storage systems. Naval Research Logistics (NRL), 54(5), 556-567.
Li, J. T., & Liu, H. J. (2016). Design optimization of amazon robotics. Automation, Control and Intelligent Systems, 4(2), 48-52.
Mirzaei, M., De Koster, R. B., & Zaerpour, N. (2017). Modelling load retrievals in puzzle-based storage systems. International Journal of Production Research, 55(21), 6423-6435.
De Koster, R., Le-Duc, T., & Roodbergen, K. J. (2007). Design and control of warehouse order picking: A literature review. European journal of operational research, 182(2), 481-501.
Kota, V. R., Taylor, D., & Gue, K. R. (2015). Retrieval time performance in puzzle-based storage systems. Journal of Manufacturing Technology Management, 26(4): 582–602.
Bukchin, Y., & Raviv, T. (2021). A comprehensive toolbox for load retrieval in puzzle-based storage systems with simultaneous movements. DOI: 10.13140/RG.2.2.32086.98884
Yunfeng, M. A., Haoxun, C. H. E. N., & Yugang, Y. U. (2022). An efficient heuristic for minimizing the number of moves for the retrieval of a single item in a puzzle-based storage system with multiple escorts. European Journal of Operational Research, 301(1), 51-66.