Luận văn thạc sĩ kỹ thuật công nghiệp application of clustering algorithm for storage location assignment problem in synchronized zone order pciking warehouses

Luận văn thạc sĩ nghiên cứu kỹ thuật công nghiệp application of clustering algorithm for storage location assignment problem in, đánh giá hiện trạng, phân tích vấn đề, đề xuất

• Tác giả: Huỳnh Hữu Đức
• Người hướng dẫn: PhD. Nguyễn Đức Duy
• Trường học: Ho Chi Minh City University of Technology
• Chuyên ngành: Industrial Engineering
• Đề tài: Ứng Dụng Thuật Toán Phân Cụm Trong Bài Toán Phân Bổ Vị Trí Lưu Trữ Tại Kho Lấy Hàng Đồng Bộ
• Loại tài liệu: master thesis
• Năm xuất bản: 2023
• Địa điểm: Ho Chi Minh City

Mục lục chi tiết

• Nhiệm vụ luận văn thạc sĩ
• Lời cảm ơn
• Tóm tắt (tiếng Anh)
• Tóm tắt luận văn
• Lời cam đoan
• Danh mục hình ảnh
• Danh mục bảng biểu
• Danh mục từ viết tắt
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Động lực nghiên cứu
• 1.2. Phát biểu bài toán
• 1.3. Mục tiêu và phạm vi nghiên cứu
• 1.4. Bố cục luận văn
• 2. CHƯƠNG 2: TỔNG QUAN TÀI LIỆU VÀ PHƯƠNG PHÁP NGHIÊN CỨU
• 2.1. Tổng quan tài liệu và các đóng góp
• 2.1.1. Bài toán phân bổ vị trí lưu trữ
• 2.1.2. Kho lấy hàng đồng thời theo khu vực
• 2.1.4. Thuật toán phân cụm phân cấp và phân cụm phân vùng
• 2.1.5. Thuật toán phân cụm k-means
• 3. CHƯƠNG 3: BÀI TOÁN VÀ THUẬT TOÁN
• 3.2. Định hướng giải pháp và khái niệm luồng
• 3.3. Lựa chọn đặc trưng và độ đo khoảng cách
• 3.4. Hàm đánh giá phân cụm
• 3.5. Phương pháp chọn tâm cụm ban đầu
• 3.5.1. Thành phần giảm chiều dữ liệu
• 3.6. Xác định số lượng cụm
• 3.8. Luồng thực thi của thuật toán
• 4. CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM VÀ PHÂN TÍCH
• 4.1. Bối cảnh vận hành và các ký hiệu
• 4.3. Triển khai và kết quả
• 4.5. Thảo luận về độ phức tạp tính toán
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TƯƠNG LAI
• Danh mục các công trình công bố
• Các phiên bản dữ liệu đầu vào

Tóm tắt

I. Giới thiệu về bài toán phân bổ vị trí lưu trữ

Bài toán phân bổ vị trí lưu trữ trong kho lấy hàng đồng bộ là một phần quan trọng trong quản lý logistics và chuỗi cung ứng. Việc tối ưu hóa vị trí lưu trữ không chỉ giúp giảm thiểu chi phí mà còn nâng cao hiệu quả của quá trình lấy hàng. Theo thống kê, khoảng 55% chi phí hoạt động của kho liên quan đến quy trình lấy hàng. Do đó, việc áp dụng thuật toán phân cụm để xác định vị trí lưu trữ thích hợp có thể cải thiện đáng kể hiệu suất lấy hàng. Các phương pháp truyền thống thường không đáp ứng được yêu cầu của kho hiện đại, nơi mà sự thay đổi nhu cầu và tốc độ xử lý đơn hàng ngày càng tăng cao. Các nghiên cứu trước đây đã chỉ ra rằng việc phân tích sự tương quan giữa các mặt hàng và áp dụng thuật toán phân cụm dữ liệu như k-means có thể giúp xây dựng các nhóm mặt hàng tương tự, từ đó xác định vị trí lưu trữ hiệu quả hơn.

1.1 Đặc điểm của kho lấy hàng đồng bộ

Kho lấy hàng đồng bộ (SOP) là mô hình trong đó nhiều mặt hàng được lấy cùng lúc từ các khu vực khác nhau. Mô hình này giúp tiết kiệm thời gian và giảm thiểu thời gian chờ đợi giữa các người lấy hàng. Tuy nhiên, việc xác định vị trí lưu trữ cho các mặt hàng trong SOP cần phải được thực hiện một cách cẩn thận để đảm bảo rằng các mặt hàng có nhu cầu tương tự không được lưu trữ trong cùng một khu vực. Việc này nhằm giảm thiểu thời gian di chuyển và tối ưu hóa quy trình lấy hàng. Phân tích dữ liệu và xác định mối quan hệ giữa các mặt hàng là rất quan trọng để thực hiện điều này. Các nghiên cứu gần đây đã chỉ ra rằng việc áp dụng thuật toán k-means có thể mang lại những kết quả tích cực trong việc nhóm các mặt hàng tương tự và từ đó đưa ra các quyết định phân bổ vị trí lưu trữ hiệu quả.

II. Phương pháp và thuật toán k means

Thuật toán k-means là một trong những thuật toán phân cụm phổ biến nhất được sử dụng trong bài toán phân bổ vị trí lưu trữ. Thuật toán này hoạt động bằng cách phân chia dữ liệu thành k nhóm dựa trên các đặc điểm tương đồng của chúng. Quá trình này bao gồm việc xác định các tâm cụm và phân loại các điểm dữ liệu vào các cụm gần nhất. Việc áp dụng thuật toán phân cụm trong ngữ cảnh của kho lấy hàng đồng bộ có thể giúp tối ưu hóa việc phân bổ vị trí lưu trữ, giảm thiểu thời gian lấy hàng và nâng cao hiệu suất hoạt động. Các yếu tố như thời gian di chuyển, thời gian tìm kiếm và thời gian lấy hàng được xem xét để tối ưu hóa quy trình. Điều này đặc biệt quan trọng trong bối cảnh thương mại điện tử, nơi mà số lượng đơn hàng gia tăng nhưng với khối lượng mặt hàng nhỏ hơn.

2.1 Cấu trúc và hoạt động của thuật toán k means

Thuật toán k-means bắt đầu bằng việc xác định số lượng cụm k mà người dùng mong muốn. Sau đó, nó sẽ chọn ngẫu nhiên k điểm từ dữ liệu làm tâm cụm ban đầu. Tiếp theo, thuật toán sẽ phân loại các điểm dữ liệu vào các cụm dựa trên khoảng cách đến các tâm cụm. Sau mỗi lần phân loại, tâm cụm mới sẽ được tính toán lại dựa trên trung bình của các điểm trong mỗi cụm. Quá trình này lặp lại cho đến khi không còn sự thay đổi nào trong việc phân loại. Việc sử dụng phân tích dữ liệu để xác định các đặc điểm của mặt hàng và sự tương quan giữa chúng là rất quan trọng trong việc tối ưu hóa quy trình này. Sự chính xác trong việc phân nhóm mặt hàng sẽ giúp giảm thiểu thời gian di chuyển giữa các khu vực, từ đó nâng cao hiệu suất của quy trình lấy hàng.

III. Kết quả thực nghiệm và phân tích

Trong nghiên cứu này, các kết quả thực nghiệm cho thấy rằng việc áp dụng thuật toán phân cụm k-means đã mang lại những cải tiến rõ rệt trong hiệu suất của quy trình lấy hàng. Các thử nghiệm được thực hiện trên nhiều bộ dữ liệu khác nhau đã chứng minh rằng việc phân bổ vị trí lưu trữ hợp lý có thể giảm thiểu thời gian di chuyển và thời gian xử lý đơn hàng. Hệ thống kho lấy hàng đồng bộ đã được cải thiện đáng kể nhờ vào việc phân nhóm các mặt hàng tương tự và phân bổ chúng vào các khu vực khác nhau. Điều này không chỉ giúp tiết kiệm thời gian mà còn giảm thiểu chi phí vận hành. Các chỉ số hiệu suất chính như thời gian hoàn thành đơn hàng và độ chính xác trong việc lấy hàng đã được nâng cao, cho thấy giá trị thực tiễn của việc áp dụng thuật toán máy học trong lĩnh vực logistics.

3.1 Phân tích hiệu suất và độ chính xác

Các chỉ số hiệu suất được sử dụng để đánh giá kết quả bao gồm thời gian di chuyển, thời gian lấy hàng và độ chính xác trong quy trình lấy hàng. Kết quả cho thấy rằng khi áp dụng thuật toán k-means, thời gian di chuyển giữa các khu vực được giảm thiểu đáng kể. Điều này có nghĩa là người lấy hàng có thể hoàn thành đơn hàng nhanh hơn, dẫn đến việc cải thiện độ chính xác và giảm thiểu sai sót trong quá trình lấy hàng. Hơn nữa, việc phân tích dữ liệu cho thấy rằng các mặt hàng có nhu cầu tương tự được nhóm lại với nhau giúp tối ưu hóa quy trình, từ đó nâng cao hiệu suất hoạt động của kho. Những phát hiện này cho thấy rằng việc áp dụng thuật toán phân cụm dữ liệu không chỉ có giá trị lý thuyết mà còn mang lại lợi ích thực tiễn trong quản lý kho và logistics.

Nội dung chính

Tổng quan nghiên cứu

Trong hệ thống logistics và chuỗi cung ứng hiện đại, kho hàng đóng vai trò là không gian đệm chiến lược nhằm giảm thiểu tác động tiêu cực từ sự biến động nhu cầu của thị trường đối với tính ổn định của sản xuất. Theo thống kê của ngành logistics tại Việt Nam, khoảng 70% doanh nghiệp cung cấp dịch vụ kho bãi. Sự bùng nổ của thương mại điện tử với tốc độ tăng trưởng doanh thu bán lẻ trực tuyến vượt 20% mỗi năm đã làm thay đổi đáng kể hành vi tiêu dùng: số lượng đơn hàng (Picking Orders - PO) tăng vọt nhưng số lượng sản phẩm trên mỗi đơn hàng lại giảm nhỏ. Trong cấu trúc chi phí vận hành kho, quy trình lấy hàng (order picking) chiếm tỷ trọng lớn nhất, lên tới khoảng 55% tổng chi phí. Đồng thời, thời gian di chuyển (traveling time) của nhân viên chiếm xấp xỉ 50% tổng thời gian xử lý đơn hàng (Order-Picking Processing Time - OPT), trong khi 95% OPT được cấu thành từ 4 yếu tố chính: di chuyển, tìm kiếm, bốc dỡ và chuẩn bị.

Để nâng cao hiệu suất lấy hàng, mô hình lấy hàng đồng thời theo khu vực (Synchronized Zone Order Picking - SOP) được ứng dụng rộng rãi, nơi nhiều nhân viên cùng thực hiện thu gom các mặt hàng thuộc cùng một đơn hàng tại các phân khu được chỉ định riêng biệt. Tuy nhiên, bài toán phân bổ vị trí lưu trữ (Storage Location Assignment Problem - SLAP) trong kho SOP thường gặp thách thức lớn về sự chênh lệch thời gian nhặt hàng giữa các khu vực, dẫn đến thời gian chờ đợi (idle time) kéo dài và làm giảm hiệu quả chung.

Nghiên cứu này tập trung giải quyết vấn đề trên bằng cách phát triển một giải thuật phân cụm k-means cải tiến. Mục tiêu cụ thể là nhóm các mặt hàng (Stock-Keeping Units - SKU) có mức độ tương đồng cao về nhu cầu và số lượng đặt hàng vào cùng một cụm, từ đó phân bổ các mặt hàng trong cùng cụm sang các khu vực (zones) lưu trữ khác nhau. Quy tắc này giúp triệt tiêu thời gian nhàn rỗi giữa các nhân viên lấy hàng, từ đó rút ngắn đáng kể thời gian hoàn thành đơn hàng. Nghiên cứu được thực hiện tại Trường Đại học Bách khoa – ĐHQG TP.HCM từ tháng 09/2022 đến tháng 01/2023, mang lại giải pháp định lượng giúp tối ưu hóa từ 15% đến 25% thời gian xử lý đơn hàng trong môi trường kho vận thực tế.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu vận dụng lý thuyết quản trị vận hành kho bãi hiện đại kết hợp với bài toán phân bổ vị trí lưu trữ (SLAP). Theo khung lý thuyết của các nghiên cứu kinh điển trong ngành, quy trình giải quyết SLAP được chia thành hai giai đoạn: gom nhóm dòng hàng (family grouping) và phân bổ vị trí lưu trữ vật lý (storage allocation). Trong mô hình kho lấy hàng đồng thời (SOP), nhiều nhân viên cùng xử lý một đơn hàng tại các khu vực tách biệt, do đó thời gian hoàn thành đơn hàng phụ thuộc vào thời gian của nhân viên hoàn thành muộn nhất (makespan).

Lý thuyết phân cụm dữ liệu phân vùng (Partitional Clustering), đặc biệt là thuật toán k-means, được lựa chọn làm nền tảng toán học chính. Nghiên cứu chuẩn hóa và vận dụng 5 khái niệm chuyên ngành then chốt:

1. Đối tượng dữ liệu (Object/Data point): Đại diện cho một mã sản phẩm (SKU) với thông tin số lượng được yêu cầu trong các đơn hàng.
2. Thời gian xử lý lấy hàng (OPT): Thước đo hiệu suất chính, tỷ lệ thuận với quãng đường và thời gian di chuyển của nhân viên kho.
3. Khoảng cách Euclidean bậc hai: Thước đo khoảng cách tổng hợp giữa các cặp mặt hàng dựa trên độ lệch số lượng yêu cầu qua các đơn hàng $D_{ij} = \sqrt{\sum (q_{io} - q_{jo})^2}$.
4. Bán kính lân cận $m$-NN ($m$-nearest-neighbor radius): Khoảng cách lớn nhất trong số $m$ đối tượng gần nhất với đối tượng đang xét, trong đó tham số $m$ được gán bằng số lượng nhân viên lấy hàng trong ca làm việc.
5. Độ đo ứng viên (Candidate Measure): Tỷ số giữa mật độ điểm lân cận trong bán kính trung bình và bán kính $m$-NN của chính đối tượng đó, phản ánh tiềm năng trở thành tâm cụm.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp nghiên cứu thực nghiệm định lượng kết hợp mô hình hóa toán học. Nguồn dữ liệu bao gồm 6 bộ tham số thử nghiệm: 5 bộ dữ liệu được trích xuất và mã hóa bảo mật từ hệ thống quản lý kho (WMS) của doanh nghiệp phân phối thương mại điện tử thực tế và 1 bộ dữ liệu chuẩn (benchmark dataset) từ các công bố quốc tế uy tín. Cỡ mẫu nghiên cứu bao gồm từ 10 đến 100 đơn hàng (POs), 13 đến 50 mặt hàng (SKUs) và 3 đến 10 nhân viên lấy hàng trong mỗi ca vận hành. Phương pháp lấy mẫu phi xác suất có chủ đích (purposive sampling) được áp dụng nhằm chọn lọc các ca làm việc có mật độ đơn hàng cao và tính chất mặt hàng đa dạng, phản ánh đầy đủ áp lực vận hành thực tế.

Lý do lựa chọn giải thuật k-means cải tiến xuất phát từ ưu điểm vượt trội về độ phức tạp tính toán thấp $O(N)$ so với các thuật toán phân cấp (Hierarchical Clustering), đặc biệt thích hợp với bài toán ra quyết định nhanh khi tiếp nhận hàng tại cửa nhập (Inbound Dock). Tác giả đã cải tiến thuật toán k-means qua 3 điểm mới: (1) Khởi tạo tâm cụm ban đầu dựa trên bán kính lân cận $m$-NN nhằm loại bỏ tính ngẫu nhiên; (2) Xác định tự động số cụm $k$ thông qua chỉ số biến thiên tần số tích lũy của độ đo ứng viên (CRCCM) với ngưỡng $\epsilon_{Initial} = 10%$, thay thế phương pháp Elbow vốn đòi hỏi can thiệp thủ công; (3) Tích hợp hàm đánh giá phân cụm nội bộ vào điều kiện dừng với ngưỡng $\epsilon_{Convergence} = 10%$ và số lần lặp liên tiếp $\delta = 10$. Toàn bộ quy trình nghiên cứu được triển khai thực hiện từ tháng 09/2022 đến tháng 12/2022 và bảo vệ chính thức vào tháng 01/2023.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình chạy thử nghiệm thuật toán trên 6 bộ dữ liệu với các quy mô khác nhau đã mang lại những phát hiện quan trọng:

1. Khắc phục triệt để tính bất định của khởi tạo ngẫu nhiên: Phương pháp khởi tạo dựa trên $m$-NN và độ đo ứng viên (Candidate Measure) giúp xác định duy nhất một tập hợp tâm cụm ban đầu tối ưu. Phương pháp này loại bỏ 100% rủi ro rơi vào cực trị cục bộ và nguy cơ xuất hiện cụm rỗng do các điểm dị biệt (outliers), vốn là điểm yếu cố hữu của thuật toán k-means truyền thống.
2. Tự động hóa hoàn toàn việc xác định số cụm tối ưu: Cơ chế CRCCM đã xác định chính xác số lượng cụm $k$ (ví dụ từ $k=3$ đến $k=5$ tùy theo cấu trúc dữ liệu) mà không cần sự can thiệp trực quan của chuyên gia phân tích. So với phương pháp Elbow truyền thống phải lặp qua toàn bộ dải giá trị $k$, phương pháp đề xuất giúp tiết kiệm hơn 60% thời gian tính toán xác định tham số ban đầu.
3. Tốc độ hội tụ nhanh và ổn định: Hàm đánh giá phân cụm tổng thể $E_{overall}$ (được tính bằng căn bậc hai của tổng bình phương khoảng cách giữa các cặp phần tử trong cùng một cụm) đạt trạng thái hội tụ ổn định chỉ sau 2 đến 10 vòng lặp. Điều này đáp ứng xuất sắc yêu cầu ra quyết định phân bổ vị trí lưu trữ trong thời gian thực tại các nhà kho bận rộn.
4. Cân bằng tải và rút ngắn thời gian xử lý đơn hàng: Khi phân bổ các SKU có nhu cầu nhặt tương đồng vào các zone khác nhau, độ lệch thời gian nhặt hàng giữa các nhân viên giảm mạnh. Kết quả mô phỏng cho thấy thời gian hoàn thành đơn hàng (OPT/makespan) giảm từ 18% đến 24% so với các chính sách phân bổ ngẫu nhiên hoặc phân bổ chỉ dựa trên tần suất cùng xuất hiện đơn thuần.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán đạt hiệu quả cao là sự thay đổi bản chất của đặc trưng phân cụm: sử dụng chênh lệch số lượng lấy hàng thực tế (picking quantity) của từng SKU trong từng đơn hàng thay vì chỉ đếm số lần cùng xuất hiện (co-appearance). Các nghiên cứu trước đây thường cho rằng hai mặt hàng xuất hiện cùng nhau trong nhiều đơn hàng thì nên xếp tách biệt. Tuy nhiên, nếu một mặt hàng có số lượng nhặt là 50 sản phẩm trong khi mặt hàng kia chỉ có 1 sản phẩm, nhân viên ở khu vực thứ nhất vẫn phải mất thời gian nhặt lâu hơn rất nhiều, khiến nhân viên ở khu vực thứ hai rơi vào trạng thái chờ đợi. Bằng cách đo khoảng cách chênh lệch số lượng qua không gian đa chiều của các đơn hàng, thuật toán đảm bảo các mặt hàng có khối lượng nhặt cân bằng sẽ được chia đều cho các nhân viên, giúp họ hoàn thành công việc gần như cùng một thời điểm.

Dữ liệu thực nghiệm được trực quan hóa hiệu quả thông qua biểu đồ đường biểu diễn sự thay đổi của độ đo ứng viên (Candidate Measure) và tỷ lệ thay đổi tích lũy (CRCCM). Điểm bẻ gãy vượt ngưỡng $\epsilon_{Initial} = 10%$ phản ánh ranh giới rõ ràng để chọn ra các tâm cụm đại diện có mật độ cao và cách xa nhau. Đồng thời, bảng ma trận kết quả chạy 6 bộ tham số minh chứng rằng giá trị hàm mục tiêu $E_{overall}$ giảm đều đặn qua các thế hệ lặp, khẳng định tính vững chắc của mô hình toán học khi áp dụng vào thực tiễn logistics.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu, 4 khuyến nghị mang tính hành động cao được đề xuất cho các doanh nghiệp và nhà quản trị chuỗi cung ứng:

1. Tích hợp module k-means cải tiến vào hệ thống WMS hiện hữu: Bộ phận Công nghệ Thông tin và Kỹ sư Hệ thống cần triển khai tích hợp thuật toán vào phần mềm WMS trong vòng 3 đến 6 tháng tới. Module này phải tự động xử lý dữ liệu đơn hàng và đưa ra gợi ý phân bổ vị trí lưu kho cho các lô hàng mới tại Inbound Dock với thời gian xử lý dưới 3 phút cho mỗi lô 500 SKU.
2. Thiết lập chu kỳ tái phân bổ vị trí lưu trữ động (Dynamic Re-slotting): Giám đốc vận hành kho cần chuẩn hóa quy trình đánh giá lại vị trí lưu trữ định kỳ 30 ngày một lần. Việc cập nhật ma trận số lượng đơn hàng theo mùa vụ giúp duy trì tỷ lệ cân bằng tải giữa các nhân viên lấy hàng luôn đạt trên 90%, giảm thiểu thời gian nhàn rỗi phát sinh do xu hướng tiêu dùng thay đổi.
3. Trang bị thiết bị quét mã vạch và chỉ dẫn lấy hàng đồng bộ theo thời gian thực: Ban quản lý kho cần đầu tư nâng cấp hạ tầng thiết bị cầm tay (Handheld Scanners) hoặc hệ thống Pick-to-Light tại từng phân khu trong vòng 6 tháng. Mục tiêu là đồng bộ hóa 100% dữ liệu tiến độ nhặt hàng giữa các zone, nâng cao độ chính xác kiểm kê lên trên 99.5%.
4. Ứng dụng kỹ thuật phân tích thành phần chính (PCA) cho kho dữ liệu lớn: Khi quy mô đơn hàng vượt quá 10.000 đơn hàng/ngày, đội ngũ kỹ sư dữ liệu cần hoàn thiện cấu phần giảm chiều dữ liệu PCA trước quý 2 năm tới nhằm nén không gian đặc trưng đơn hàng, giúp rút ngắn thêm 35% thời gian tính toán của thuật toán phân cụm.

Đối tượng nên tham khảo luận văn

Luận văn cung cấp nhiều giá trị thực tiễn và học thuật cho 4 nhóm đối tượng chính:

1. Giám đốc vận hành và Quản lý kho bãi (Warehouse Managers & Operations Directors): Nắm vững phương pháp phân vùng lưu trữ khoa học để tái cấu trúc không gian kho, tối ưu hóa năng suất lao động của nhân viên và cắt giảm từ 15% đến 25% chi phí vận hành lấy hàng.
2. Kỹ sư Kỹ thuật Hệ thống Công nghiệp và Quản lý Chuỗi cung ứng (Industrial Engineers): Sử dụng các mô hình toán học, phương pháp đo khoảng cách Euclidean cải tiến và thuật toán phân cụm $m$-NN để ứng dụng giải quyết các bài toán tối ưu hóa tài nguyên, cân bằng chuyền và định tuyến trong nhà máy.
3. Giảng viên, Nghiên cứu sinh và Học viên Cao học ngành Logistics: Tiếp cận một tài liệu tham khảo học thuật chỉn chu về phương pháp giải quyết bài toán SLAP kết hợp SOP, mở ra các hướng nghiên cứu nâng cao về thuật toán meta-heuristic hoặc học tăng cường (Reinforcement Learning).
4. Các công ty phát triển giải pháp phần mềm Quản lý Kho hàng (WMS Vendors): Tận dụng mã giả (pseudo-code) và luồng thuật toán chi tiết trong luận văn để phát triển các tính năng phân bổ vị trí lưu trữ thông minh (Smart Slotting Module), nâng cao giá trị thương mại cho sản phẩm phần mềm.

Câu hỏi thường gặp

Bài toán SLA trong kho lấy hàng đồng thời (SOP) khác gì so với kho truyền thống?

Trong kho truyền thống với một người nhặt toàn bộ đơn hàng, các mặt hàng hay mua cùng nhau thường được xếp cạnh nhau để rút ngắn quãng đường. Ngược lại, trong kho SOP với nhiều người nhặt song song ở các khu vực khác nhau, các mặt hàng có nhu cầu tương đương phải được xếp ở các khu vực tách biệt. Điều này giúp các nhân viên hoàn thành việc lấy hàng cùng lúc, giảm thiểu thời gian chờ đợi.

Tại sao nghiên cứu sử dụng số lượng mặt hàng (quantity) làm đặc trưng thay vì chỉ đếm số lần cùng xuất hiện?

Nếu hai mặt hàng luôn xuất hiện cùng nhau nhưng một mặt hàng cần nhặt 100 đơn vị sản phẩm còn mặt hàng kia chỉ cần 1 đơn vị, thời gian xử lý tại hai khu vực vẫn chênh lệch rất lớn. Việc sử dụng số lượng mặt hàng làm vector đặc trưng giúp phản ánh chính xác thời gian thao tác thực tế của nhân viên, từ đó cân bằng khối lượng công việc hiệu quả hơn.

Phương pháp khởi tạo tâm cụm $m$-NN có ưu thế gì vượt trội so với khởi tạo ngẫu nhiên?

Khởi tạo ngẫu nhiên trong k-means dễ dẫn đến nghiệm cục bộ không tối ưu hoặc tạo ra các cụm rỗng do điểm nhiễu. Phương pháp $m$-NN tính toán mật độ lân cận và độ đo ứng viên (Candidate Measure) dựa trên số lượng nhân viên thực tế, tạo ra tập tâm cụm ban đầu cố định, có độ phủ rộng và đại diện chính xác nhất cho cấu trúc dữ liệu.

Cơ chế CRCCM tự động xác định số lượng cụm $k$ thay thế phương pháp Elbow như thế nào?

Phương pháp Elbow truyền thống yêu cầu chạy thử nghiệm lặp lại nhiều lần trên dải giá trị của $k$ và cần chuyên gia quan sát đồ thị để chọn điểm gãy. Cơ chế CRCCM theo dõi tốc độ thay đổi tích lũy của độ đo ứng viên; ngay khi chỉ số này vượt ngưỡng $\epsilon_{Initial} = 10%$, thuật toán tự động chọn số cụm $k$ tối ưu mà không cần bất kỳ sự can thiệp thủ công nào.

Thuật toán có khả năng áp dụng cho kho hàng quy mô hàng chục nghìn SKU không?

Hoàn toàn khả thi. Thuật toán k-means có độ phức tạp tính toán tuyến tính $O(N)$, rất thích hợp cho dữ liệu lớn. Đối với các kho có hàng chục nghìn SKU và số lượng đơn hàng khổng lồ, việc tích hợp thêm kỹ thuật giảm chiều dữ liệu PCA như định hướng của luận văn sẽ giúp nén dữ liệu hiệu quả và duy trì tốc độ xử lý nhanh chóng.

Kết luận

• Luận văn đã mô hình hóa thành công bài toán phân bổ vị trí lưu trữ (SLAP) trong mô hình kho lấy hàng đồng thời (SOP), giải quyết triệt để vấn đề thời gian chờ đợi giữa các nhân viên lấy hàng.
• Đóng góp học thuật nổi bật là giải thuật k-means cải tiến với phương pháp khởi tạo tâm cụm dựa trên bán kính lân cận $m$-NN và cơ chế tự động xác định số cụm $k$ thông qua chỉ số CRCCM.
• Kết quả thực nghiệm trên 6 bộ tham số chứng minh tính ổn định cao, thuật toán hội tụ nhanh chóng sau 2 đến 10 vòng lặp và giúp cải thiện thời gian xử lý đơn hàng từ 15% đến 25%.
• Kế hoạch tiếp theo trong giai đoạn tới là hoàn thiện cấu phần giảm chiều dữ liệu PCA và thử nghiệm thuật toán trên hệ thống kho tự động hóa hoàn toàn (AS/RS).
• Đề tài là công trình nghiên cứu công phu, có giá trị học thuật và tính ứng dụng thực tiễn cao, mở ra giải pháp tối ưu hóa đột phá cho ngành quản trị chuỗi cung ứng và logistics hiện đại.

Trích đoạn nội dung tài liệu

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.