臺灣博碩士論文加值系統

This thesis focuses on dealing with the Tasks – Vehicles Assigning Problem in a two lane autonomous smart warehouse, which is a part in a three year project joining the Productivity 4.0 program hosted by Executive Yuan as well as the Taiwan Government, using autonomous guided vehicles (AGVs) as the main force for goods retrieval. The motivation of this thesis comes from the rapid risen and development in e – commerce as well as network flow, the foundation of Industry 4.0, and the Internet of Everything in the warehouse management field. Using the KIVA – Like robot used in the Amazon e – retailer, this thesis will solved a combinatorial problem by utilizing optimization method named Hungarian method, which recorded as one of the fastest resulting local optima results, for finding the best combinations among the tasks – vehicles ensuring that the tasks are fulfilled in ascendant order with minimum total time in retrieving goods. Another interest in this thesis is finding the relationships between the total number of vehicles and the warehouse’s parameters such as number of pods, number of total tasks and aisles length ensuring that deadlock conflictions are prohibited in a two – lane warehouse context. A simulated model also be proposed in this thesis, using MATLAB 2015a for optimizing the routing problem and NETLOGO 6.0 for simulating and visual interface on how the warehouse will function and also used for analyzing the warehouse systems’ performance.

This thesis focuses on dealing with the Tasks – Vehicles Assigning Problem in a two lane autonomous smart warehouse, which is a part in a three year project joining the Productivity 4.0 program hosted by Executive Yuan as well as the Taiwan Government, using autonomous guided vehicles (AGVs) as the main force for goods retrieval. The motivation of this thesis comes from the rapid risen and development in e – commerce as well as network flow, the foundation of Industry 4.0, and the Internet of Everything in the warehouse management field. Using the KIVA – Like robot used in the Amazon e – retailer, this thesis will solved a combinatorial problem by utilizing optimization method named Hungarian method, which recorded as one of the fastest resulting local optima results, for finding the best combinations among the tasks – vehicles ensuring that the tasks are fulfilled in ascendant order with minimum total time in retrieving goods. Another interest in this thesis is finding the relationships between the total number of vehicles and the warehouse’s parameters such as number of pods, number of total tasks and aisles length ensuring that deadlock conflictions are prohibited in a two – lane warehouse context. A simulated model also be proposed in this thesis, using MATLAB 2015a for optimizing the routing problem and NETLOGO 6.0 for simulating and visual interface on how the warehouse will function and also used for analyzing the warehouse systems’ performance.

Table of Contents
Acknowledgement i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables vii
Chapter 1.Introduction 1
1.1 Background 1
1.2 Objective 9
1.3 Problem Limitation 9
1.4 Research Methodology 10
1.5 Organization of Thesis 10
Chapter 2.Literature Review 12
2.1 Automatic Guided Vehicle system (AGVs) 12
2.2 Amazon Kiva System 13
2.3 AGV collaborations 14
2.4 Conflict Tree Problem 16
2.5 The Cross Aisle and Warehouse Layout Design 19
2.6 Generalized Assignment Problem 20
2.7 Hungarian Method 22
Chapter 3.Problem Statement 27
3.1 Warehouse Vehicle Routing Introduction 27
3.1.1. Traditional Warehouse 27
3.1.2. Proposed Warehouse 28
3.1.3. Common Process 30
3.2 Characteristic of the Proposed Warehouse 31
3.2.1. Overall Warehouse 31
3.2.2. Order Picking Station 32
3.2.3. Tasks arrangement 33
3.2.4. Vehicles Good Retrieval Process 33
3.3 Problem Assumption and Identification 33
3.3.1. Problem Assumption 33
3.3.2. Problem Identification 34
3.4 Mathematical Model 35
Chapter 4.Simulation Flow Chart 39
4.1 Overall Simulation Flow Chart 39
4.2 Pseudo Code for the Problem 40
Chapter 5.Simulation Analysis 50
5.1 Input Assumption 50
5.2 Simulation Results Discussion 53
Answer for Question 1 : 53
Answer for Question 2 : 59
Chapter 6.Conclusions and Future Suggestions 62
References 64

[1]. Applegate, L. M., Holsapple, C. W., Kalakota, R., Radermacher, F. J., & Whinston, A. B. (1996). Electronic commerce: building blocks of new business opportunity. Journal of Organizational Computing and Electronic Commerce, 6(1), 1-10.
[2]. Azi, N., Gendreau, M., & Potvin, J.-Y. (2010). An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 202(3), 756-763.
[3]. Baidya, R., & Ghosh, S. K. (2015). Model for a predictive maintenance system effectiveness using the analytical hierarchy process as analytical tool. IFAC-PapersOnLine, 48(3), 1463-1468.
[4]. Banharnsakun, A., Achalakul, T., & Batra, R. C. (2012). Target finding and obstacle avoidance algorithm for microrobot swarms. Paper presented at the Systems, Man, and Cybernetics (SMC), 2012 IEEE International Conference on.
[5]. Baynote. (2014, May 28). Infographic: The E-Commerce Big Leagues: Baynote.
[6]. Bechtsis, D., Tsolakis, N., Vlachos, D., & Iakovou, E. (2017). Sustainable supply chain management in the digitalisation era: The impact of Automated Guided Vehicles. Journal of Cleaner Production, 142, 3970-3984.
[7]. Beni, G., & Wang, J. (1993). Swarm intelligence in cellular robotic systems Robots and Biological Systems: Towards a New Bionics? (pp. 703-712): Springer.
[8]. Boehning, M. (2014). Improving safety and efficiency of agvs at warehouse black spots. Paper presented at the Intelligent Computer Communication and Processing (ICCP), 2014 IEEE International Conference on.
[9]. Dr. Ralf C. Schaepfer, Markus Koch, Dr. Phillip Merkofer. “Industry 4.0: Challenges and solutions for the digital transformation and use of exponential technologies”. Deloitte AG. Zurich. 2014.
[10]. Dziwis, D. (2005). Automated/Self Guided Vehicles (AGV/SGV) and System Design Considerations. http://www.werc.org/assets/1/workflow_staging/Publications/430.PDF
[11]. Fazlollahtabar, H., Fazlollahtabar, H., Saidi-Mehrabad, M., Saidi-Mehrabad, M., Masehian, E., & Masehian, E. (2015). Mathematical model for deadlock resolution in multiple AGV scheduling and routing network: a case study. Industrial Robot: An International Journal, 42(3), 252-263.
[12]. Ferrante, E., Turgut, A. E., Duéñez-Guzmán, E., Dorigo, M., & Wenseleers, T. (2015). Evolution of self-organized task specialization in robot swarms. PLoS Comput Biol, 11(8), e1004273.
[13]. Field, B. F., & Kasper, J. G. (1991). Automated guided vehicle: Google Patents.
[14]. Fukuda, T., & Ueyama, T. (1992). Self-organizing cellular robotic system. Comparison between social system and robotic system. Paper presented at the Biomedical Engineering Days, 1992., Proceedings of the 1992 International.
[15]. Gatica, C. P., Koester, M., Gaukstern, T., Berlin, E., & Meyer, M. (2016). An industrial analytics approach to predictive maintenance for machinery applications. Paper presented at the Emerging Technologies and Factory Automation (ETFA), 2016 IEEE 21st International Conference on.
[16]. Guizzo, E. (2008). Three engineers, hundreds of robots, one warehouse. IEEE Spectrum, 45(7), 26-34.
[17]. Jevtić, A., Gazi, P., Andina, D., & Jamshidi, M. (2010). Building a swarm of robotic bees. Paper presented at the World Automation Congress (WAC), 2010.
[18]. Kapanoglu, M., Alikalfa, M., Ozkan, M., & Parlaktuna, O. (2012). A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time. Journal of intelligent manufacturing, 23(4), 1035-1045.
[19]. Koff, G. A., & Boldrin, B. (2008). Automated guided vehicles. Materials Handling Handbook, 2nd Edition, 273-314.
[20]. Kumar, N., Zeadally, S., & Misra, S. C. (2016). Mobile cloud networking for efficient energy management in smart grid cyber-physical systems. IEEE Wireless Communications, 23(5), 100-108.
[21]. Ladj, A., Tayeb, F. B.-S., & Varnier, C. (2016). An integrated prognostic based hybrid genetic-immune algorithm for scheduling jobs and predictive maintenance. Paper presented at the Evolutionary Computation (CEC), 2016 IEEE Congress on.
[22]. Lasi, H., Fettke, P., Kemper, H.-G., Feld, T., & Hoffmann, M. (2014). Industry 4.0. Business & Information Systems Engineering, 6(4), 239-242. doi: 10.1007/s12599-014-0334-4
[23]. Lee, E. A., & Seshia, S. A. (2011). Introduction to embedded systems: A cyber-physical systems approach: Lee & Seshia.
[24]. Liu, C., & Chen, J. (2015, August 14). Taiwan to invest NT$36 billion in Productivity 4.0 project. Retrieved December 15, 2016, from shttp://focustaiwan.tw/news/aipl/201508140011.aspx
[25]. Nguyen, Q., Kumar, S., & K.G, G. (2014). Using Predictive Analytics to Optimize Asset Maintenance in the Utilities Industry.
[26]. Olmi, R., Secchi, C., & Fantuzzi, C. (2011). Coordination of industrial AGVs. International Journal of Vehicle Autonomous Systems, 9(1-2), 5-25.
[27]. Olmi, R., Secchi, C., & Fantuzzi, C. (2011). An efficient control strategy for the traffic coordination of agvs. Paper presented at the Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on.
[28]. Pandey, R., & Singh, A. (2016, June 11). Utilization of AGVs and Machines in FMS Environment. Journal of Material Sciences & Engineering, 5(263). doi: 10.4172/2169-0022.1000263
[29]. Papa, G., Zurutuza, U., & Uribeetxeberria, R. (2016). Cyber physical system based proactive collaborative maintenance. Paper presented at the Smart Systems and Technologies (SST), International Conference on.
[30]. Poudel, D. B. (2013). Coordinating Hundreds of Cooperative, Autonomous Robots in a Warehouse. Jan, 27, 1-13.
[31]. Qin, Z. (2010). Introduction to E-commerce: Springer Science & Business Media.
[32]. Qiu, L., Wang, J., Chen, W., & Wang, H. (2015). Heterogeneous AGV routing problem considering energy consumption. Paper presented at the Robotics and Biomimetics (ROBIO), 2015 IEEE International Conference on.
[33]. Rajkumar, R. R., Lee, I., Sha, L., & Stankovic, J. (2010). Cyber-physical systems: the next computing revolution. Paper presented at the Proceedings of the 47th Design Automation Conference.
[34]. Schlaepfer, R., Koch, M., & Merkhofer, P. (2015). Industry 4.0 challenges and solutions for the digital transformation and use of exponential technologies. Deloitte, AG, Zurich. http:// www2. deloitte. com/ content/ dam/ Deloitte/ ch/ Documents/ manufacturing/ ch-en-manufacturing-industry-4-0-24102014. pdf (20.12. 2015).
[35]. Secchi, C., Olmi, R., Rocchi, F., & Fantuzzi, C. (2015). A dynamic routing strategy for the traffic control of agvs in automatic warehouses. Paper presented at the Robotics and Automation (ICRA), 2015 IEEE International Conference on.
[36]. Senanayake, M., Senthooran, I., Barca, J. C., Chung, H., Kamruzzaman, J., & Murshed, M. (2016). Search and tracking algorithms for swarms of robots: A survey. Robotics and Autonomous Systems, 75, 422-434.
[37]. Seshia, S. A., Hu, S., Li, W., & Zhu, Q. (2016). Design Automation of Cyber-Physical Systems: Challenges, Advances, and Opportunities. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
[38]. Shalom, B. (2014, September 09). Smart Logistics: Mobile meets the value chain (and makes it faster, smarter, and cheaper). Retrieved March 03, 2017, from https://venturebeat.com/2014/09/09/smart-logistics-mobile-meets-the-value-chain-and-makes-it-faster-smarter-and-cheaper/
[39]. Shimada, J., & Sakajo, S. (2016). A statistical approach to reduce failure facilities based on predictive maintenance. Paper presented at the Neural Networks (IJCNN), 2016 International Joint Conference on.
[40]. Stork, A. (2015). Visual Computing Challenges of Advanced Manufacturing and Industrie 4.0 [Guest editors' introduction]. IEEE computer graphics and applications, 35(2), 21-25.
[41]. Sultanovs, E., Skorobogatjko, A., & Romanovs, A. (2016). Centralized healthcare cyber-physical system's architecture development. Paper presented at the Power and Electrical Engineering of Riga Technical University (RTUCON), 2016 57th International Scientific Conference on.
[42]. Susto, G. A., & Beghi, A. (2016). Dealing with time-series data in Predictive Maintenance problems. Paper presented at the Emerging Technologies and Factory Automation (ETFA), 2016 IEEE 21st International Conference on.
[43]. Wahlster, W. (2013). The semantic product memory: an interactive black box for smart objects SemProM (pp. 3-21): Springer.
[44]. Wang, L., & Wang, G. (2016). Big Data in Cyber-Physical Systems, Digital Manufacturing and Industry 4.0. IJEM-International Journal of Engineering and Manufacturing (IJEM), 6(4), 1.
[45]. Wen-Jing, QIU Ling HSU. "Scheduling and Routing Algorithms for AGVs: a Survey." 1999
[46]. Wurman, P. R., D'Andrea, R., & Mountz, M. (2008). Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI magazine, 29(1), 9.
[47]. Yang, X.-S. (2010). Firefly algorithm, Levy flights and global optimization Research and development in intelligent systems XXVI (pp. 209-218): Springer.
[48]. Yang, X.-S. (2010). Firefly algorithm, stochastic test functions and design optimisation. International Journal of Bio-Inspired Computation, 2(2), 78-84.
[49]. Yuan. (2016, March 23). Manufacturing Productivity 4.0. Taiwan: Retrieved from http://www.ey.gov.tw/pda_en/Dictionary_Content.aspx?n=A240F8389D824425&sms=D8F3EB15472D7847&s=4E3155D2BBC1D24F.
[50]. Yuan. (2016, May 30). Smart Machine and Productivity 4.0 in Taiwan: Now and Future. Taiwan: Retrieved from www.cieca.org.tw/ConferenceData.aspx?mrid=838.
[51]. S. L. Francis, S. G. Anavatti, and M. Garratt, "D* lite Search algorithm with Fibonacci heap for Efficient Path Planning," 2012.
[52]. Birattari, M., Paquete, L., Stüztle, T., & Varrentrapp, K. (2001). Classification of Metaheuristics and Design of Experiments for the Analysis of Components. Technical report, Darmstadt University of Technology, Germany.