Route planning methods for a modular warehouse system

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

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.


Keywords


Warehouse management; Motion planning; Heuristics algorithms

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.11121/ijocta.01.2020.00752

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Elif G. Dayıoğlu, Kenan Karagül, Yusuf Şahin, Michael G. Kay

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

footer_771

   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM    PROQUEST   ZBMATH more...