Bài viết Giải thuật meta-heuristic giải bài toán người du lịch đề xuất một giải thuật meta-heuristic sử dụng ý tưởng tìm kiếm địa phương để giải bài toán người du lịch. Giải thuật đã được cài đặt, thử nghiệm trên bộ dữ liệu chuẩn lấy từ TSPLIB và thu được những kết quả khá tốt. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 12 73 .2013 Quyển 2 GIẢI THUẬT META-HEURISTIC GIẢI BÀI TOÁN NGƯỜI DU LỊCH META-HEURISTIC ALGORITHM FOR SOLVING TRAVELLING SALESMAN PROBLEM Võ Khánh Trung Đặng Đại Thọ Trường Đại học Bách khoa Hà Nội Trường Cao đẳng Công nghệ Thông tin Email trungvokhanh@ Đại học Đà Nẵng Email TÓM TẮT Bài toán người du lịch là một bài toán NP-khó thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù học hoặc lý thuyết khoa học máy tính. Bài toán được phát biểu như sau cho trước một danh sách các thành phố và khoảng cách giữa chúng tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần. Hiện nay chưa có giải thuật chính xác nào để giải quyết bài toán này trong trường hợp tổng quát. Vì vậy các giải thuật gần đúng đặc biệt được quan tâm. Trong bài báo này chúng tôi đề xuất một giải thuật meta-heuristic sử dụng ý tưởng tìm kiếm địa phương để giải bài toán người du lịch. Giải thuật đã được cài đặt thử nghiệm trên bộ dữ liệu chuẩn lấy từ TSPLIB và thu được những kết quả khá tốt. Từ khóa bài toán người du lịch NP-khó giải thuật meta-heuristic tìm kiếm cục bộ tối ưu hóa tổ hợp ABSTRACT The travelling salesman problem TSP is an NP-hard problem in combinatorial optimization important in operations research and theoretical computer science. It asks the following question given a list of cities and the distances between each pair of cities what is the shortest possible route that visits each city exactly once and returns to the origin city Hower today there are not exact algorithms to solve it in general case. Therefore heuristic and approximation algorithms are especially interested. This paper proposes a new meta-heuristic algorithm based on local search for solving traveling salesman problem. This algorithm has been installed tested on standard data sets taken from TSPLIB and obtained with quite good results. Key words travelling salesman problem TSP NP-hard problem meta-heuristic algorithm .
