隨著線上購物風氣盛行，物流需求量與配送頻率亦日益增長。新型態的物流倉儲系統捨棄傳統整面的固架式儲位，以眾多可移動式的單一立體貨架來儲存產品，各貨架均可被一台小型機器人自底部頂起而在倉庫內移動。此類倉儲系統可充分彈性運用閒置之貨架與倉庫空間，不似傳統固架式倉儲系統常陷於不當的儲位規劃以及狹窄之揀貨通道，進而導致多餘、繁忙又不順暢之揀貨作業。過去相關研究大多將倉儲內之訂單揀貨流程分為(1)貨架選擇問題與(2)多機器人路徑規劃問題(Multi-Agent Path Finding, MAPF)等兩階段流程來個別探討。然而，現實中此兩階段流程的決策息息相關，理應要一併考量才能得到更好的整體物流效率。其中第一階段的相關文獻大多考量選取較少貨架，卻忽略各貨架之實際位置，導致其第二階段可能會走較久的路線；而第二階段決策的相關文獻大多假設每貨架皆配置一台專屬機器人，亦即機器人與貨架有相同數量，將機器人數量遠少於貨架的現實大幅簡化，導致規劃而得之移動路線效能不佳。此外，針對結束揀貨作業的貨架該被移至何處停留，亦無文獻加以著墨。
本研究試圖將上述兩階段物流決策及其衍生的相關問題一併處理，假設各台機器人與各貨架之初始位置、貨架上之貨物品項與數量、各站訂單需求等資訊皆為已知，探討如何指揮調度機器人去移動貨架，期以最快方式完成規劃期間所有訂單之揀貨、包裝、出口等作業。上述之揀貨作業包含指揮機器人移動至合適的貨架，將該貨架移至倉庫內的某揀貨站點，待駐守該站點的揀貨人員完成包裝作業後，再將該貨架移至合宜的暫存位置等數個步驟。因同時有多台機器人與貨架在倉庫內移動，如何避免彼此碰撞、阻塞而能以最快方式完成揀貨任務的路線規劃問題，其本質是一個NP-hard的多元商品網路流量問題。由於本議題十分新穎，除結合過去的兩階段倉儲內物流路線規劃外，更考量了機器人少於貨架個數的現實狀況，同時規劃機器人與貨架在兩階段流程中的最佳移動路徑。本研究使用「層空網路」圖的架構，以整數規劃模式處理機器人與貨架的指派以及避撞路徑之規劃，以在最短的時間內完成所有的訂單出貨；本研究也提出貪婪演算法，以及一滾動式求解演算法，將問題依時段切分成數個較小規模的問題再依序求解，以加速整體的求解過程；數值測試結果顯示本研究設計之求解演算法可在短時間內得到不錯的可行解，可供相關系統在其實務應用中參考使用。

We investigate a realistic problem from a Robotic Movable Fulfillment System (RMFS), where racks containing items are carried by robots to workstations for finishiing orders. For a planning horizon, we seek efficient and effective ways to route robots and racks with minimum makespan or total waiting time for collecting all items in given orders. Related literature usually simplifies this complex problem to two easier subproblems: (1) movable rack selection to assign racks to workstations, and (2) multi-agent path finding (MAPF) to plan collision-free routings for racks (as robots). To the best of our knowledge, this thesis may arguably be the first that deals with both subproblems at the same time. Also, we further route a just-off-duty rack from a workstation to its destined storage region for avoiding congestion near the workstation. This problem is NP-hard since its MAPF subproblem is already NP-hard. We propose a mixed integer programming (MIP) formulation similar to a multi-commodity network flow model on a level-space network. The MIP calculates an exact optimal solution but is time-consuming in practice. We introduce a rolling-horizon solution mechanism that divides the planning horizon into several shorter periods and solve the same MIP over a few consecutive periods in an iterative fashion. We propose a greedy algorithm to calculate a good quick solution. We also design three order sorting heuristics to improve the solution quality. Computational experiments indicate the total waiting time a better objective to optimize than the makespan. Some intriguing cases are reported where our MIP solution suggests carryover operations between robots that could never be considered by any MAPF-like heuristics. For such cases, the optimality gap by efficient heuristics may be up to 30% or more, which shows the advantages of the proposed MIP formulation.

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.
Drain, J. (2018). Two algorithms for the package-exchange robot-routing problem. Retrieved from https://arxiv.org/abs/1812.10215
Erdem, E., Kisa, D. G., Oztok, U., & Schüller, P. (2013). A general formal framework for pathfinding 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.
Ma, H., Koenig, S., Ayanian, N., Cohen, L., Hönig, W., Kumar, T. K., Uras, T., Xu, H., Tovey, C., & Sharon, G. (2017). Overview: Generalizations of multi-agent path finding to real-world scenarios. Retrieved from https://arxiv.org/abs/1702.05515
Ma, H., Tovey, C., Sharon, G., Kumar, T. K. S., & Koenig, S. (2016). Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. Paper presented at the Thirtieth AAAI Conference on Artificial Intelligence. Retrieved from https://dl.acm.org/doi/10.5555/3016100.3016346
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 40-66.
Sundar, S., & Singh, A. (2012). A hybrid heuristic for the set covering problem. Operational Research, 12(3), 345-365.
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
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 fulfilment 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