NGHIÊN CỨU KẾT HỢP THUẬT TOÁN GA VÀ THUẬT TOÁN K-MEANS ĐỂ GIẢI BÀI TOÁN ĐỊNH TUYẾN XE

Tóm tắt

Mục tiêu chính của nghiên cứu này là tìm ra giải pháp cho vấn đề định tuyến xe bằng cách sử dụng các thuật toán di truyền kết hợp với thuật toán phân cụm K-Means. Bài toán định tuyến xe (Vehicle Routing Problem -VRP) là một bài toán tối ưu hóa tổ hợp phức tạp thuộc lớp NP-đầy đủ (nondeterministic polynomial -complete). Giải bài toán định tuyến xe là giải bài toán tối ưu hoá tổ hợp nhằm tìm ra lộ trình tối ưu cho một đội xe phân phối hàng hoá từ kho đến nhiều địa điểm khách hàng, sao cho chi phí di chuyển là thấp nhất, đồng thời tuân thủ các ràng buộc về thời gian và sức chứa của xe. Bài báo nghiên cứu thuật toán di truyền và kỹ thuật phân cụm K-Means để tìm ra giải pháp đúng hoặc gần đúng đến các vấn đề tối ưu hóa và tìm kiếm để giải bài toán định tuyến xe.