GIẢI THUẬT TÌM KIẾM CỤC BỘ GIẢI BÀI TOÁN NGƯỜI DU LỊCH

Abstract

Bài toán người du lịch là một bài toán tối ưu hóa tổ hợp: Tìm hành trình ngắn nhất cho người du lịch, đi qua n thành phố khác nhau, mỗi thành phố đúng một lần và quay về nơi xuất phát. Bài toán này thuộc lớp NP-khó, được nghiên cứu chuyên sâu trong lĩnh vực tối ưu hóa và lý thuyết khoa học máy tính. Hiện nay chưa có giải thuật chính xác nào để giải bà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 tìm kiếm cục bộ mới để 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.