Title 35_P10 final-319-322.pdf ✅

319 HỘI THẢO KHOA HỌC QUỐC GIA VỀ LOGISTICS VÀ QUẢN LÝ CHUỖI CUNG ỨNG VIỆT NAM LẦN THỨ 4 (CLSCM-2024) NGHIÊN CỨU BÀI TOÁN TỐI ƯU TUYẾN ĐƯỜNG NHẶT HÀNG TRONG HOẠT ĐỘNG KHAI THÁC KHO RESEARCH ON OPTIMIZING ORDER-PICKING ROUTES IN WAREHOUSE OPERATION PHẠM THỊ MAI PHƯƠNG* , PHẠM THỊ YẾN, NGUYỄN THỊ NHA TRANG Bộ môn Logistics, Khoa Kinh tế, Trường Đại học Hàng hải Việt Nam *Email liên hệ: [email protected] Tóm tắt Bài báo này nghiên cứu việc áp dụng thuật toán A* để tối ưu hóa tuyến đường nhặt hàng trong hoạt động khai thác kho. Với sự phát triển của ngành logistics và thương mại điện tử, yêu cầu về hiệu quả và tốc độ trong quản lý kho hàng ngày càng cao. Tuy nhiên, việc xác định tuyến đường nhặt hàng tối ưu trong kho vẫn là một thách thức lớn. Bằng cách áp dụng thuật toán A*, nghiên cứu đã tìm ra giải pháp tối ưu hóa lộ trình nhặt hàng, giúp giảm thời gian xử lý đơn hàng, chi phí vận hành và tăng cường hiệu suất hoạt động của kho. Kết quả cho thấy ứng dụng này đã cải thiện quá trình nhặt hàng, giảm thiểu tình trạng tắc nghẽn và nâng cao hiệu suất làm hàng. Từ khóa: Tối ưu tuyến đường, hoạt động nhặt hàng, thuật toán A*. Abstract This paper studies the application of the A* algorithm to optimize the order-picking routes warehouse operation.. With the growth of the logistics and e-commerce sectors, the demands for efficiency and speed in warehouse management are becoming increasingly higher. However, identifying the optimal order-picking routes in warehouse remains a significant challenge. By applying the A* algorithm, this research has found a solution to optimize the picking routes, reducing order processing time, operational costs, and enhancing warehouse performance. The results show that this application has improved the order-picking process, minimized congestion, and increased operational efficiency. Keywords: Route optimization, order picking, A* algorithm. 1. Đặt vấn đề Với sự phát triển nhanh chóng của ngành logistics và thương mại điện tử, yêu cầu về hiệu quả và tốc độ trong quản lý kho hàng ngày càng trở nên quan trọng [1]. Tại Việt Nam, các doanh nghiệp logistics đang đối diện với nhiều thách thức lớn trong việc nâng cao hiệu suất hoạt động kho hàng nhằm đáp ứng nhu cầu ngày càng tăng của thị trường. Hiện tại, hiệu quả hoạt động của các kho hàng vẫn còn nhiều hạn chế, chủ yếu do trình độ quản lý chưa cao và thiếu thông tin về các biện pháp hỗ trợ nâng cao hiệu quả kho hàng [2]. Một trong những vấn đề nan giải trong quản lý kho hàng là tối ưu hóa tuyến đường nhặt hàng, một yếu tố quan trọng ảnh hưởng trực tiếp đến thời gian xử lý đơn hàng, chi phí vận hành và mức độ hài lòng của khách hàng [3]. Trong hoạt động khai thác kho hàng, việc nhặt hàng là một quy trình quan trọng, chiếm phần lớn trong tổng chi phí vận hành kho [4]. Do đó, hoạt động này đòi hỏi sự tối ưu hóa cao để đảm bảo hiệu quả và tiết kiệm chi phí. Tuy nhiên, việc xác định tuyến đường nhặt hàng tối ưu trong một không gian kho hàng lớn và phức tạp là một bài toán không hề đơn giản. Nghiên cứu này nhằm tìm ra giải pháp tối ưu tuyến đường nhặt hàng trong kho thông qua việc ứng dụng thuật toán A*. Từ đó giúp giảm thiểu thời gian và chi phí cho hoạt động nhặt hàng, đồng thời nâng cao hiệu suất hoạt động khai thác kho. 2. Tổng quan nghiên cứu Thuật toán A* là một trong những thuật toán tìm kiếm tối ưu được ứng dụng rộng rãi trong nhiều lĩnh vực nhờ khả năng tìm ra đường đi ngắn nhất với chi phí thấp nhất và sử dụng bộ nhớ hiệu quả hơn so với các thuật toán như BFS và DFS. Đặc điểm nổi bật này đã giúp thuật toán A* được triển khai thành công trong nhiều môi trường và thiết bị khác nhau, từ robot kho hàng đến các thiết bị tự vận hành trong không gian làm việc lớn. Trong bối cảnh tối ưu hóa tuyến đường nhặt hàng, thuật toán A* đã được áp dụng để quy hoạch đường đi cho robot trong kho hàng. Nghiên cứu của Duchoň và cộng sự đã đề cập đến việc lập kế
320 HỘI THẢO KHOA HỌC QUỐC GIA VỀ LOGISTICS VÀ QUẢN LÝ CHUỖI CUNG ỨNG VIỆT NAM LẦN THỨ 4 (CLSCM-2024) hoạch đường đi cho robot di động dựa trên bản đồ lưới, với các cải tiến nhằm tối ưu hóa thời gian tính toán và quãng đường di chuyển. Điều này đặc biệt hữu ích trong các môi trường kho hàng phức tạp, nơi việc tối ưu hóa quãng đường di chuyển có thể dẫn đến cải thiện đáng kể về hiệu suất hoạt động [5]. Ngoài ra, nghiên cứu của Erke và cộng sự đã khắc phục các hạn chế của thuật toán A* truyền thống, nhằm nâng cao khả năng tránh chướng ngại vật và giảm thời gian tính toán cho các phương tiện tự vận hành trên đường bộ [6]. Những cải tiến này có thể được áp dụng trực tiếp vào việc tối ưu hóa tuyến đường nhặt hàng trong kho, nơi các yếu tố như chướng ngại vật và yêu cầu về hiệu suất tính toán là rất quan trọng. Ngoài ra, thuật toán A* hình học cũng được ứng dụng thành công trong nghiên cứu của nhóm tác giả Gang Tang đối với xe tự hành AGV. Nghiên cứu này đã giải quyết các vấn đề phát sinh trong quá trình di chuyển như yêu cầu về khoảng cách, góc quay, và khả năng di chuyển trên đường chéo. Kết quả thử nghiệm cho thấy thuật toán A* hình học đã giúp các xe AGV giảm 25% góc quay và 25,5% tổng quãng đường di chuyển so với bảy thuật toán khác [7]. Cuối cùng, nghiên cứu của nhóm Martins đã cải tiến thuật toán A*, giúp giảm hơn 90% thời gian xử lý thuật toán và giảm 83,45% số lượng điểm đến ngẫu nhiên trong hoạt động lập kế hoạch tuyến đường cho robot di động trong không gian làm việc lớn [8]. Những cải tiến này có thể được áp dụng để tăng tốc quá trình tối ưu hóa tuyến đường nhặt hàng trong kho hàng, giúp nâng cao hiệu suất và giảm thiểu chi phí vận hành. 3. Ứng dụng thuật toán A* nhằm tối ưu tuyến đường nhặt hàng tại kho VDC Duyên hải Thuật toán A* là một thuật toán tìm kiếm heuristic được sử dụng để tìm đường đi ngắn nhất trong một đồ thị. Để áp dụng thuật toán này cho việc tối ưu tuyến đường nhặt hàng trong kho, hàm mục tiêu (hàm chi phí) và hàm điều kiện (hàm heuristic) cần được xác định rõ . Tuy nhiên, các xe nâng có thể bị trùng lặp lộ trình, dẫn đến việc phải chờ đợi trong quá trình lấy hàng. Do đó, thuật toán cần được phát triển để giảm thiểu tình trạng tắc nghẽn trong hoạt động khai thác kho. 3.1. Thiết lập bài toán Thuật toán A* (A-star) là một thuật toán tìm kiếm đường đi ngắn nhất rất phổ biến, sử dụng trong các bài toán định tuyến, lập kế hoạch di chuyển. A* hoạt động trên cơ sở lý thuyết đồ thị, trong đó mỗi điểm trên bản đồ hoặc lưới được biểu diễn như một nút (node), và các cạnh (edges) giữa các nút biểu diễn con đường giữa các điểm đó. Mục tiêu là tìm đường đi ngắn nhất từ nút bắt đầu (start) đến nút đích (goal), thông qua việc đánh giá chi phí di chuyển giữa các nút. Do đó, kho hàng thể được mô hình hóa như một lưới ô vuông và hàm mục tiêu được xác định như sau: - Điểm bắt đầu: Vị trí hiện tại của nhân viên nhặt hàng. - Điểm đích: Vị trí của các mặt hàng cần nhặt. Hàm mục tiêu: Min [f(x)=g(x)+h(x)] Trong đó: f(x) là tổng khoảng cách cần phải di chuyển để lấy tất cả mặt hàng. g(x) là tổng khoảng cách đã di chuyển từ điểm bắt đầu đến vị trí hiện tại x. h(x) là khoảng cách Manhattan được tính theo công thức sau: h(x)=∣xcurrent−xgoal∣+∣ycurrent−ygoal∣. Bước 1: Khởi tạo hệ thống • Dữ liệu đầu vào: Bản đồ kho hàng, bao gồm các vị trí kệ hàng, lối đi, điểm bắt đầu và điểm kết thúc cho mỗi xe nâng. • Thiết lập: Cấu hình ban đầu cho từng xe nâng, bao gồm vị trí hiện tại và vị trí hàng hóa cần nhặt. Bước 2: Lựa chọn vị trí và khởi động quá trình tìm kiếm • Lựa chọn vị trí hàng hóa cần nhặt: Mỗi xe nâng sẽ thực hiện thao tác lựa chọn vị trí cần đi nhặt hàng trên ứng dụng di động. • Ưu tiên xe chọn trước: Xe nâng nào chọn vị trí trước sẽ có quyền ưu tiên tìm đường trước. Bước 3: Áp dụng thuật toán A* cho xe đầu tiên • Thiết lập hàm chi phí: Tính toán hàm chi phí cho xe đầu tiên bằng cách sử dụng thuật toán A*, nhằm tìm ra đường đi ngắn nhất từ vị trí hiện tại đến vị trí hàng hóa cần nhặt. • Đánh dấu đường đi: Sau khi xác định được đường đi ngắn nhất, đánh dấu lộ trình này để tránh các xe khác trùng lặp. Bước 4: Áp dụng thuật toán A* cho các xe còn lại • Cập nhật bản đồ: Đối với mỗi xe tiếp theo, cập nhật bản đồ kho hàng để loại bỏ hoặc giảm trọng số các đoạn đường đã được xe trước đó sử dụng. • Tìm đường tối ưu: Áp dụng lại thuật toán A* để tìm ra đường đi tối ưu khác, dựa trên cơ sở tránh trùng lặp với lộ trình của các xe trước. • Lặp lại: Thực hiện quá trình này cho tất cả các xe nâng, đảm bảo không có hai xe nào trùng lộ trình. Bước 5: Giám sát và điều chỉnh • Giám sát thời gian thực: Hiển thị lộ trình của tất cả các xe trên màn hình máy tính để người quản lý kho