Bài toán người bán hàng

Nếu người bán hàng xuất phát từ điểm A, và nếu khoảng cách giữa hai điểm bất kì được biết thì đâu là đường đi ngắn nhất mà người bán hàng có thể thực hiện được sao cho đi hết tất cả các điểm mỗi điểm một lần để quay về lại điểm A ban đầu?

Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) 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.

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

Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều ứng dụng trong lập kế hoạch, hậu cần, cũng như 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 TSP (cho trước độ dài L, xác định xem có tồn tại hay không một chu trình đi qua mỗi đỉnh đúng một lần và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ. Do đó, có nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào cho TSP đều tăng theo cấp số nhân với số thành phố.

TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thủy của nó như lập kế hoạch, logistic, và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một bài toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm hàn trên bảng mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu diễn bởi thời gian du lịch hay giá thành, hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian thậm chí còn làm cho bài toán trở nên khó hơn.

Trong lý thuyết của độ phức tạp tính toán, phiên bản quyết định của bài toán TSP thuộc lớp NP-đầy đủ. Vì vậy không có giải thuật hiệu quả nào cho việc giải bài toán TSP. Hay nói cách khác, giống như thời gian chạy xấu nhất cho bất ký giải thuật nào cho bài toán TSP tăng theo hàm mũ với số lượng thành phố, vì vậy thậm chí nhiều trường hợp với vài trăm thành phố cũng đã mất vài năm CPU để giải một cách 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 biết rõ. Một cuốn sổ tay dành cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán này và có ví dụ cho chu trình trong nước Đức và Thụy Sĩ, nhưng không chứa bất kì nội dung toán học nào.

Bài toán người bán hàng được định nghĩa trong thế kỉ 19 bởi nhà toán học Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman. Trò chơi Icosa của Hamilton là một trò chơi giải trí dựa trên việc tìm kiếm chu trình Hamilton. Trường hợp tổng quát của TSP có thể được nghiên cứu lần đầu tiên bởi các nhà toán học ở Vienna và Harvard trong 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 nhất cho bài toán, và phát hiện ra thuật toán láng giềng gần nhất là không tối ưu.

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

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

Năm 1972, Richard M. Karp chứng minh rằng bài toán chu trình Hamilton là NP-đầy đủ, kéo theo bài toán TSP cũng là NP-đầy đủ. Đây là một lý giải toán học cho sự khó khăn trong việc tìm kiếm chu trình ngắn nhất.

Một bước tiến lớn được thực hiện cuối thập niên 1970 và 1980 khi Grötschel, Padberg, Rinaldi và cộng sự đã giải được những trường hợp lên tới 2392 thành phố, sử dụng phương pháp mặt phẳng cắt và nhánh cận.

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

Phát biểu

Có một người giao hàng cần đi giao hàng tại n thành phố. Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, và khoảng cách từ một thành phố đến các thành phố khác đã được biết trước. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.

Dưới dạng đồ thị

Bài toán người bán hàng có thể được mô hình hoá như một đồ thị vô hướng có trọng số, trong đó mỗi thành phố là một đỉnh của đồ thị còn đường đi giữa các thành phố là mỗi cạnh. Khoảng cách giữa hai thành phố là độ dài cạnh. Đây là vấn đề cực tiểu hoá với điểm đầu và điểm cuối là cùng một đỉnh sau khi thăm hết các đỉnh còn lại đúng một lần. Mô hình này thường là một đồ thị đầy đủ (giữa mỗi cặp đỉnh đều có cạnh). Nếu không có đường giữa hai thành phố thì có thể thêm một cạnh với độ dài đủ lớn vào đồ thị mà không ảnh hưởng đến kết quả tối ưu sau 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ố là không đổi dù đi theo chiều nào. Như vậy đồ thị trong bài toán này là đồ thị vô hướng. Việc đối xứng này làm giảm đi một nửa số lời giải có thể. Trong khi đó, với bài toán TSP bất đối xứng thì đường đi giữa hai thành phố có thể chỉ một chiều hoặc có độ dài khác nhau giữa mỗi chiều, tạo nên đồ thị có hướng. Các tai nạn giao thông, đường một chiều hay phí hàng không giữa các thành phố với phí điểm xuất phát và điểm đến khác nhau là những ví dụ về sự bất đối xứng.

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

Cũng như các bài toán NP-khó khác, có các hướng sau đây để tiếp cận bài toán người bán hàng.

Thiết kế thuật toán tìm kiếm lời giải tối ưu (thường hoạt động hiệu quả cho những trường hợp nhỏ).
Thiết kế thuật toán heuristic để tìm những lời giải tốt nhưng không nhất thiết tối ưu.
Thiết kế thuật toán xấp xỉ để tìm những lời giải không quá lớn so với lời giải tối ưu.
Giải quyết các trường hợp đặc biệt.

Ví dụ minh họa

Sử dụng thuật toán láng giềng gần nhất (tiếng Anh: nearest neighbour algorithm)
Các bước của thuật toán:

Bước 1: Chọn một đỉnh bắt đầu V.
Bước 2: Từ đỉnh hiện hành chọn cạnh nối có chiều dài nhỏ nhất đến các đỉnh chưa đến. Đánh dấu đã đến đỉnh vừa chọn.
Bước 3: Nếu còn đỉnh chưa đến thì quay lại bước 2.
Bước 4: Quay lại đỉnh V.

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

Bắt đầu với đỉnh A

Từ A, đỉnh gần nhất là C, chiều dài AC = 8
Từ C, đỉnh chưa viếng thăm gần nhất là E, CE = 4
Từ E, đỉnh chưa viếng thăm gần nhất là B, EB = 15
Từ B, đỉnh chưa viếng thăm gần nhất là D, BD = 10
Không còn đỉnh chưa viếng thăm, vì vậy quay về A, DA = 14

Tổng chi phí ACEBDA là 8 + 4 + 15 + 10 + 14 = 51

Lặp lại bắt đầu với những đỉnh khác:

Đỉnh bắt đầu	Đường đi	Tổng chiều dài
A	ACEBDA	51
B	BACEDB	50
C	CEABDC	45
D	DCEABD	45
E	ECABDE	50
E	ECDBAE	45

Có ba đường đi có chiều dài 45 km là giống nhau. Một nhân viên bán hàng có cửa hàng tại A, đường đi tốt nhất tìm ra bởi thuật toán láng giềng gần nhất là ABDCEA = 45 km

Công thức

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

Tùy thuộc vào có hay không sự chỉ đạo, trong đó một cạnh của đồ thị là đi qua các vấn đề, một trong những phân biệt đối xứng từ đối xứng đi vấn đề nhân viên bán hàng. Xây dựng các bất đối xứng TSP trên m thành phố, một trong những giới thiệu không-một biến

và do thực tế là tất cả các nút của đồ thị phải có đúng một cạnh chỉ tay về phía nó và một trong những chỉ đi từ nó, có được một vấn đề chuyển nhượng cổ điển. Những khó khăn này một mình là không đủ vì công thức này sẽ cho phép "subtours", có nghĩa là, nó sẽ cho phép các vòng phân chia xảy ra. Vì lý do này, một mô hình thích hợp của các vấn đề đi du lịch nhân viên bán hàng không đối xứng phải loại bỏ những subtours từ xem xét việc bổ sung "subtour loại bỏ" hạn chế. Vấn đề sau đó trở thành

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

Xây dựng các đối xứng đi vấn đề nhân viên bán hàng, người ta ghi nhận rằng hướng đi qua là không đáng kể, do đó c ij = c ji. Từ hướng không quan trọng bây giờ, người ta có thể xem xét các đồ thị, nơi chỉ có một vòng cung (vô hướng) giữa hai nút. Vì vậy, chúng tôi cho x j e { 0,1 } là biến quyết định nơi j chạy qua tất cả các cạnh E của đồ thị vô hướng và c j là chi phí đi cạnh đó. Để tìm một tour du lịch trong biểu đồ này, người ta phải chọn một tập hợp con của các cạnh như vậy mà tất cả các nút được chứa trong hai chính xác của các cạnh được lựa chọn. Như vậy, vấn đề có thể được xây dựng như một vấn đề 2 khớp trong đồ thị G v có m (m-1) / 2 không-một biến, tức là một nửa số lượng các công tác xây dựng trước đó. Như trong trường hợp bất đối xứng, subtours phải được loại bỏ thông qua hạn chế loại bỏ subtour. Vấn đề do đó có thể được xây dựng như:

Các thuật toán

Các thuật toán: phương pháp chính xác để giải quyết vấn đề như vậy đòi hỏi các thuật toán tạo ra cả một giới hạn dưới và một trên ràng buộc về giá trị nhỏ nhất thực sự của các trường hợp vấn đề. Bất kỳ tour du lịch vòng quanh chuyến đi mà đi qua mỗi thành phố đúng một lần là một giải pháp khả thi với một chi phí nhất định mà không thể nhỏ hơn so với các tour du lịch chi phí tối thiểu. Thuật toán xây dựng các giải pháp khả thi, và do đó giới hạn trên đối với các giá trị tối ưu, được gọi là công nghệ tự động. Những giải pháp chiến lược sản xuất câu trả lời nhưng không có bất kỳ đảm bảo chất lượng như thế nào xa họ có thể từ câu trả lời tối ưu. Các thuật toán heuristic mà cố gắng để tìm ra giải pháp khả thi trong một nỗ lực duy nhất được gọi là công nghệ tự động xây dựng trong khi các thuật toán đó lặp đi lặp lại thay đổi và cố gắng cải thiện một số giải pháp bắt đầu được gọi là công nghệ tự động cải thiện. Khi một giải pháp có được phụ thuộc vào điểm xuất phát ban đầu của thuật toán, cùng một thuật toán có thể được sử dụng nhiều lần từ nhiều điểm khởi đầu (ngẫu nhiên). Đối với một cuộc khảo sát tuyệt vời của công nghệ tự động cải thiện ngẫu nhiên, xem Junger, Reinelt và Rinaldi (1994)^[1]. Thông thường, nếu một trong những nhu cầu một giải pháp nhanh chóng, người ta có thể giải quyết cho một thuật toán heuristic được thiết kế tốt đã được chứng minh bằng thực nghiệm để tìm tour du lịch "gần như tối ưu" đến nhiều vấn đề TSP. Nghiên cứu của Johnson (1990)^[2], và Junger, Reinelt và Rinaldi (1994) ^[1] mô tả thuật toán tìm giải pháp cho TSPs rất lớn (vấn đề với hàng chục ngàn, thậm chí hàng triệu biến) để trong vòng 2% của tối ưu trong thời gian rất hợp lý. Đối với phương pháp tiếp cận thuật toán di truyền để TSP, xem Potvin (1996)^[3], cách tiếp cận ủ mô phỏng thấy Aarts, et al. (1988), cách tiếp cận mạng lưới thần kinh, xem Potvin (1993)^[4], và cách tiếp cận tìm kiếm kỵ, xem Fiechter (1990)^[5]. Bảo lãnh thực hiện cho chẩn đoán được đưa ra trong Johnson và Papadimitriou (1985)^[6], phân tích xác suất của công nghệ tự động sẽ được thảo luận trong Karp và Steele (1985)^[7], và sự phát triển và thử nghiệm thực tế về chẩn đoán được báo cáo trong Golden và Stewart (1985)^[8].

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

Vì vậy, làm thế nào để có được và cải thiện thấp hơn ràng buộc? Một thư giãn của một vấn đề tối ưu hóa là một vấn đề tối ưu hóa mà bộ các giải pháp khả thi đúng có chứa tất cả các giải pháp khả thi của vấn đề ban đầu và có giá trị hàm mục tiêu nhỏ hơn hoặc bằng với đúng giá trị hàm mục tiêu cho các điểm khả thi cho vấn đề ban đầu. Do đó chúng tôi thay thế các "true" vấn đề bằng một với một khu vực có tính khả thi hơn đó là khả năng giải quyết dễ dàng hơn. Thư giãn này được tiếp tục tinh chế để thắt chặt các khu vực có tính khả thi để nó đại diện cho chặt chẽ hơn vấn đề thực sự. Các kỹ thuật tiêu chuẩn để đạt được giới hạn thấp hơn trên các vấn đề TSP là sử dụng một thư giãn mà là dễ dàng hơn để giải quyết hơn vấn đề ban đầu. Những nới lỏng có thể có một trong hai bộ khả thi rời rạc hay liên tục. Một số nới lỏng đã được xem xét cho TSP. Trong số đó là thư giãn n-đường dẫn, thư giãn chuyển nhượng, thư giãn 2 phù hợp, thư giãn 1-cây, và các chương trình thư giãn tuyến tính. Để tạo ra một cách ngẫu nhiên TSPs không đối xứng, vấn đề có đến 7500 thành phố đã được giải quyết bằng cách sử dụng thư giãn khoán, trong đó cho biết thêm subtours trong một khuôn khổ chi nhánh và ràng buộc và trong đó sử dụng một phỏng đoán ranh giới trên dựa trên subtour vá, (Miller và Pekny, 1991) ^[9]. Đối với TSP đối xứng, thư giãn 1-cây và nới lỏng 2 phù hợp đã thành công nhất. Những nới lỏng đã được nhúng vào một khuôn khổ chi nhánh và cắt.

Quá trình tìm kiếm hạn chế được vi phạm bởi một thư giãn nhất định, được gọi là một máy bay cắt kỹ thuật và tất cả những thành công cho các vấn đề TSP lớn đã sử dụng máy bay để cắt liên tục thắt chặt việc xây dựng của vấn đề. Điều quan trọng cần nhấn mạnh rằng tất cả các phương pháp tính toán thành công với TSP sử dụng khía cạnh-định bất bình đẳng như cắt máy bay. Máy bay cắt chung loại của văn học lập trình số nguyên sử dụng đơn cơ sở-đại diện để có được cắt giảm, chẳng hạn như Gomory hoặc cắt giảm giao lộ, từ lâu đã bị bỏ rơi vì tính chất hội tụ nghèo.

Một trong những cắt giảm đơn giản đã được chứng minh để xác định các khía cạnh của TSP polytope cơ bản là cắt giảm loại bỏ subtour. Bên cạnh những khó khăn, bất bình đẳng lược, sự bất bình đẳng cây bè lũ, con đường, xe cút kít và xe đạp bất bình đẳng, bất bình đẳng thang và vương miện đã được hiển thị để xác định các khía cạnh của polytope này. Lý thuyết cơ bản của thế hệ khía cạnh cho việc đi lại vấn đề nhân viên bán hàng đối xứng được cung cấp trong Grötschel và Padberg (1985)^[10] và Junger, Reinelt và Rinaldi (1994)^[1]. Các mô tả thuật toán như thế nào chúng được sử dụng trong việc cắt giảm các cách tiếp cận chiếc máy bay sẽ được thảo luận trong Padberg và Rinaldi (1991)^[9] và Junger, Reinelt và Rinaldi (1994)^[1]. Triển khai thực hiện xử lý song song được trình bày trong Christof và Reinelt (1995) ^[11] và Applegate, et al. (1998)^[12]. Cắt giảm các thủ tục máy bay sau đó có thể được nhúng vào một cây tìm kiếm được gọi là chi nhánh và cắt giảm. Một số vấn đề TSP lớn nhất giải quyết đã sử dụng xử lý song song để hỗ trợ trong việc tìm kiếm tối ưu. Theo sự hiểu biết của chúng ta về cấu trúc toán học cơ bản của vấn đề TSP được cải thiện, và với sự tiến bộ liên tục trong công nghệ máy tính, có khả năng là nhiều vấn đề tối ưu hóa tổ hợp khó khăn và quan trọng sẽ được giải quyết bằng cách kết hợp cắt thủ tục thế hệ máy bay, chẩn đoán, sửa chữa biến thông qua tác động hợp lý và giảm chi phí và tìm kiếm cây.

Ứ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)^[13], các đại tu động cơ tuốc bin khí (Pante, Lowe và Chandrasekaran, 1987)^[14], trong xử lý vật liệu trong một nhà kho (Ratliff và Rosenthal, 1981)^[15], 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)^[16] và các vấn đề Orienteering (Golden, Levy và Vohra, 1987)^[14] 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 ^[17] 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.

Độ 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 là 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ố thì có: 1/2 × (n − 1)! đường đi.

+ Giả sử n = 16 =>> 1/2 * 15! = 6.54 ×10¹¹ đường đi =>> Số đường đi quá lớn.

Độ phức tạp của tính xấp xỉ

Trong trường hợp tổng quát, bài toán người bán hàng là NPO-đầy đủ. Khi các 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ể tìm lời giải xấp xỉ không quá 1,5 lần lời giải tối ưu.

Khi các khoảng cách là bất đối xứng nhưng thỏa mãn bất đẳng thức tam giác, thuật toán tốt nhất hiện nay đạt tỉ lệ xấp xỉ $O(\log n/\log \log n)$ .^[18]

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

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

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

Không gian Euclide

Khi các thành phố là các điể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 để tìm lời giải xấp xỉ với độ chính xác bất kì. Cụ thể hơn, với bất kì $\epsilon >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}}/\epsilon )^{O(d({\sqrt {d}}/\epsilon )^{d-1})}n+O(dn\log n)$ và tìm ra lời giải không quá $1+\epsilon$ lời giải tối ưu.^[19]

Ghi chú

^ ^a ^b ^c ^d M. Jünger, G. Reinelt and G. Rinaldi (1994). "The Traveling Salesman Problem," in Ball, Magnanti, Monma and Nemhauser (eds.), Handbook on Operations Research and the Management Sciences North Holland Press, 225-330.
^ D. S. Johnson (1990) "Local Optimization and the Traveling Salesman Problem," Proc. 17th Colloquium on Automata, Languages and Programming, Springer Verlag, 446-461.
^ J.V. Potvin (1996) "Genetic Algorithms for the Traveling Salesman Problem", Annals of Operations Research 63, 339-370.
^ J.V. Potvin (1993), "The Traveling Salesman Problem: A Neural Network Perspective", INFORMS Journal on Computing 5 328-348.
^ C.N. Fiechter (1990) "A Parallel Tabu Search Algorithm for Large Scale Traveling Salesman Problems" Working Paper 90/1 Department of Mathematics, École Polytechnique Fédérale de Lausanne, Switzerland.
^ D. S. Johnson and C.H. Papadimitriou (1985). "Performance Guarantees for Heuristics," in The Traveling Salesman Problem, Lawler, Lenstra, Rinooy Kan and Shmoys, eds., John Wiley, 145-180.
^ R. Karp and J.M. Steele (1985). "Probabilistic Analysis of Heuristics," in The Traveling Salesman Problem, Lawler, Lenstra, Rinnooy Kan and Shmoys, eds., John Wiley, 181-205.
^ B.L. Golden and W.R. Stewart (1985). "Empirical Analysis of Heuristics," in The Traveling Salesman Problem, Lawler, Lenstra, Rinooy Kan and Shmoys, eds., John Wiley, 207-250.
^ ^a ^b D. Miller and J. Pekny (1991). "Exact Solution of Large Asymmetric Traveling Salesman Problems," Science 251, 754-761.
^ ] M.W. Padberg and M. Grötschel (1985). "Polyhedral Computations," in The Traveling Salesman Problem, Lawler, Lenstra, Rinooy Kan and Shmoys, eds., John Wiley, 307-360.
^ T. Christof and G. Reinelt, (1995) "Parallel cutting plane generation for the TSP in Parallel Programming and Applications (P. Fritzson, L. Finmo, eds.) IOS Press, 163-169.
^ D. Applegate, R.E. Bixby, V. Chvatal, and W. Cook (1998) "On the solution of traveling salesman problems" Documenta Mathematica - Extra Volume, ICM III 645-658.
^ RE Bland và DF Shallcross (1987). "Đi du lịch lớn người bán hàng vấn đề phát sinh từ thí nghiệm trong X-quang tinh thể: Báo cáo sơ bộ về tính toán," Báo cáo kỹ thuật số 730, Trường OR / IE, Đại học Cornell, Ithaca, New York.
^ ^a ^b BL Golden, L. Levy và R. Vohra (1987). "Vấn đề Orienteering," Hải quân nghiên cứu Logistics 34, 307-318.
^ HD Ratliff và AS Rosenthal (1981). "Trật tự hái trong một kho hình chữ nhật: Một trường hợp khả năng giải quyết cho vấn đề người bán hàng Du lịch," PDRC Báo cáo Dòng số 81-10. Viện Công nghệ Georgia, Atlanta, Georgia.
^ E. Balas (1989). "Giải thưởng Du lịch Thu vấn đề người bán hàng," Mạng 19, 621-636.
^ M. Dorigo, V. Maniezzo, et A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics--Part B, volume 26, numéro 1, pages 29-41, 1996.
^ Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, Amin Saberi (2010). “An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem” (PDF). Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. tr. 379–389. Bản gốc (PDF) lưu trữ ngày 13 tháng 3 năm 2011. Truy cập ngày 19 tháng 8 năm 2011.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
^ Satish B. Rao, Warren D. Smith (1998). “Approximating geometrical graphs via "spanners" and "banyans"”. Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC '98). ACM, New York, NY, USA. tr. 540–550. doi:10.1145/276698.276868.