توصيفگر ها :
سيستم ربات متحرك هوشمند , انبارداري , زمان‌بندي برداشت سفارش , بازپرسازي , برنامه‌ريزي محدوديت , الگوريتم جستوجوي همسايگي بزرگ تطبيق‌يافته
چكيده فارسي :
سيستم ربات متحرك هوشمند يك سيستم اقلام به نزد انباردار است كه در خرده‌فروشي‌هاي برخط استفاده مي‌شود. در اين سيستم قفسه‌ها توسط ربات‌ها به ايستگاه‌هاي برداشت يا بازپرسازي منتقل مي‌شوند تا اقلام توسط نيروي انساني برداشته شده يا در قفسه‌ها انبارش شوند. در اين سيستم، اجراي همزمان دو فرايند برداشت و بازپرسازي قابل انجام بوده و مي‌تواند موجب بهبود عملكرد سيستم و پاسخگويي سريع‌تر به سفارش‌هاي مشتريان نسبت به اجراي دو فرايند به صورت مجزا شود. به همين دليل بررسي اين دو فرايند به صورت يكپارچه اهميت دارد.
در اين پايان‌نامه در مرحله‌ي اول، مسائل مرتبط با فرايند برداشت سفارش از جمله مسائل تخصيص سفارش‌ها به ايستگاه‌هاي برداشت، ترتيب پاسخ به سفارش‌ها در هر ايستگاه برداشت، انتخاب قفسه‌ها براي پاسخ به سفارش‌ها، زمان‌بندي حركت قفسه‌ها و ترتيب و تعداد برداشت اقلام از هر قفسه به صورت يكپارچه بررسي مي‌شود. همچنين به عنوان نوآوري اين پژوهش، دو عامل موجودي اقلام و فاصله‌ي قفسه‌ها از ايستگاه‌هاي برداشت در مسئله‌ي برداشت سفارش در سيستم ربات متحرك هوشمند در نظر گرفته مي‌شوند. در اين پژوهش يك مدل برنامه‌ريزي عدد صحيح مختلط و يك مدل برنامه‌ريزي محدوديت به همراه تغيير روش شاخه‌زني و شش اصل غلبه براي بهبود كارايي آن و به منظور كمينه‌سازي زمان اتمام برداشت سفارش ارائه مي‌شود. آزمايش‌هاي عددي نشان مي‌دهد كه مدل برنامه‌ريزي محدوديت نسبت به مدل برنامه‌ريزي رياضي براي حل مسائل ابعاد متوسط عملكرد بهتري دارد. همچنين يك الگوريتم جستوجوي همسايگي بزرگ تطبيق‌يافته مبتني بر يك الگوريتم ابتكاري براي حل مسائل ابعاد بزرگ ارائه مي‌شود. در الگوريتم پيشنهادي دو روش توالي سفارش تصادفي و روش توالي سفارش مبتني بر مشابهت سفارش‌ها براي تعيين توالي اوليه‌ي سفارش‌ها و دو شاخص ابتكاري نسبت اقلام قابل برداشت به فاصله و همچنين جمع اقلام قابل برداشت و فاصله براي انتخاب قفسه‌ها پيشنهاد مي‌گردد. نتايج عددي نشان مي‌دهد كه استفاده از روش توالي سفارش مبتني بر مشابهت سفارش‌ها براي تعيين توالي اوليه‌ي سفارش‌ها و شاخص ابتكاري جمع اقلام قابل برداشت و فاصله براي انتخاب قفسه نسبت به ساير رويكردها در حل مسائل ابعاد متوسط به طور ميانگين تا 07,2% و در حل مسائل ابعاد بزرگ به طور ميانگين تا 18,5% عملكرد بهتري دارد.
در مرحله‌ي دوم و با توجه به اين موضوع كه امكان اجراي همزمان دو فرايند برداشت و بازپرسازي در سيستم ربات متحرك هوشمند وجود دارد، مسائل مرتبط با اين دو فرايند به صورت يكپارچه بررسي شده و ضمن در نظر گرفتن كليه‌ي مسائل مرتبط با فرايند برداشت، مسائل مرتبط با فرايند بازپرسازي نيز از جمله تخصيص اقلام ورودي به ايستگاه‌هاي بازپرسازي، انتخاب قفسه‌ها جهت انبارش اقلام ورودي، زمان‌بندي حركت قفسه‌‌هاي انتخاب شده و ترتيب و تعداد اقلام قابل انبارش در هر قفسه مشخص مي‌شود. برنامه‌ريزي يكپارچه‌ي دو فرايند برداشت و بازپرسازي از نوآوري‌هاي اين پژوهش محسوب مي‌شود. در اين بخش نيز ضمن ارائه‌ي يك مدل برنامه‌ريزي رياضي و يك مدل برنامه‌ريزي محدوديت به همراه روش‌هاي شاخه‌زني و اصول غلبه، يك الگوريتم ابتكاري به منظور حل مسائل مرتبط با فرايند بازپرسازي نيز معرفي مي‌گردد كه به الگوريتم معرفي شده براي حل مسائل فرايند برداشت اضافه مي‌شود تا امكان برنامه‌ريزي همزمان دو فرايند برداشت و بازپرسازي وجود داشته باشد. در اين الگوريتم نيز دو شاخص با نام‌هاي نسبت ظرفيت خالي به فاصله و همچنين جمع ظرفيت خالي و فاصله به عنوان شاخص‌هاي ابتكاري براي انتخاب قفسه به منظور انبارش اقلام ورودي معرفي مي‌گردد. نتايج عددي نشان مي‌دهد كه استفاده از شاخص ابتكاري جمع ظرفيت خالي و فاصله نسبت به شاخص ابتكاري نسبت ظرفيت خالي به فاصله براي نمونه‌هاي ابعاد متوسط به طور ميانگين تا 68,5% و براي نمونه‌هاي ابعاد بزرگ به طور ميانگين تا 24,6% نتايج بهتري را ارائه مي‌كند.
چكيده انگليسي :
Robotic Mobile Fullfilment is an inventory system used in online retail stores. In this system, racks are moved by robots to picking or replenishment stations so that items can be picked up by human labor or stored in the racks. In this system, the simultaneous execution of the two processes of picking and replenishment is possible and can improve system performance and responsiveness to customer orders compared to executing the two processes separately. Therefore, the integrated examination of these two processes is important.
In this thesis, in the first stage, issues related to the order picking process are examined, including the order allocation for picking stations, the order response sequence at each picking station, selection of racks to fulfill orders, scheduling rack movements, and the uniformity of item picking from each rack. Additionally, as an innovation in this research, two factors, item inventory and rack distance from picking stations, are considered in the order picking problem in Robotic Mobile Fullfilment. In this study, an integer programming model and a constraint programming model with a modified branching method and six dominance rules are presented to improve system performance and minimize order picking makespan. Numerical experiments show that the constraint programming model performs better than the mathematical programming model for medium-sized problems. Furthermore, a adaptive large neighborhood search algorithm based on a heuristic algorithm is proposed for solving large-scale problems. The proposed algorithm suggests two methods: a random order sequence method and a similarity-based order sequence method for determining the initial order sequence, and two heuristic indices, Pickable Items-to-Distance Ratio and the Sum of Pickable Items and Distance, for selecting racks. Numerical results show that using the similarity-based order sequencing method to determine the initial sequence of orders and the heuristic index of the Sum of Pickable Items and Distance compared to other approaches in solving medium-sized problems has, on average, 7.02% better performance, and in solving large-sized problems has, on average, 18.5% better performance.
In the second stage, considering the possibility of simultaneously executing two picking and replenishment processes in a Robotic Mobile Fullfilment System, issues related to both processes are investigated holistically. All issues related to the picking process, as well as those related to the replenishment process, such as allocation of orders to replenishment stations, rack selection for items , scheduling of rack movements, and the order and quantity of item replenishment from each rack are taken into account. The integrated planning of the two processes is also considered as an innovation in this research. In this section, a mathematical programming model and a constraint programming model with branching methods and dominance rules are presented to minimize the makespan. Additionally, an innovative algorithm is proposed to solve replenishment-related problems as an extension to the algorithm introduced for picking-related problems. In this algorithm, two heuristic indices named Empty Capacity-to-Distance Ratio and Sum of Empty Capacity and Distance are suggested for selecting racks for item storage. Numerical results show that using the initiative index of um of Empty Capacity and Distance compared to the initiative index of capacity to distance for medium-sized samples, on average, provides up to 68.5% better performance, and for large-sized samples, on average, provides up to 24.6% better performance.
