Bài toán của người bán hàng

Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) là một vấn đề NP-khó trong tối ưu hóa tổ hợp và lý thuyết khoa học máy tính. Bài toán yêu cầu tìm chu trình ngắn nhất để thăm tất cả các thành phố một lần và trở lại thành phố xuất phát.

Được đề xuất lần đầu vào năm 1930, bài toán này là một trong những vấn đề được nghiên cứu nhiều nhất trong tối ưu hóa. Nó thường dùng để đánh giá các phương pháp tối ưu hóa. Mặc dù rất khó giải quyết trong tổng quát, đã có nhiều phương pháp chính xác và heuristic để xử lý các bài toán với hàng chục nghìn thành phố.

Ngay cả khi ở dạng đơn giản nhất, bài toán TSP có nhiều ứng dụng thực tiễn trong lập kế hoạch, logistics và thiết kế vi mạch.

Trong lý thuyết độ phức tạp tính toán, phiên bản quyết định của bài toán TSP (cho độ dài L, xác định xem có chu trình đi qua mỗi đỉnh đúng một lần và có độ dài nhỏ hơn L hay không) thuộc lớp NP-đầy đủ. Điều này cho thấy thời gian xấu nhất của bất kỳ thuật toán nào cho TSP có khả năng tăng theo cấp số nhân với số lượng thành phố.

Bài toán TSP, ngay cả ở dạng đơn giản, có nhiều ứng dụng trong lập kế hoạch, logistic và sản xuất vi mạch. Khi biến thể của nó xuất hiện trong các lĩnh vực khác như phân tích gen, khái niệm thành phố có thể là khách hàng, điểm hàn, mảnh DNA, và khoảng cách có thể là thời gian, chi phí hoặc sự so sánh gen. Trong nhiều trường hợp, các hạn chế về tài nguyên và thời gian làm cho bài toán trở nên phức tạp hơn.

Trong lý thuyết độ phức tạp tính toán, bài toán quyết định của TSP thuộc lớp NP-đầy đủ. Điều này có nghĩa là không có thuật toán hiệu quả nào cho TSP. Thời gian chạy tồi tệ nhất của bất kỳ thuật toán nào tăng theo hàm mũ với số lượng thành phố, dẫn đến việc ngay cả các bài toán với vài trăm thành phố cũng có thể mất hàng năm CPU để giải quyết chính xác.

Lịch sử

Nguồn gốc của bài toán người bán hàng vẫn chưa được làm sáng tỏ. Một cuốn sách cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán và đưa ra ví dụ về chu trình tại Đức và Thụy Sĩ, nhưng không có nội dung toán học.

Bài toán người bán hàng được đưa ra vào thế kỉ 19 bởi hai nhà toán học William Rowan Hamilton từ Ireland và Thomas Kirkman từ Anh. Trò chơi Icosa của Hamilton là một trò chơi giải trí xoay quanh việc tìm chu trình Hamilton. Vấn đề tổng quát của TSP lần đầu tiên được nghiên cứu bởi các nhà toán học tại Vienna và Harvard vào những năm 1930, đặc biệt là Karl Menger, người đã định nghĩa bài toán, xem xét thuật toán hiển nhiên và phát hiện ra rằng thuật toán láng giềng gần nhất không phải là tối ưu.

Tên bài toán người bán hàng được gán bởi Hassler Whitney tại Đại học Princeton ngay sau đó.

Vào những năm 1950 và 1960, bài toán trở nên nổi bật trong cộng đồng nghiên cứu ở châu Âu và Mỹ. George Dantzig, Delbert Ray Fulkerson và Selmer M. Johnson từ công ty RAND ở Santa Monica đã có những đóng góp quan trọng, chuyển bài toán thành dạng quy hoạch nguyên và phát triển phương pháp mặt phẳng cắt để tìm giải pháp. Họ đã giải quyết tối ưu cho một trường hợp với 49 thành phố bằng cách xây dựng và chứng minh rằng không có chu trình nào ngắn hơn. Trong những thập kỷ tiếp theo, bài toán được nghiên cứu bởi nhiều nhà khoa học trong các lĩnh vực toán học, khoa học máy tính, hóa học, vật lý và các lĩnh vực khác.

Năm 1972, Richard M. Karp chứng minh bài toán chu trình Hamilton là NP-đầy đủ, đồng nghĩa với việc bài toán TSP cũng thuộc lớp NP-đầy đủ, giải thích sự khó khăn trong việc tìm chu trình ngắn nhất.

Cuối thập niên 1970 và 1980 chứng kiến một bước tiến lớn khi Grötschel, Padberg, Rinaldi và các cộng sự giải quyết thành công các trường hợp với tới 2392 thành phố, sử dụng phương pháp mặt phẳng cắt và nhánh cận.

Vào thập niên 1990, Applegate, Bixby, Chvátal, và Cook phát triển chương trình Concorde, giải quyết nhiều bài toán với kích thước kỷ lục hiện nay. Gerhard Reinelt công bố bộ dữ liệu TSPLIB vào năm 1991, chứa các trường hợp với độ khó khác nhau, được sử dụng rộng rãi để so sánh kết quả nghiên cứu. Năm 2005, Cook và nhóm của ông đã giải bài toán với 33810 thành phố, một bài toán thiết kế vi mạch, là trường hợp lớn nhất trong TSPLIB. Trong nhiều bài toán khác với hàng triệu thành phố, đã tìm được giải pháp với sai số không vượt quá 1% so với tối ưu.

Phát biểu

Một người giao hàng cần đi giao hàng tại n thành phố, bắt đầu từ một thành phố, thăm từng thành phố một lần và trở lại điểm xuất phát. Mỗi thành phố chỉ được thăm một lần, và khoảng cách giữa các thành phố đã được biết trước. Tìm chu trình khép kín sao cho tổng chiều dài các đoạn đường là ngắn nhất.

Dưới dạng đồ thị

Bài toán người bán hàng có thể được diễn tả dưới dạng một đồ thị vô hướng có trọng số, với mỗi thành phố là một đỉnh và các con đường giữa các thành phố là các cạnh. Khoảng cách giữa hai thành phố tương ứng với chiều dài của cạnh. Vấn đề là tìm chu trình ngắn nhất bắt đầu và kết thúc tại cùng một đỉnh, thăm tất cả các đỉnh khác đúng một lần. Thông thường, mô hình này là một đồ thị đầy đủ (mỗi cặp đỉnh đều có cạnh). Nếu không có đường nối hai thành phố, có thể thêm một cạnh với độ dài rất lớn mà không làm ảnh hưởng đến giải pháp tối ưu cuối cùng.

Đối xứng và bất đối xứng

Trong bài toán TSP đối xứng, khoảng cách giữa hai thành phố không thay đổi dù đi theo chiều nào, dẫn đến đồ thị vô hướng. Điều này giảm một nửa số khả năng giải quyết. Ngược lại, trong bài toán TSP bất đối xứng, đường đi giữa hai thành phố có thể có độ dài khác nhau theo mỗi chiều, tạo thành đồ thị có hướng. Ví dụ về sự bất đối xứng bao gồm tai nạn giao thông, đường một chiều, hoặc phí hàng không khác nhau giữa các thành phố.

Tìm kiếm lời giải

Như nhiều bài toán NP-khó khác, bài toán người bán hàng có thể được tiếp cận theo nhiều phương pháp khác nhau.

• Thiết kế thuật toán tìm kiếm tối ưu (hiệu quả nhất cho các bài toán nhỏ).
• Thiết kế thuật toán heuristic để tìm những giải pháp tốt nhưng không hoàn toàn tối ưu.
• Thiết kế thuật toán xấp xỉ để tìm các giải pháp gần nhất với giải pháp tối ưu.
• Xử lý các trường hợp đặc biệt.

Ví dụ minh họa

Áp dụng thuật toán láng giềng gần nhất (nearest neighbour algorithm)
Các bước thực hiện như sau:

• Bước 1: Chọn một đỉnh khởi đầu V.
• Bước 2: Từ đỉnh hiện tại, chọn cạnh có chiều dài ngắn nhất đến các đỉnh chưa được thăm. Đánh dấu đỉnh vừa chọn là đã thăm.
• Bước 3: Nếu còn đỉnh chưa thăm, lặp lại bước 2.
• Bước 4: Quay trở lại đỉnh V.

Bài toán gồm năm thành phố với khoảng cách giữa các thành phố tính bằng km. Áp dụng thuật toán láng giềng gần nhất, bắt đầu từ mỗi đỉnh để tìm lộ trình tốt nhất cho người bán hàng, với cửa hàng đặt tại A và yêu cầu đi qua tất cả các thành phố còn lại.

Bắt đầu từ đỉnh A

• Đỉnh gần nhất từ A là C, với khoảng cách AC = 8
• Từ C, đỉnh chưa thăm gần nhất là E, CE = 4
• Từ E, đỉnh chưa thăm gần nhất là B, EB = 15
• Từ B, đỉnh chưa thăm gần nhất là D, BD = 10
• Đã thăm hết các đỉnh, quay lại A, DA = 14

Tổng chi phí cho lộ trình ACEBDA là 8 + 4 + 15 + 10 + 14 = 51

Tiến hành lặp lại từ các đỉnh khác:

Có ba lộ trình với chiều dài 45 km giống nhau. Đối với nhân viên bán hàng tại A, lộ trình tốt nhất được tìm thấy bởi thuật toán láng giềng gần nhất là ABDCEA với chiều dài 45 km

Công thức

Công thức: Để giải quyết bài toán TSP lớn, bước đầu tiên là tìm một công thức toán học phù hợp. Đối với bài toán nhân viên bán hàng đi du lịch, cấu trúc toán học là một đồ thị, trong đó mỗi thành phố được biểu thị bằng một điểm (hoặc nút), và các cạnh nối giữa các điểm (gọi là vòng cung hoặc cạnh). Mỗi cạnh liên kết với một khoảng cách (hoặc chi phí). Nếu nhân viên bán hàng có thể đi trực tiếp từ mỗi thành phố đến tất cả các thành phố khác, đồ thị được coi là hoàn chỉnh. Một chuyến đi vòng quanh các thành phố tương ứng với một tập hợp con của các cạnh, gọi là tour du lịch hoặc chu trình Hamilton trong lý thuyết đồ thị. Chiều dài của tour du lịch là tổng độ dài của các cạnh trong chuyến đi.

Tùy thuộc vào việc đồ thị có chỉ đạo hay không, bài toán có thể có sự đối xứng hoặc không đối xứng. Đối với bài toán TSP không đối xứng trên m thành phố, một biến thể nổi bật là không có tính đối xứng.

Do yêu cầu rằng mỗi nút của đồ thị phải có đúng một cạnh đi vào và một cạnh đi ra, bài toán trở thành một bài toán chuyển nhượng cổ điển. Những khó khăn này không đủ vì công thức sẽ cho phép các 'subtours', tức là các vòng phân chia. Do đó, một mô hình phù hợp cho bài toán nhân viên bán hàng không đối xứng phải loại bỏ các subtours bằng cách bổ sung các hạn chế 'loại bỏ subtour'. Vấn đề trở thành

nơi K là bất kỳ tập hợp con thích hợp khác rỗng trong các thành phố 1,..., m. Chi phí c_ij có thể khác với chi phí c_ji. Lưu ý rằng có m (m-1) không đối xứng trong công thức này.

Khi giải quyết bài toán nhân viên bán hàng với đồ thị đối xứng, ta nhận thấy hướng đi qua không quan trọng, vì vậy c_ij = c_ji. Trong trường hợp này, đồ thị chỉ có một vòng cung (vô hướng) giữa hai nút. Biến quyết định x_j thuộc {0,1} cho biết nút j có chạy qua tất cả các cạnh E của đồ thị vô hướng hay không, với c_j là chi phí của cạnh đó. Để tìm một tour du lịch, ta cần chọn một tập hợp con của các cạnh sao cho tất cả các nút được nối bởi chính xác hai cạnh trong tập hợp. Vấn đề trở thành bài toán 2 khớp trong đồ thị G với m(m-1)/2 không đối xứng, tức là một nửa số lượng các cạnh trước đó. Giống như trong trường hợp bất đối xứng, cần loại bỏ các subtours qua hạn chế loại bỏ subtour. Vấn đề cuối cùng được xây dựng như:

Các thuật toán

Các thuật toán: Để giải quyết bài toán này, cần dùng phương pháp chính xác để tạo ra cả giới hạn dưới và trên cho giá trị tối ưu của bài toán. Mỗi tour du lịch đi qua tất cả các thành phố đúng một lần là một giải pháp khả thi với chi phí không thấp hơn chi phí tối thiểu. Thuật toán xây dựng các giải pháp khả thi, từ đó tạo ra giới hạn trên cho giá trị tối ưu, được gọi là công nghệ tự động. Các thuật toán này có thể cung cấp câu trả lời nhưng không đảm bảo chất lượng gần đúng của chúng so với giải pháp tối ưu. Các thuật toán heuristic cố gắng tìm giải pháp khả thi trong một lần thử, được gọi là công nghệ tự động xây dựng, trong khi các thuật toán lặp lại và cải thiện các giải pháp được gọi là công nghệ tự động cải thiện. Vì một giải pháp phụ thuộc vào điểm xuất phát ban đầu, cùng một thuật toán có thể được áp dụng từ nhiều điểm khởi đầu khác nhau. Các nghiên cứu như của Junger, Reinelt và Rinaldi (1994) đã khảo sát công nghệ tự động cải thiện ngẫu nhiên. Đối với giải pháp nhanh chóng, thuật toán heuristic được thiết kế tốt có thể tìm ra tour du lịch 'gần như tối ưu' cho nhiều bài toán TSP. Các nghiên cứu của Johnson (1990) và Junger, Reinelt và Rinaldi (1994) mô tả thuật toán cho TSP lớn (với hàng chục ngàn, thậm chí hàng triệu biến) gần tối ưu trong thời gian hợp lý. Các phương pháp như thuật toán di truyền (Potvin, 1996), mô phỏng annealing (Aarts et al., 1988), mạng nơ-ron (Potvin, 1993), và tìm kiếm kỵ (Fiechter, 1990) cũng được áp dụng. Các phân tích về chẩn đoán và xác suất của công nghệ tự động được đề cập trong các nghiên cứu của Johnson và Papadimitriou (1985), Karp và Steele (1985), và sự phát triển thực tế được báo cáo trong Golden và Stewart (1985).

Để đánh giá độ gần đúng của các ràng buộc với giá trị tối ưu, cần phải biết cả giới hạn trên và dưới. Nếu giới hạn trên và dưới trùng nhau, điều đó chứng minh rằng giải pháp là tối ưu. Nếu không, ước lượng sai số tương đối của các ràng buộc trên có thể được tính bằng cách lấy sự khác biệt giữa giới hạn trên và dưới chia cho giới hạn dưới. Vì vậy, cần cả giới hạn trên và dưới để chứng minh giải pháp tối ưu cho các vấn đề tổ hợp phức tạp hoặc để đạt được các giải pháp với đảm bảo chất lượng.

Để cải thiện các ràng buộc thấp hơn, ta có thể sử dụng thư giãn của bài toán tối ưu hóa. Thư giãn là bài toán tối ưu hóa với tập hợp giải pháp khả thi bao gồm tất cả các giải pháp của bài toán gốc, và có giá trị hàm mục tiêu nhỏ hơn hoặc bằng. Thay vì giải quyết bài toán gốc khó, ta chuyển sang bài toán dễ hơn. Các thư giãn có thể là rời rạc hoặc liên tục và được tinh chỉnh để gần gũi hơn với bài toán thực sự. Ví dụ, các thư giãn như n-đường dẫn, chuyển nhượng, 2 khớp, 1-cây, và tuyến tính đã được áp dụng cho TSP. Đối với TSP không đối xứng với 7500 thành phố, thư giãn khoán được sử dụng để giải quyết bài toán qua phương pháp chi nhánh và ràng buộc. Đối với TSP đối xứng, thư giãn 1-cây và 2 khớp là hiệu quả nhất.

Tìm kiếm bị hạn chế bởi một thư giãn nhất định, và kỹ thuật cắt máy bay đã được sử dụng để liên tục thắt chặt bài toán. Các phương pháp thành công trong TSP đều sử dụng cắt máy bay, nhưng các kỹ thuật cắt đơn cơ sở như Gomory hoặc cắt giao lộ đã không còn phổ biến do hội tụ kém.

Một trong những cắt giảm đơn giản để xác định các khía cạnh của TSP polytope là cắt giảm loại bỏ subtour. Ngoài cắt giảm subtour, các bất bình đẳng khác như cây bè lũ, con đường, xe cút kít, xe đạp, thang và vương miện cũng xác định các khía cạnh của polytope này. Lý thuyết cơ bản của các khía cạnh trong TSP đối xứng được trình bày trong Grötschel và Padberg (1985) và Junger, Reinelt và Rinaldi (1994). Các phương pháp cắt máy bay được mô tả trong Padberg và Rinaldi (1991) và Junger, Reinelt và Rinaldi (1994). Xử lý song song được trình bày trong Christof và Reinelt (1995) và Applegate, et al. (1998). Các thủ tục cắt máy bay có thể được nhúng vào cây tìm kiếm như chi nhánh và cắt giảm. Nhiều bài toán TSP lớn đã sử dụng xử lý song song để tìm giải pháp tối ưu.

Ứng dụng

Vấn đề tối ưu hóa tổ hợp, đặc biệt là TSP, không chỉ là một ví dụ về một polytope phức tạp mà còn xuất hiện trong nhiều bài toán thực tế quan trọng. Các ứng dụng của TSP bao gồm phân tích cấu trúc tinh thể (Bland và Shallcross, 1987), bảo trì động cơ tuốc bin (Pante, Lowe và Chandrasekaran, 1987), xử lý vật liệu trong kho (Ratliff và Rosenthal, 1981), tối ưu hóa cắt giảm chứng khoán (Garfinkel, 1977), phân nhóm dữ liệu (Lenstra và Rinooy Kan, 1975), lập kế hoạch công việc máy tính (Gilmore và Gomory, 1964), và phân công tuyến đường cho máy bay (Boland, Jones, và Nemhauser, 1994). Biến thể của TSP liên quan đến nguồn tài nguyên hạn chế và ứng dụng trong lập kế hoạch tổng hợp (Pekny và Miller, 1990) cũng được nghiên cứu, cùng với các vấn đề thưởng thu thập (Balas, 1989) và Orienteering (Golden, Levy và Vohra, 1987). TSP thường là một phần của các bài toán tổ hợp phức tạp như định tuyến xe, nơi cần xác định tuyến đường tối ưu cho đội xe phục vụ khách hàng. Xem thêm Christofides (1985) và Fisher (1987) để biết thêm chi tiết.

Các thuật toán tối ưu hóa đã được áp dụng rộng rãi cho nhiều bài toán tổ hợp, từ phân bậc hai đến định tuyến xe và nhiều vấn đề khác. Những phương pháp này đã được điều chỉnh để giải quyết các bài toán năng động với biến ngẫu nhiên, đa mục tiêu và xử lý song song. Chúng cũng được sử dụng để tìm giải pháp gần tối ưu cho TSP. So với các phương pháp như mô phỏng luyện kim (Simulated annealing) và thuật toán di truyền (Genetic algorithm), thuật toán đàn kiến (Ant Colony Optimization) có ưu thế trong việc xử lý các đồ thị thay đổi liên tục và thích ứng với sự thay đổi theo thời gian thực, đặc biệt trong mạng định tuyến và giao thông đô thị.

Các thuật toán ACO đầu tiên, được gọi là hệ thống Ant, được thiết kế để giải quyết vấn đề TSP bằng cách tìm chuyến đi ngắn nhất liên kết nhiều thành phố. Thuật toán này dựa trên hành vi của kiến, với mỗi con kiến tạo ra một vòng chuyến đi qua các thành phố. Ở mỗi giai đoạn, các con kiến lựa chọn thành phố tiếp theo theo các quy tắc cụ thể.

1. Mỗi thành phố phải được thăm đúng một lần.

2. Thành phố xa xôi có ít khả năng được lựa chọn hơn.

3. Độ mạnh của pheromone trên một cạnh giữa hai thành phố càng lớn, xác suất chọn cạnh đó càng cao.

4. Khi hoàn thành hành trình, kiến gửi thêm pheromone lên tất cả các cạnh nó đi qua nếu hành trình đó ngắn.

5. Sau mỗi vòng lặp, lượng pheromone trên các đường mòn sẽ giảm dần do bay hơi.

Độ phức tạp tính toán

Phiên bản quyết định của bài toán người bán hàng thuộc loại NP-đầy đủ. Ngay cả khi khoảng cách giữa các thành phố là khoảng cách Euclide, bài toán vẫn là NP-khó.

- Với n thành phố, số lượng đường đi là: 1/2 × (n − 1)!

Trong trường hợp tổng quát, bài toán người bán hàng là NPO-đầy đủ. Khi khoảng cách thỏa mãn bất đẳng thức tam giác và đối xứng, bài toán là APX-đầy đủ và thuật toán Christofides có thể cung cấp lời giải xấp xỉ không quá 1,5 lần lời giải tối ưu.

Khi khoảng cách là bất đối xứng nhưng vẫn thỏa mãn bất đẳng thức tam giác, thuật toán tốt nhất hiện tại đạt được tỷ lệ xấp xỉ O(log n / log log n).

Các trường hợp đặc biệt

Cải thiện ngẫu nhiên

Thuật toán chuỗi Markov được sử dụng để tối ưu hóa và tìm kiếm địa phương, có thể tìm ra các tuyến đường gần tối ưu cho 700 đến 800 thành phố. TSP là tiêu chuẩn cho nhiều phương pháp tối ưu hóa tổ hợp như thuật toán di truyền, tìm kiếm Tabu, tối ưu hóa thuộc địa kiến và các phương pháp entropy chéo.

Khi các thành phố nằm trong không gian Euclide, bài toán vẫn là NP-đầy đủ. Tuy nhiên, khi số chiều của không gian là hằng số, có thuật toán cung cấp lời giải xấp xỉ với độ chính xác tùy ý. Cụ thể, với bất kỳ $\mathrm{ϵ<!--\; ϵ\; -->}>0$ và $d$ là số chiều của không gian Euclide, có thuật toán chạy trong thời gian $(\sqrt{d}/\mathrm{ϵ<!--\; ϵ\; -->}{)}^{O\left(d\right(\sqrt{d}/\mathrm{ϵ<!--\; ϵ\; -->}{)}^{d-<!--\; -\; -->1})}n+O(dn\log <!--\; \; -->n)$ và tìm ra lời giải không kém hơn $1+\mathrm{ϵ<!--\; ϵ\; -->}$ so với lời giải tối ưu.

Ghi chú

Các liên kết bên ngoài

Tiếng Anh:

• Ứng dụng demo của thuật toán di truyền giải quyết TSP và VRPTW trực tuyến Lưu trữ 2008-12-19 tại Wayback Machine
• TSPLIB Lưu trữ 2017-03-25 tại Wayback Machine
• Vấn đề người bán hàng Lưu trữ 2008-12-26 tại Wayback Machine của Georgia Tech
• Ví dụ về việc tìm giải pháp xấp xỉ cho vấn đề TSP bằng thuật toán di truyền Lưu trữ 2007-09-16 tại Wayback Machine
• Cài đặt Java của giải pháp TSP sử dụng JGAP (Java Genetic Algorithms Package) với kỹ thuật là thuật toán di truyền.
• Giải pháp cho Vấn đề người bán hàng sử dụng bản đồ Kohonen
• Mạng nơ-ron Kohonen Lưu trữ 2007-09-27 tại Wayback Machine áp dụng cho Vấn đề người bán hàng (sử dụng ba chiều).
• Hầu hết các họ TSP phát triển theo đa thức Trang web riêng tư cho thấy có một phương pháp để có được một tập hợp các tuyến đường tối ưu cho người bán hàng thuộc một họ phát triển không nhanh hơn khoảng 2In2. Tuy nhiên, ngay cả với n lớn, phương pháp này cho ra tốc độ đa thức cho hầu hết các tập hợp nút.
• VisualBots Lưu trữ 2003-12-16 tại Wayback Machine - Phần mềm miễn phí mô phỏng nhiều đại lý trong Microsoft Excel. Các chương trình mẫu bao gồm giải pháp thuật toán di truyền, ACO, và simulated annealing cho TSP.
• Chứng minh đang được thử nghiệm Lưu trữ 2007-09-28 tại Wayback Machine trên trang web riêng về thời gian tính toán đa thức trên đồ thị vô hướng 2-D.
• Các liên kết đến mã nguồn TSP Lưu trữ 2007-09-28 tại Wayback Machine
• http://www.delphiforfun.org/Programs/traveling_salesman.htm Vấn đề người bán hàng (TSP) yêu cầu tìm con đường ngắn nhất để thăm mỗi thành phố trong tập hợp cho trước và trở về điểm xuất phát.
• CONCORDE Lưu trữ 2007-09-12 tại Wayback Machine Trang chủ của CONCORDE TSP Solver, một thư viện ANSI C dành riêng cho việc giải quyết vấn đề TSP.
• [1] Lưu trữ 2009-04-10 tại Wayback Machine tham khảo