Một Thuật Toán Heuristic Hiệu Quả Cho Vấn Đề Người Bán Hàng Du Lịch

Bài báo này thảo luận về một quy trình heuristic rất hiệu quả để tạo ra các giải pháp tối ưu và gần tối ưu cho vấn đề người bán hàng du lịch đối xứng. Quy trình này dựa trên một phương pháp tổng quát cho các thuật toán heuristic mà được cho là có tính ứng dụng rộng rãi trong các vấn đề tối ưu kết hợp. Quy trình này tạo ra các giải pháp tối ưu cho tất cả các vấn đề đã được thử nghiệm, bao gồm cả các bài toán "cổ điển" được đề cập trong tài liệu, cũng như các bài toán thử nghiệm được sinh ngẫu nhiên, lên đến 110 thành phố. Thời gian chạy tăng trưởng khoảng theo quy luật n²; về mặt tuyệt đối, một bài toán điển hình với 100 thành phố yêu cầu chưa đến 25 giây cho một trường hợp (GE635), và khoảng ba phút để đạt được giải pháp tối ưu với độ tin cậy trên 95 phần trăm.