Bài toán người bán hàng (TSP)
Bài toán người bán hàng (Traveling Salesman Problem - TSP) là một bài toán phổ biến và có nhiều ứng dụng trong logistics. Trong TSP, một người bán hàng được cho một danh sách các thành phố và khoảng cách giữa từng cặp thành phố. Mục tiêu là tìm đường đi ngắn nhất xuất phát từ điểm gốc, đi qua tất cả các điểm, rồi quay trở lại thành phố ban đầu. Đây là một bài toán tính toán khó, nhưng Miller-Tucker-Zemlin (MTZ) đã chỉ ra rằng có thể giải bằng Quy hoạch tuyến tính nguyên (Integer Linear Programming). Trong bài tập này, bạn sẽ xác định hàm mục tiêu và một số ràng buộc cho TSP trên một bộ dữ liệu nhỏ gồm 15 thành phố (xem hình bên dưới). Mục tiêu là thử dùng LpVariable.dicts kết hợp với list comprehension.
Ba biến Python n, cities và dist đã được tạo sẵn cho bạn \(^{1}\). Biến n là số lượng thành phố, cities là danh sách các thành phố được đánh số, và dist là một pandas DataFrame chứa khoảng cách cặp giữa các thành phố. Bạn có thể khám phá chúng trong console. Ngoài ra, mô hình cũng đã được khởi tạo sẵn cho bạn.
\(^{1}\) Bộ dữ liệu đến từ Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Bài tập này là một phần của khóa học
Phân tích Chuỗi Cung Ứng với Python
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____],
cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____],
lowBound=0, upBound=(n-1), cat=____)