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ố.

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ị

TSP đối xứng với bốn thành phố

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ách. 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.

Độ 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ó.

Độ 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)$.

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.

Liên kết ngoài

Tiếng Anh:

• Demo applet of a genetic algorithm solving TSP and VRPTW online
• TSPLIB
• Travelling Salesman Problem at Georgia Tech
• Example of finding approximate solution of TSP problem using a genetic algorithm
• A Java implementation of a TSP-solution using JGAP (Java Genetic Algorithms Package). The technique used is a Genetic Algorithm.
• Solution of the Travelling Salesman Problem using a Kohonen Map
• Kohonen Neural Network applied to the Traveling Salesman Problem (using three dimensions).
• Most TSP loop families grow polynomially Private web page shows that a method exists for obtaining a set of optimal "travelling salesman" routes that is a member of a family that grows no faster than about 2ⁿIn2. However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.
• VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
• Work-in-progress attempted proof on private web page of polynomial calculation time on the 2-D undirected graph.
• Links to TSP source codes
• http://www.delphiforfun.org/Programs/traveling_salesman.htm The Travelling Salesman Problem (TSP) requires that we find the shortest path visiting each of a given set of cities and returning to the starting point.
• CONCORDE Home of the CONCORDE TSP Solver, an ANSI C library dedicated to solving the TSP problem.