VIET NAM NATIONAL UNIVERSITY HO CHI MINH CITY HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY HUYNH HUU DUC APPLICATION OF CLUSTERING ALGORITHM FOR STORAGE LOCATION ASSIGNMENT PROBLEM IN SYNCHRONIZED ZONE ORDER PICKING WAREHOUSES Major: Industrial Engineering Major ID: 8520117 MASTER THESIS HO CHI MINH CITY, January 2023 THIS RESEARCH IS COMPLETED AT: HO CHI MINH CITY UNIVERSITY OF TECHNOLOGY – VNU HCM Instructor: PhD. Nguyen Duc Duy …………………………………………………. Do Thanh Luu……………………………………………………. Le Song Thanh Quynh…………………………………………… Master’s Thesis is defended at HCMC University of Technology, VNU-HCM on January 08, 2023.
The Board of The Master’s Thesis Defense Council includes: 1. Do Ngoc Hien……………………………………. Le Duc Dao……………………………………………………. Counter-Argument Member: PhD.
Do Thanh Luu……………………………. Counter-Argument Member: PhD. Le Song Thanh Quynh…………………… 5. Council Member: PhD.
Nguyen Van Thanh……………………………………. Verification of the Chairman of the Master’s Thesis Defense Council and the Dean of the Faculty of Mechanical Engineering after the thesis is corrected (if any). CHAIRMAN OF THE COUNCIL DEAN OF FACULTY OF MECHANICAL (Full name and signature) ENGINEERING (Full name and signature) i VIETNAM NATIONAL UNIVERSITY HCMC SOCIALIST REPUBLIC OF VIETNAM VNUHCM UNIVERSITY OF TECHNOLOGY Independence – Liberty – Happiness ________________________ __________________ MASTER’S THESIS ASSIGNMENTS Full name: HUYNH HUU DUC. Date of birth: August 08, 1997.
Place of birth: Long An. Major: Industrial Engineering. I – TITLE: APPLICATION OF CLUSTERING ALGORITHM FOR STORAGE LOCATION ASSIGNMENT PROBLEM IN SYNCHRONIZED ZONE ORDER PICKING WAREHOUSES/ ỨNG DỤNG GIẢI THUẬT PHÂN CỤM VÀO BÀI TOÁN XÁC ĐỊNH VỊ TRÍ LƯU TRỮ TRONG KHO LẤY HÀNG ĐỒNG THỜI ASSIGNMENTS AND CONTENT: Assignments: • Understanding the structure of k-means clustering algorithms. • Understanding the problem of storage location assignment in synchronized order picking warehouses.
• Applying the k-means clustering algorithm in a suitable way to solve the problem of storage location assignment in synchronized order picking warehouses. • Demonstrating the effectiveness of the proposed algorithm by using different data sets in the scope and goals of the thesis. Content: • Chapter 1 gives some introduction and determines the goal and scope of the study. ii • Chapter 2 reports the literature review and shows the methodology of the study.
• Chapter 3 presents the problem statement and the modified design of the clustering algorithm. • Chapter 4 shows the experimental validation and analysis results to prove the ability and extent of the proposed algorithm to the problem. • Chapter 5 gives conclusion statements and some suggestions for future studies. II – ASSIGNMENT DELIVERING DATE (based on the Decision on Assignments Delivering): September 05, 2022.
III – ASSIGNMENT COMPLETING DATE (based on the Decision on Assignments Delivering): December 18, 2022. IV – INSTRUCTOR: PhD. Nguyen Duc Duy. Ho Chi Minh City, ………………………….
INSTRUCTOR HEAD OF DEPARTMENT (Full name and signature) (Full name and signature) DEAN OF FACULTY OF MECHANICAL ENGINEERING (Full name and signature) iii ACKNOWLEDGEMENTS This thesis is completed with the valuable support of many people. First of all, I would like to express my special and sincere gratitude to my research advisor PhD Nguyen Duc Duy for thoughtfully instructing and consulting me during two hard semesters of conducting this thesis. Secondly, I want to express many thanks to Assoc. PhD Do Ngoc Hien, Head of Department of Industrial Systems Engineering, Ho Chi Minh City Univeristy of Technology for kindly giving me a good environment to work and study.
I am also grateful to all staff of Department of of Industrial Systems Engineering and members of Faculty of Mechanical Engineering for their kindness and sympathy when I carry out this thesis. Last but not least, it is my pleasure and lucky to be my parents’ son and to be a member of my close friends’ circle as well as my extended family. Thanks so much to them for accompanying me not only in my academic path but also in my memorable life. HUYNH HUU DUC iv ABSTRACT The development of E-commerce leads to the appearance of higher numbers of orders but with smaller amounts of item quantities per order.
In this situation, the important role of warehouses as buffering places is becoming more obvious. One of the common and vital performance metrics of warehouse operations is the efficiency of the order-picking phase. To improve this metric, several solutions are studied and applied, including the policy of synchronized zone order-picking systems. In this thesis, the author tries to prove that in synchronized zone order-picking warehouses, a proper mechanism of storage location assignment can contribute to the improvement rate of order-picking efficiency.
In more detail, the more the picking demand of two items is similar, the less the likelihood that these items should be located in the same zone should be so that the idle time between pickers when they simultaneously fulfill the order can be cut down, leading to improvement in the completion time of an order. Therefore, the author tries to develop a suitable k-means clustering algorithm to release lists of items that should be located in different zones as suggestions for warehouse staff to plan for the storage phase, aiming at improving order-picking efficiency. v TÓM TẮT LUẬN VĂN Sự phát triển của thương mại điện tử dẫn đến sự xuất hiện của số lượng đơn đặt hàng cao hơn nhưng với lượng đặt hàng của mỗi mặt hàng trên mỗi đơn hàng nhỏ hơn. Trong bối cảnh như vậy, vai trò bộ đệm quan trọng của nhà kho ngày càng trở nên rõ ràng.
Một trong những thước đo hiệu suất phổ biến và quan trọng của hoạt động nhà kho là hiệu quả của giai đoạn lấy hàng. Để cải thiện chỉ số này, một số giải pháp đã được nghiên cứu và áp dụng, trong đó có chính sách về hệ thống lấy hàng đồng thời. Trong luận án này, tác giả cố gắng chứng minh rằng trong kho lấy hàng đồng thời, cơ chế xác định vị trí lưu trữ phù hợp có thể góp phần nâng cao hiệu quả lấy hàng. Cụ thể hơn, nhu cầu lấy hàng của hai mặt hàng càng giống nhau thì khả năng các mặt hàng này nằm trong cùng một khu vực nên càng nhỏ đi, để thời gian nhàn rỗi giữa những người lấy hàng khi họ thực hiện lấy hàng đồng thời cho cùng một đơn hàng có thể được cắt giảm, dẫn đến cải tiến về thời gian hoàn thành đơn hàng.
Do đó, tác giả cố gắng phát triển thuật toán phân cụm k-mean phù hợp để đưa ra danh sách các mặt hàng nên đặt ở các khu vực khác nhau, từ đó cung cấp gợi ý cho nhân viên kho lập kế hoạch cho giai đoạn lưu trữ nhằm nâng cao hiệu quả lấy hàng. vi DECLARATION I hereby declare that this is my own research. All the data and the results used in this research are honest and have not been published in other studies. I will be totally responsible for my research if it is incorrect as mentioned above.
The research’s author HUYNH HUU DUC vii CONTENTS MASTER’S THESIS ASSIGNMENTS. iv TÓM TẮT LUẬN VĂN. vii List of Figures. x List of Tables.
xi List of Acronyms.3 Goal and scope. LITERATURE REVIEW AND METHODOLOGY .1 Literature review and contributions .1 Storage location assignment .2 Synchronized order picking warehouses .4 Hierarchical and partitional clustering .5 k-means clustering algorithms. PROBLEM AND ALGORITHM .2 Solution orientation and concept of flow .3 Feature selection and distance measure .4 Clustering evaluation function .5 Initial cluster centers selection method .1 Dimension reduction component .6 Determination of the number of clusters .8 Flow of the algorithm. EXPERIMENTAL RESULTS AND ANALYSIS .1 Operational context and notations .3 Implementation and results .5 Discussions on computational complexity.
CONCLUSION AND FUTURE DIRECTIONS. 41 List of Publications. INPUT DATA VERSIONS. 65 x List of Figures Figure 2.
Illustration of Synchronized Order Picking (source: [14]). An example of the method of determining the number of clusters. The master flow of the k-means algorithm. 32 xi List of Tables Table 2.
Literature review on Storage Location Assignment. Pseudo-code of Distance calculation function. Literature review on issue groups of random initialization. Summary of quantification orientations for initial selection of cluster centers.
Pseudo-code of function of initial selecting cluster centers. Matching between properties of the proposed intialization method based on m-NN and issue groups of random intialization. Pseudo-code of the function to determine the number of clusters. An example of the method of determining the number of clusters.
The detailed content of each component of the master flow. Summary of experimental results. 36 xii List of Acronyms Acronyms Terms CLA Clustering Algorithm CRCCM Cumulative Rate of Change of Candidate Measure m-NN m-nearest-neighbor OPT Order-Picking Processing Time PCA Principal Component Analysis PO Picking Order RCFDC Rate of Cumulative Frequency Distribution Change SKU Stock-Keeping-Unit SLA Storage Location Assignment SOP Synchronized Order-Picking 1 Chapter 1.1 MOTIVATION Warehousing plays a vital role in logistics and supply chain management, especially in Viet Nam.7% of logistics enterprises in Viet Nam provide warehousing services [1]. Additionally, the industry of e-commerce in Viet Nam has recently experienced significant developments [2], leading to a dramatically increasing demand for various items but in small volumes.
In such a trend, since warehouses have been playing a vital role as buffering spaces in supply chains and ensuring the uncertainty of consumer demand has as few adverse effects as possible on the stability of production systems [3 - 6], improvement activities in the warehouse operations are still a valuable and practical area to study. There are six fundamental warehouse processes, including receiving, putaway, storage, picking, packing, and shipping [7]. In which, storage is vital in the warehouse operation. While the other steps ensure smooth material flows inside and outside a warehouse, storage is where the buffering role of a warehouse in a supply chain presents apparently, placing items after the put-away process and before specific quantities of them are picked in the order-picking process to cover demands [8].
As a result, a mechanism set in the storage phase, like Storage Location Assignment (SLA) problems, has various effects on the efficiency of both inbound and outbound flows of a warehouse regarding several key performance indicators such as picking time and cost, productivity, delivery and inventory accuracy [5, 8, 9]. The order-picking process accounts for a large proportion, about 55% [7], of the operational cost of a warehouse. Therefore, this study focuses on SLA problems in the area of its relationship to order-picking processing efficiency and inherits the idea, from the study of Ene and Öztürk [5], of employing order-picking processing time (OPT) as the measure of the efficiency. According to Tompkins et al.
[10], OPT is constructed 2 mainly (about 95%) from four components: traveling time, searching time, picking time, and set-up time. Traveling time accounts for the most significant proportion (approximately 50%), so it is chosen as the indicator of the efficiency of the order- picking process in this study. To enhance the efficiency of the order-picking process in terms of the OPT, synchronized order-picking (SOP), or multiple items of the same picking order (PO) are collected simultaneously by pickers from pickers’ assigned zones, utilized [11]. Because of its operational advantages, the SOP warehouses are selected to be the scope of this study.
An SLA solution that targets improving the order-picking process can be broken down into two sub-processes: family grouping and storage allocation [12, 13]. In more detail, while the family grouping sub-process includes an analysis of correlation (or similarity) between items and a clustering step to formulate clusters of items that are highly similar in terms of some selected characteristics, the storage allocation sub- process includes drafting a priority list and a position assignment result based on this list for items.
