PHƯƠNG PHÁP MỚI GIẢI BÀI TOÁN NGƯỜI BÁN HÀNG SỬ DỤNG THUẬT TOÁN RUNNER – ROOT

Tóm tắt

Bài toán người bán hàng (Travelling Salesman Problem - TSP) là bài toán tìm đường đi ngắn nhất giữa nhiều thành phố cho người bán hàng nhằm tiết kiệm thời gian và chi phí. Đây là bài toán tối ưu rời rạc phức tạp, đòi hỏi phải có các phương pháp giải hiệu quả. Bài viết trình bày một phương pháp mới dựa trên thuật toán Runner - Root (RRA) để tìm đường đi ngắn nhất cho TSP. Trong đó, RRA là thuật toán được phát triển dựa trên ý tưởng về sự nhân giống của các loại thực vật bò lan. Hiệu quả của RRA cho bài toán TSP được kiểm chứng trên TSP 14 thành phố. Dựa trên kết quả tính toán cho thấy, phương pháp đề xuất RRA là một trong những công cụ đáng được xem xét cho bài toán TSP