Yusuf ŞAHİN, Elif G. DAYIOĞLU, Kenan KARAGÜL, Michael G. KAY

Route planning methods for a modular warehouse system

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 avariant of robot motion planning problem. The structures of the procedures aredeveloped in three steps for the simultaneous movement of multiple unit-sizedpackages in a modular warehouse. The proposed heuristic methods consist ofroute planning, tagging, and main control components. In order to demonstrate thesolution performance of the methods, various experiments were conducted withdifferent data sets and the solution times and qualities of the proposed methodswere compared with previous studies. It was found that the proposed methodsprovide better solutions when taking the number of steps and solution time intoconsideration.

PDF

___

[1] 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.
[2] Ç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.
[3] 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.
[4] 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]
[5] 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]
[6] Datar, M. (2011). Priority-based Control Algorithm for Movement of Packages in a Public Distribution Center. PhD Thesis, North Carolina State University.
[7] 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]
[8] Sittivijan, P. (2015). Modular Warehouse Control: Simultaneous Rectilinear Movement of Multiple Objects within Limited Free Space Environment. PhD Thesis, North Carolina State University.
[9] 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]
[10] Spitznagel, E.L. (1967). A new look at the fifteen puzzle. Mathematics Magazine, 40(4), 171-174.
[11] 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.
[12] Gue, K.R., & Kim, B.S. (2007). Puzzle‐based storage systems. Naval Research Logistics, 54(5), 556-567.
[13] 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.
[14] Hearn, R.A., & Demaine, E.D. (2005). PSPACEcompleteness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2), 72-96.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] 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.
[21] Sarrafzadeh, M., & Maddila, S.R. (1995). Discrete warehouse problem. Theoretical Computer Science, 140(2), 231-247.
[22] 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.
[23] 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.
[24] Švestka, P., & Overmars, M.H. (1998). Coordinated path planning for multiple robots. Robotics and Autonomous Systems, 23(3), 125-152.
[25] 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.
[26] 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.
[27] 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.
[28] 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.
[29] 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.
[30] 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.