Bài toán người bán hàng
Tìm kiếm lời giải > Ứng dụng

Người ta có thể hỏi, tuy nhiên, cho dù vấn đề để nhận được tất cả sự chú ý của nó có. Ngoài việc là một "polytope" của một vấn đề tối ưu hóa tổ hợp khó khăn từ một phức tạp điểm lý thuyết của xem, có những trường hợp quan trọng của các vấn đề thực tế có thể được xây dựng như các vấn đề TSP và nhiều vấn đề khác là những khái quát của vấn đề này. Bên cạnh việc khoan mạch in bảng mô tả ở trên, vấn đề có cấu trúc TSP xảy ra trong phân tích cấu trúc của các tinh thể, (Bland và Shallcross, 1987), các đại tu động cơ tuốc bin khí (Pante, Lowe và Chandrasekaran, 1987), trong xử lý vật liệu trong một nhà kho (Ratliff và Rosenthal, 1981), trong việc cắt giảm các vấn đề chứng khoán, (Garfinkel, 1977), các phân nhóm của các mảng dữ liệu, (Lenstra và Rinooy Kạn, 1975), trình tự các công việc trên một máy tính duy nhất (và Gilmore Gomory, 1964) và phân công các tuyến đường cho máy bay của một hạm đội quy định (Boland, Jones, và Nemhauser, 1994). Biến thể có liên quan về vấn đề nhân viên bán hàng đi du lịch bao gồm các nguồn tài nguyên hạn chế đi du lịch vấn đề nhân viên bán hàng trong đó có các ứng dụng trong lập kế hoạch với thời hạn tổng hợp (Pekny và Miller, 1990). Nghiên cứu này cũng cho thấy giải thưởng thu thập đi vấn đề nhân viên bán hàng (Balas, 1989) và các vấn đề Orienteering (Golden, Levy và Vohra, 1987) là trường hợp đặc biệt của tài nguyên hạn chế TSP. Quan trọng nhất là vấn đề nhân viên bán hàng đi du lịch thường thể hiện như một bài toán con trong nhiều vấn đề tổ hợp phức tạp, là nổi tiếng và quan trọng nhất trong số đó là vấn đề định tuyến xe, có nghĩa là, vấn đề xác định cho một đội xe mà khách hàng sẽ được phục vụ bởi mỗi chiếc xe và theo thứ tự mỗi chiếc xe nên đến các khách hàng được giao. Đối với các cuộc điều tra có liên quan, xem Christofides (1985) và Fisher (1987).
Thuật toán tối ưu hóa đã được áp dụng cho nhiều vấn đề tối ưu hóa tổ hợp khác nhau, từ phân bậc hai với Proteingấp hoặc định tuyến xe (Vehicle routing problem) và rất nhiều phương pháp có nguồn gốc đã được thích nghi với các vấn đề năng động trong thực tế các biến ngẫu nhiên, các vấn đề ngẫu nhiên, đa mục tiêu và triển khai song song. Nó cũng đã được sử dụng để sản xuất các giải pháp gần tối ưu cho vấn đề nhân viên bán hàng đi du lịch. Họ có lợi thế hơn mô phỏng luyện kim (Simulated annealing) và thuật toán di truyền (Genetic algorithm) của phương pháp tiếp cận vấn đề tương tự khi đồ thị có thể thay đổi tự động; thuật toán đàn kiến có thể chạy liên tục và thích ứng với những thay đổi trong thời gian thực. Đây là quan tâm trong mạng định tuyến (Network routing) và các hệ thống giao thông đô thị.
Các thuật toán ACO đầu tiên được gọi là hệ thống Ant  và nó nhằm mục đích để giải quyết vấn đề nhân viên bán hàng đi du lịch, trong đó mục đích là để tìm ngắn chuyến đi vòng quanh để liên kết một loạt các thành phố. Các thuật toán chung là tương đối đơn giản và dựa trên một tập hợp các kiến, mỗi người làm của vòng các chuyến đi có thể cùng các thành phố. Ở mỗi giai đoạn, các kiến lựa chọn để di chuyển từ một thành phố khác theo một số quy tắc:
1. Nó phải đến mỗi thành phố đúng một lần.
2. Một thành phố xa xôi có ít cơ hội được lựa chọn (khả năng hiển thị.
3. Cường độ cao hơn đường mòn pheromone đặt ra trên một cạnh giữa hai thành phố, lớn hơn xác suất mà cạnh đó sẽ được chọn.
4. Đã hoàn thành cuộc hành trình của nó, là kiến ​​gia gửi pheromone hơn trên tất cả các cạnh nó đi qua, nếu cuộc hành trình ngắn.
5. Sau mỗi lần lặp, những con đường mòn các kích thích tố bay hơi.