Route planning methods for a modular warehouse system

Elif G. Dayıoğlu; Kenan Karagül; Yusuf Şahin; Michael G. Kay

doi:10.11121/ijocta.01.2020.00752

Authors

Elif G. Dayıoğlu Mersin University http://orcid.org/0000-0002-4716-952X
Kenan Karagül Pamukkale University http://orcid.org/0000-0001-5397-4464
Yusuf Şahin Burdur Mehmet Akif Ersoy University http://orcid.org/0000-0002-3862-6485
Michael G. Kay NC State University http://orcid.org/0000-0002-1359-8270

DOI:

https://doi.org/10.11121/ijocta.01.2020.00752

Keywords:

Warehouse management, Motion planning, Heuristics algorithms

Abstract

In this study, procedures are presented that can be used to determine the routes of the packages transported within a modular storage system. The problem is a variant of robot motion planning problem. The structures of the procedures are developed in three steps for the simultaneous movement of multiple unit-sized packages in a modular warehouse. The proposed heuristic methods consist of route planning, tagging, and main control components. In order to demonstrate the solution performance of the methods, various experiments were conducted with different data sets and the solution times and qualities of the proposed methods were compared with previous studies. It was found that the proposed methods provide better solutions when taking the number of steps and solution time into consideration.

Downloads

Download data is not yet available.

Author Biographies

Elif G. Dayıoğlu, Mersin University

Elif G. Dayıoğlu received her B.S. and M.S. degree from the Computer Engineering Department of Pamukkale University in 2014 and 2017 respectively. She is currently pursuing a PhD degree in Computer Engineering at Çukurova University. She has been working as a research assistant at the Computer Technology and Infırmation Systems Department of Mersin University since 2014.

Kenan Karagül, Pamukkale University

Kenan Karagül studied industrial engineering for his Bachelor degree and business administration for M.S. and PhD degrees. His field of study includes operations research, logistics, vehicle routing problems, metaheuristics, and quantitative models. He worked at various firms between 1996 and 2001. He worked at Pamukkale University as an instructor until 2013. He has been working at the same university as an assistant professor since 2013. He was awarded the best Ph.D. thesis on Graduate Tourism Students Congress in Kuşadası (2014).

Yusuf Şahin, Burdur Mehmet Akif Ersoy University

Yusuf Şahin received the M.S. degree in industrial engineering from Pamukkale University in 2009 and a PhD degree in business administration from Suleyman Demirel University in 2014. He has been an assistant professor of business administration at Burdur Mehmet Akif Ersoy University since 2014. His field of study includes operations research, logistics, warehouse management, vehicle routing, meta-heuristics, and quantitative models.

Michael G. Kay, NC State University

Michael G. Kay has been a professor of Industrial Engineering at North Carolina State University since 1992. He is Interim Director of the Operations Research Graduate Program and is Associate Director of Graduate Programs in the ISE Department. He is the current President of the College-Industry Council on Material Handling Education.

References

Mason-Jones, R., & Towill, D.R. (1999). Total cycle time compression and the agile supply chain. International Journal of Production Economics, 62(1-2), 61-73.

Çancı, M., & Erdal, M. (2009). Lojistik Yönetimi: Freight Forwarder El Kitabı. 3. Baskı, Uluslararası Taşımacılık ve Lojistik Hizmet Üretenleri Derneği, İstanbul.

Sahin, Y., & Eroğlu, A. (2015). Hierarchical Solution of Order Picking and Capacitated Vehicle Routing Problems. Suleyman Demirel University Journal of Engineering Sciences and Design, 3(1), 15-28.

Xiang, L., Kay, M.G., & Telford, J. (2007). Public Logistics Network Protocol Design and Implementation [online]. North Carolina, North Carolina State University, Available from: https://people.engr.ncsu.edu/kay/pln/IERC07.pdf [Accessed 15 August 2018]

Kay, M. G. (2004). Protocol Design for a Public Logistic Network [online]. North Carolina, North Carolina State University, Available from: https://people.engr.ncsu.edu/kay/pln/IMHRC04.pdf [Accessed 16 August 2018]

Datar, M. (2011). Priority-based Control Algorithm for Movement of Packages in a Public Distribution Center. PhD Thesis, North Carolina State University.

Kay, M.G. (2013). Home Delivery Logistics Networks using Driverless Delivery Vehicles [online]. North Carolina, North Carolina State University, Available from: https://people.engr.ncsu.edu/kay/hdln/HDLNuDDV.pdf [Accessed 15 August 2018]

Sittivijan, P. (2015). Modular Warehouse Control: Simultaneous Rectilinear Movement of Multiple Objects within Limited Free Space Environment. PhD Thesis, North Carolina State University.

Bauer, B. (1994). The Manhattan Pair Distance Heuristic for the 15-Puzzle [online]. Paderborn, Universitat-GH Paderborn. Available from: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.7&rep=rep1&type=pdf [Accessed 25 July 2018]

Spitznagel, E.L. (1967). A new look at the fifteen puzzle. Mathematics Magazine, 40(4), 171-174.

Reinefeld, A. (1993). Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*. Thirteenth International Joint Conference on Artificial Intelligence, pp 248-253.

Gue, K.R., & Kim, B.S. (2007). Puzzle‐based storage systems. Naval Research Logistics, 54(5), 556-567.

Flake, G.W., & Baum, E.B. (2002). Rush Hour is PSPACE-complete, or "Why you should generously tip parking lot attendants. Theoretical Computer Science, 270(1-2), 895-911.

Hearn, R.A., & Demaine, E.D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2), 72-96.

Hauptman, A., Elyasaf, A., Sipper, M., & Karmon, A. (2009). GP-Rush: using genetic programming to evolve solvers for the Rush Hour puzzle. 11th Annual Conference on Genetic and Evolutionary Computation, pp 955-962.

Sharma, R., & Aloimonos, Y. (1992). Coordinated motion planning: the warehouseman's problem with constraints on free space. IEEE Transactions on systems, man, and cybernetics, 22(1), 130-141.

Hopcroft, J.E., Schwartz, J.T., & Sharir, M. (1984). On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE-Hardness of the Warehouseman's Problem. The International Journal of Robotics Research, 3(4), 76-88.

Yeung, D.Y., & Bekey, G. (1987). A decentralized approach to the motion planning problem for multiple mobile robots. IEEE International Conference on Robotics and Automation, 4, 1779-1784.

Sanchez, G., Latombe, & Jean-Claude (2002). Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. IEEE International Conference on Robotics and Automation, 2, 2112-2119.

Sharma, R., & Aloimonos, Y., (1992). Coordinated motion planning: the warehouseman's problem with constraints on free space. IEEE Transactions on systems, man, and cybernetics, 22(1), 130-141.

Sarrafzadeh, M., & Maddila, S.R. (1995). Discrete warehouse problem. Theoretical Computer Science, 140(2), 231-247.

LaValle, S.M., & Hutchinson, S.A. (1998). Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics and Automation, 14(6), 912-925.

Azarm, K., & Schmidt, G. (1997). Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation. IEEE International Conference on Robotics and Automation, 4, 3526-3533.

Švestka, P., & Overmars, M.H. (1998). Coordinated path planning for multiple robots. Robotics and Autonomous Systems, 23(3), 125-152.

Leroy, S., Laumond, J.P., & Siméon, T. (1999). Multiple path coordination for mobile robots: A geometric algorithm. 16th International Joint Conference on Artificial Intelligence, pp 1118-1123.

Guo, Y., & Parker, L.E. (2002). A distributed and optimal motion planning approach for multiple mobile robots. IEEE International Conference on Robotics and Automation, 3, 2612-2619.

Yamashita, A., Arai, T., Ota, J., & Asama, H. (2003). Motion planning of multiple mobile robots for cooperative manipulation and transportation. IEEE Transactions on Robotics and Automation, 19(2), 223-237.

Liu, S. Mao, L., & Yu, J., (2006). Path planning based on ant colony algorithm and distributed local navigation for multi-robot systems. IEEE International Conference on Mechatronics and Automation, pp 1733-1738.

Koç, Ç., Erbaş, M., & Ozceylan, E. (2018). A rich vehicle routing problem arising in the replenishment of automated teller machines. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 8(2), 276-287.

Uddin, M.F., & Kazushi, S.A.N.O., (2011). Coordination and Optimization: The integrated supply chain analysis with non-linear price-sensitive demand. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 2(1), 83-94.