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. | TẠP CHÍ KHOA HỌC ĐẠI HỌC VĂN LANG Nguyễn Thị Quyên 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 A NEW METHOD FOR SOLVING TRAVELING SALESMAN PROBLEM USING RUNNER-ROOT ALGORITHM NGUYỄN THỊ QUYÊN 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. Từ khóa thuật toán runner RRA root bài toán người bán hàng TSP đường đi ngắn nhất. ABSTRACT The traveling salesman problem TSP is the problem of finding the shortest route between many cities for sellers to save time and costs. This is a complex discrete optimization problem that requires effective solutions. The article presents a new method based on the runner- root algorithm RRA to find the shortest route to the TSP. In which RRA is an algorithm developed based on the idea of propagation of creeping plants. The effectiveness of RRA for the TSP is verified on the TSP of 14 cities. The calculation results show that the proposed RRA method is one of the tools worth considering for the TSP. Key words runner-root algorithm traveling salesman problem shortest route. 1. ĐẶT VẤN ĐỀ biên 14 phương pháp Lagrangian 7 và các Bài toán TSP là bài toán tối ưu nổi tiếng phương pháp dựa trên các thuật toán tối ưu như nhằm tìm đường đi ngắn nhất giữa các thành giải thuật di truyền 3 tối ưu bầy đàn Particle phố cho người bán hàng bao gồm thành phố Swarm Optimization - PSO 16 tối ưu đàn bắt đầu
