Tối ưu tuyến đường TSP

Bai toan Nguoi ban hang du lich (TSP) la gi?

TSP hoi: cho mot tap dia diem va khoang cach giua chung, tuyen duong ngan nhat tham moi dia diem dung mot lan va quay ve diem xuat phat la gi? Day la mot trong nhung bai toan duoc nghien cuu nhieu nhat.

TSP la NP-kho, khong co thuat toan nao giai toi uu trong thoi gian da thuc cho truong hop lon. Giai phap thuc te dua vao heuristic: Lang gieng gan nhat (nhanh, dai hon toi uu ~25%), Clarke-Wright, va meta-heuristic.

TSP ung dung truc tiep trong giao hang cham diem, lich trinh dich vu, khoan PCB va toi uu duong lay hang trong kho.

Formula: Muc tieu: min Σ d(route[i], route[i+1]) Lang gieng gan nhat: tham dia diem gan nhat chua tham Tiet kiem: s(i,j) = d(depot,i) + d(depot,j) − d(i,j)

Vi du tinh toan

Xuat phat (0,0), 4 diem (3,4),(6,1),(8,5),(2,7). Lang gieng gan nhat: tong 25,1. Clarke-Wright co the tim 23,4.

Khi nào nên sử dụng máy tính này

• Điều phối giao hàng lập kế hoạch tuyến hàng ngày cho một tài xế thăm 10-30 địa điểm khách hàng
• Quản lý dịch vụ hiện trường tối ưu tuyến kỹ thuật viên để giảm thiểu thời gian di chuyển giữa các cuộc gọi dịch vụ
• Kỹ sư kho thiết kế đường lấy hàng tối ưu qua nhiều vị trí lối đi
• Đại diện bán hàng lên kế hoạch chuyến đi nhiều thành phố thăm khách hàng với khoảng cách lái xe tối thiểu

Những sai lầm thường gặp cần tránh

• Giả định giải pháp lân cận gần nhất là tối ưu — đây là heuristic tham lam có thể dài hơn 20-25% so với tuyến tối ưu; luôn thử nhiều thuật toán và so sánh
• Sử dụng khoảng cách đường thẳng (Euclid) cho định tuyến đường bộ — khoảng cách lái xe thực tế có thể dài hơn 20-40% do mạng lưới đường; dùng khoảng cách thực nếu có
• Quên bao gồm chuyến về depot — TSP yêu cầu trở về điểm xuất phát; bỏ qua chuyến về sẽ đánh giá thấp tổng khoảng cách tuyến
• Áp dụng TSP cho bài toán thực chất là VRP — nếu có ràng buộc công suất, cửa sổ thời gian hoặc nhiều xe, hãy sử dụng công cụ VRP để có kết quả tốt hơn

Cách diễn giải kết quả

• So sánh kết quả Nearest Neighbor và Clarke-Wright: nếu khác biệt đáng kể, bài toán có chỗ để tối ưu thêm với phương pháp nâng cao hơn
• Thời gian tính toán bằng mili giây giúp đánh giá liệu định tuyến lại thời gian thực có khả thi cho quy mô bài toán của bạn
• Hình ảnh bản đồ tuyến giúp xác định sự kém hiệu quả rõ ràng như tuyến giao nhau hoặc quay lui không cần thiết mà heuristic có thể tạo ra

Tiêu chuẩn & Tài liệu tham khảo

• Nearest Neighbor và tiết kiệm Clarke-Wright (1964) — các heuristic xây dựng được đối sánh trong công cụ này
• Tìm kiếm cục bộ Lin-Kernighan — heuristic tham chiếu thực tế cho các hành trình TSP chất lượng cao
• TSPLIB — thư viện đối sánh công khai chuẩn dùng để so sánh chất lượng bộ giải TSP

Câu hỏi thường gặp

Nen dung thuat toan nao?

Duoi 15 diem: lang gieng gan nhat, trong 20-25% toi uu. 15-50 diem: Clarke-Wright + 2-opt, trong 5-10%. Tren 50: meta-heuristic hoac Google OR-Tools.

TSP khac gi voi dinh tuyen giao hang thuc te?

Thuc te them cua so thoi gian, suc chua xe, giao thong, duong mot chieu va nhieu xe. TSP la nen tang nhung phan mem thuc te them cac rang buoc nay.