伴隨著貨櫃裝運的需求逐年增加，貨櫃碼頭要藉著不斷改善產能以利國際海上運輸的競爭。無人搬運車系統(AGV)是維繫貨櫃碼頭執行轉運作業的重要工具。本論文聚焦在無人搬運車的途程問題上，旨在解決無人搬運車的運輸問題，提升卸貨作業的效率。卸貨的過程是進口貨櫃從貨櫃船到堆場之間的相關作業。本問題假設AGV的作業環境為一單向運行搬運區域，以無線控制方式操作AGV。AGV的搬運區域可說是虛擬的網路結構，用以導引AGV的位置和行進方向。常見的AGV途程問題是選擇或搜尋無碰撞情況產生的可行路徑。一般的AGV通常會被指派到最短距離或最短運輸時間的路徑上，當移動大量的貨櫃時，使用同樣的路徑容易引起阻塞。本研究根據即時的交通情形，指派搬運中的AGV選擇不同既定的路徑，達成搬運任務。每個任務都有固定數量的候選路徑，用以分散各路徑的AGV數量，減少阻塞。候選路徑是由典型的最短路徑與K條路徑演算法的方式求得。為了控制行進中的AGV，本論文利用移動決策(MDM)過程，讓AGV辨識路徑上可能發生的情形，並作出對應的移動決策；為了監控移動中的AGV，網路結構會被分成較小單位的區域。系統依據AGV的移動情形，分別記錄AGV途程上的資料諸如等待時間、運行時間、處理時間和總完工時間。
本論文比較使用最短路策略(SPS)與多條路徑策略(CPS)在卸貨作業中的差異。模擬過程顯示使用多條路徑可以減少AGV的等待時間與總完工時間，在不同規模的貨櫃數量上都能達到顯著的效果，有助於改善AGV搬運過程的旅行時間。針對不同的規模與選擇路徑的標準，顯著的效果僅出現在特定的實驗組合，可以做為決定候選路徑的參考依據。

With the dramatically increasing demand of containerization, container terminals gradually improve their productivity to compete in international maritime transportation. The automatic guided vehicle (AGV) system streamlines container movements in container terminals.
To increase the container handling throughput, we focus on the AGV routing problem in the container unloading process. The handling process considers from vessels to yard blocks. A unidirectional network structure which constructs the transportation area guides AGVs to the exact locations and directions of path segments. The purpose of a classical AGV routing problem is to select or find feasible conflict-free paths to transport specified tasks to destinations. In most AGV routing problems, loaded AGVs always follow the shortest distance paths or shortest time paths. Congestion is foreseen to increase as there are many containers along such a path. We resolve this AGV routing problem in the static routing setting, which assigns loaded AGVs to the shortest time paths according to the real-time conditions of the routes. There are a number of feasible path sets for sharing the AGV task flow.The feasible path sets are generated through the classical shortest path and the K-shortest path algorithms. A movement decision making (MDM) processes identifies the states on routes and determines the movement for each time unit for each route. The network structure is divided into smaller unit segments. The MDM process determines movements according to defined traffic conditions. A path selection process assigns loaded AGVs according to the specified criterion. The traveling information such as waiting time, transport time, handling time and make-span are recorded according to the movements on assigned routes.
We compare the effect of the shortest path and multiple paths for the unloading process. The simulation results show that our algorithm significantly reduces the total traveling time for adopting multiple paths. We further observe the effect of adopting different candidate path sizes for different workloads. The outcomes show the reduction of the average traveling time under CPS. However, the significances show on specified experiment combinations. We can take the outcomes as references for path size of candidate sets.

誌謝 I
摘要 II
ABSTRACT III
CONTENTS V
LIST OF FIGURES VI
LIST OF TABLES VIII
Ⅰ.INTRODUCTION 1
Ⅱ.LITERATURE REVIEW 7
Ⅲ.PROBLEM DESCRIPTION 19
3-1 UNLOADING PROCESS 19
3-2 GUIDE PATH LAYOUT 20
3-3 TRAFFIC CONTROL 23
3-3-1 Unit Space Control Layout 23
3-3-2 Traveling Time Element 25
Ⅳ.NUMERICAL ANALYSIS 35
4-1 SIMULATION MODEL 35
4-1-1 Input Data 36
4-1-2 Offline Set Up 36
4-1-3 Online Decision Process 43
Ⅴ. CONCLUSION AND FUTURE RESEARCH 55
APPENDIX A: EXPERIMENT CASE 57
APPENDIX B: EXPERIMENT OUTCOME AND HYPOTHESES TEST SHEET AND STRATEGY COMPARISONS 58
APPENDIX C: ACCURATE PATH ASSIGNMENT FOR EACH CPS 67
REFERENCES 68

1. Adriaansen, A.C. (2011) An automated guided vehicle system in a container terminal. Published Master Dissertation, Department of Mechanical Engineering, Eindhoven University of Technology, The Netherlands.
2. Asef-Vaziri, A., Laporte, G., Sriskandarajah, C. (2000) The block layout shortest loop design problem. IIE Transactions 32(1):727-734.
3. Bozer, Y. A., Srinivasan, M.M. (1991) Tandem configurations for automated guided vehicle systems and the analysis of single vehicle loops. IIE Transactions 23(1):72-82.
4. Briskorn, D., Drexl, A., Hartmann, S. (2006) Inventory-based dispatching of automated guided vehicles on container terminals. OR Spectrum 28(4):611-630.
5. Dijkstra, E.W.(1959) A note on two problems in connection with graphs. Numerische Mathematik 1(1):269-271.
6. Egbelu, P. J., Tanchoco, J.M.A. (1986) Potentials for bidirectional guide path for automated guided vehicle based system. International Journal of Production Research 24(5):1075-1097.
7. Evers, J.J.M., Koppers, S.A.J. (1996) Automatic guided vehicle traffic control at a container terminal. Transportation research A 30(1):21-34.
8. Farahani, R.Z., Laporte, G., Miandoabchi, E., Bina, S. (2007) Designing efficient methods for the tandem AGV network design problem using tabu search and genetic algorithm. The International Journal of Advanced Manufacturing Technology 36(9):996-1009.
9. Gaskins, R.J., Tanchoco, J.M.A. (1987) Flow path design for automated guided vehicles systems. International Journal of Production Research 25(5):667-676.
10. Goetz, W. G., Egbelu, P. J. (1990) Guide path design and location of load pick-up/drop-off points for an automated guided vehicle system. International Journal of Production Research 28(5):927-941.
11. Guzman, M.C., Prabhu, N., Tanchoco, J.M.A. (1997) Complexity of the AGV shortest path and single-loop guide path layout problems. International Journal of Production Research 35(8):2083-2092.
12. Jeon, S.M., Kim, K.H., Kopfer, H. (2010) Routing automated guided vehicles in container terminals through the Q-learning. Logistic Research 3(1):19-27.
13. Kaspi, M., Kesselman, U., Tanchoco, J.M.A. (2002) Optimal solution for the flow path design problem of a balanced unidirectional AGV system. International Journal of Production Research 40(2):389-401.
14. Kaspi, M., Tanchoco, J.M.A. (1990) Optimal flow path design of unidirectional AGV systems. International Journal of Production Research 28(6):1023-1030.
15. Kim, C. W., Tanchoco, J.M.A. (1991) Conflict-free shortest-time bidirectional AGV routing. International Journal of Production Research 29(12):2377-2391.
16. Kim, K.H., Bae, J.W. (1999) A dispatching method for automated guided vehicles to minimize delays of containership operations. International Journal of Management Science 5(1):23-27.
17. Koo, P.H., Lee, W.S., Jang, D.W. (2004) Fleet sizing and vehicle routing for container transportation in a static environment. OR Spectrum 26(2):193-209.
18. Krishnamurthy, N.N., Batta, R., Karwan, M. H. (1993) Developing conflict-free routes for automated guided vehicles. Operation research 41(6):1077-1090.
19. Le-Anh, T., De Koster, M.B.M. (2006) A review of design and control of automated guided vehicle systems. European Journal of Operational Research 171(1):1-23.
20. Lee, B.K., Kim, K.H. (2012) Optimizing the yard layout in container terminals. OR Spectrum 35(2):363-398.
21. Lee, J.H., Lee, B.H., Choi, M.H. (1998) A real-time traffic control scheme of multiple AGV systems for collision free minimum time motion: A routing Table approach. Systems, Man and Cybernetics, Part A: Systems and Humans 28(3):347-358.
22. Maersk line, (2015). The world largest ship. in http://www.maersk. com/en/hardware/triple-e. Jun,03,2015
23. Qiu, L., Hsu, W.J. (2001) A bidirectional path layout for conflict-free routing of AGVs. International Journal of Production Research 39(10):2177-2195.
24. Rashidi, H., Tsang, E., P.K. (2004) A complete and an incomplete algorithm for automated guided vehicle scheduling in container terminals. Computers & Mathematics with Applications 61(3):630-641.
25. Ross, E.A., Mahmoodi, F. Mosier, C.T. (1996) Tandem configuration Automated Guided Vehicle Systems: A Comparative Study. Decision Science 27(1):81-102.
26. Singh, S.P., Tiwari, M.K. (2002) Intelligent agent framework to determine the optimal conflict-free path for automated guided vehicles systems. International Journal of Production Research 40(16):4195-4223.
27. Sinriech, D., Tanchoco, J.M.A. (1993) Solution methods for the mathematical models of single-loop AGV systems. International Journal of Production Research 31(3):705-725.
28. Srivastava, S.C., Choudhary, A.K., Kumar, S., Tiwari, M.K.(2008) Development of an intelligent agent-based AGV controller for a flexible manufacturing system. The International Journal of Advanced Manufacturing Technology 36(7):780-797.
29. Steenken, D., Voß, S., Stahlbock, R. (2004) Container terminal operations research-a classification and literature review. OR spectrum 26(1):3-49.
30. Tanchoco, J.M.A., Sinricech, D. (1992) OSL-optimal single-loop guide paths for AGVS. International Journal of Production Research 30(3):665-681.
31. Vis, I.F.A. (2006) Survey of research in the design and control of guided path vehicle system. European Journal of Operational Research 170(3):677-709.
32. Vis, I.F.A., De Koster, R. (2003) Transshipment of containers at a container terminals: An overview. European Journal of Operational Research 147(1):1-16.
33. Vis, I.F.A., De Koster, R. (2003) Transshipment of containers at a container terminals: An overview. European Journal of Operational Research 147(1):1-16.
34. Vis, I.F.A., Harika, I. (2004) Comparison of vehicle types at an automated container terminal. OR Spectrum 26(1):117-143.
35. Voß, S., Stahlbock R. (2008) Operations research at container terminals: a literature update. OR spectrum 30(1):1-52.
36. World port rankings 2004-2013. (2015) Retrieved on June 18, 2015, from http://www.aapa-ports.org/Industry/content.cfm?ItemNumber=900.
37. Wu, N.Q., Zhou, M.C. (2007) Shortest routing of bi-directional automatic guided vehicles avoiding deadlock and blocking. Transactions of Mechatronics 12(1):63-72.
38. Yagan, S. (Ed.). (2007) Probability and Statistics for Engineers and Science, London: Prentice Hall.
39. Yang, C.H., Choi, Y.S., Ha, T.Y. (2004) Simulation-based performance evaluation of transport vehicles at automated container terminals. OR Spectrum 26(2):149-170.