隨著電子商務的迅速發展，每日有大筆訂單需處理，這也帶動了物流倉儲的演變。新型態的物流倉儲系統Robotic Mobile Fulfillment System (RMFS)，考慮移動式貨架，貨架內儲存空間分層分隔，且儲格大小可彈性調整，存放不同體積的商品，特別適合網路購物少量多樣的消費特性。此系統的揀貨作業是透過機器人搬運可移動式貨架至揀貨工作站，讓人員進行揀貨。倉儲內之訂單揀貨流程可分為(1)貨架選擇問題，與(2)多機器人路徑規劃問題(Multi-Agent Path Finding, MAPF)，本研究處理第二階段的多機器人路徑規劃問題，假設各訂單該由哪組貨架及機器人完成、各個貨架及機器人的初始位置、貨架上的商品品項與數量、各個揀貨工作站的訂單需求皆是已知，探討如何安排機器人去移動貨架，期望最小化訂單總等待時間。因為同時有多個貨架與機器人進行移動，如何規劃一組避免碰撞的路徑使其能以最快時間完成所有訂單，本質是一個NP-hard的多元商品網路流量問題。本研究使用時空網路圖建構一個整數規劃模型，規劃多台機器人的避撞路徑，使機器人以最短時間內完成所有訂單。為加速求解並能處理較大規模的路線與排程規劃，本研究也提出兩種貪婪演算法的求解機制，並使用模擬退火法(Simulated Annealing)迭代求解出最佳的訂單完成順序。數值測試結果顯示本研究設計之求解演算法可在短時間內得到品質不錯的可行解，可供相關系統在實務應用中參考使用。

This research investigates a multi-agent path finding (MAPF) problem from a Robotic Movable Fulfillment System (RMFS). In this system, racks containing items are removable. Robots carry racks to workstations for finishing orders. It is an NP-hard problem to plan a collision-free path for several racks and robots. In this research, the number of robots is less than the number of racks. We route a robot from its position to its destined rack. Avoiding congestion near the workstation, we also route an off-duty rack from a workstation to its destined storage region. Most related literature simplifies this complex problem by assuming that each rack is a robot. They only plan collision-free paths for some racks (i.e., robots) to a workstation. Compared with our research, they only deal with around one-third of the routings. We propose an integer programming (IP) model based on the Multi-Commodity network flow problem on a time-space network to route robots and racks with a minimum total waiting time to collect all items following given orders. The IP model can only deal with small-scale cases. To deal with cases of a larger scale, we propose two greedy routing algorithms after a Simulated Annealing algorithm that calculates a good order sequence. Our computational experiments indicate that our solution methods are efficient and effective. This makes our solution methods arguably the first to deal with the MSPF problem of the most flexible settings with the best performance.

王宗翰. (2020) 考量移動式貨架選擇機制之多台倉儲機器人最佳揀貨作業路徑規劃研究. 國立成功大學工業與資訊管理學系碩士論文, 台南市. Retrieved from https://hdl.handle.net/11296/g7k43r
Boysen, N., Briskorn, D., & Emde, S. (2017). Parts-to-picker based order processing in a rack-moving mobile robots environment. European Journal of Operational Research, 262(2), 550-562.
Chvatal, V. (1979). A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3), 233-235.
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.
Erdem, E., Kisa, D. G., Oztok, U., & Schüller, P. (2013). A general formal framework for path finding problems with multiple agents. Paper presented at the Twenty-Seventh AAAI Conference on Artificial Intelligence. Retrieved from https://www.researchgate.net/publication/244864562_A_General_Formal_Framework_for_Pathfinding_Problems_with_Multiple_Agents
Hönig, W., Kiesel, S., Tinka, A., Durham, J. W., & Ayanian, N. (2018). Conflict-based search with optimal task assignment. Paper presented at the Seventeenth International Conference on Autonomous Agents and Multi Agent Systems. Retrieved from https://dl.acm.org/doi/10.5555/3237383.3237495
Li, J.-t., & Liu, H.-j. (2016). Design optimization of amazon robotics. Automation, Control and Intelligent Systems, 4(2), 48-52.
Li, Z. P., Zhang, J. L., Zhang, H. J., & Hua, G. W. (2017). Optimal Selection of Movable Shelves under Cargo-to-Person Picking Mode. International Journal of Simulation Modelling, 16(1), 145-156.
Ma, H., & Koenig, S. (2016). Optimal target assignment and path finding for teams of agents. Paper presented at the Fifteenth International Conference on Autonomous Agents & Multiagent Systems. Retrieved from https://arxiv.org/abs/1612.05693
Ma, H., & Koenig, S. (2017). AI buzzwords explained: Multi-agent path finding (MAPF). AI Matters, 3(3), 15-19.
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 40-66.
Surynek, P. (2015). Reduced time-expansion graphs and goal decomposition for solving cooperative path finding sub-optimally. Paper presented at the Twenty-Fourth International Joint Conference on Artificial Intelligence. Retrieved from https://www.ijcai.org/Proceedings/15/Papers/272.pdf
Valle, C. A., & Beasley, J. E. (2019). Order allocation, rack allocation and rack sequencing for pickers in a mobile rack environment. arXiv preprint arXiv:1903.06702.
Weidinger, F., Boysen, N., & Briskorn, D. (2018). Storage assignment with rack-moving mobile robots in KIVA warehouses. Transportation Science, 52(6), 1479-1495.
Wurman, P. R., D'Andrea, R., & Mountz, M. (2008). Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI magazine, 29(1), 9-19.
Xiang, X., Liu, C., & Miao, L. (2018). Storage assignment and order batching problem in Kiva mobile fulfillment system. Engineering Optimization, 50(11), 1941-1962.
Yu, J., & LaValle, S. M. (2013a). Planning optimal paths for multiple robots on graphs. Paper presented at the 2013 IEEE International Conference on Robotics and Automation. Retrieved from https://ieeexplore.ieee.org/document/6631084
Yu, J., & LaValle, S. M. (2013b). Structure and intractability of optimal multi-robot path planning on graphs. Paper presented at the Twenty-Seventh AAAI Conference on Artificial Intelligence. Retrieved from https://www.researchgate.net/publication/287708637_Structure_and_intractability_of_optimal_multi-robot_path_planning_on_graphs