Bài toán TSP là gì? Vì sao đội sales thực địa Việt Nam đang lãng phí 15–25% quãng đường mỗi ngày

TSP là gì, và tại sao nó "khó" theo đúng nghĩa toán học

Traveling Salesperson Problem (TSP) — bài toán người giao hàng — được phát biểu đơn giản: cho một danh sách địa điểm, tìm thứ tự ghé thăm tất cả các điểm đó sao cho tổng quãng đường di chuyển là ngắn nhất, rồi quay về điểm xuất phát. Nghe có vẻ đơn giản, nhưng TSP thuộc lớp bài toán NP-khó (NP-hard) — một trong những phát hiện nền tảng của khoa học máy tính từ thập niên 1970.

Ý nghĩa thực tế của "NP-khó": không có thuật toán nào được biết đến có thể giải chính xác TSP trong thời gian đa thức khi số điểm tăng lên. Nếu duyệt toàn bộ phương án (brute-force), số hoán vị cần kiểm tra tăng theo giai thừa — với 10 điểm bán đã có hơn 3,6 triệu hoán vị, với 15 điểm là hơn 43 nghìn tỷ. Không máy tính nào, và chắc chắn không có nhân viên sales nào, có thể duyệt hết các phương án này trong đầu mỗi sáng.

Đây là lý do một nhân viên giàu kinh nghiệm sắp xếp lộ trình "theo cảm giác" — dựa trên trí nhớ và thói quen — gần như luôn cho ra một lộ trình chênh lệch đáng kể so với lộ trình tối ưu, dù họ đã đi tuyến đó hàng trăm lần.

Vì sao vẫn giải được trong vài giây: Metaheuristics

Không giải được "chính xác tuyệt đối" trong thời gian ngắn không có nghĩa là bất lực. Từ những năm 1970 đến nay, giới nghiên cứu vận trù học (operations research) đã phát triển các thuật toán xấp xỉ (metaheuristics) như Lin-Kernighan-Helsgaun (LKH) hay các bộ giải chính xác quy mô lớn như Concorde — cho phép tìm ra lộ trình chênh lệch dưới 1% so với lời giải tối ưu tuyệt đối, trong thời gian chỉ vài giây, với hàng nghìn điểm.

Với quy mô của một tuyến sales thực địa tại Việt Nam — thường 15–30 điểm bán mỗi ngày, cộng thêm ràng buộc thực tế như khung giờ mở cửa, thời gian phục vụ tại mỗi điểm, và vị trí xuất phát — bài toán hoàn toàn nằm trong khả năng giải gần-tối-ưu của các thuật toán hiện đại chỉ trong vài giây đến vài phút, không phải vài giờ dò bản đồ thủ công của điều phối viên.

Bài toán thực tế của Việt Nam: mật độ điểm bán cao, hạ tầng phức tạp

Thị trường bán lẻ FMCG Việt Nam vẫn vận hành chủ yếu qua kênh truyền thống (General Trade — GT: tạp hoá, cửa hàng nhỏ lẻ) bên cạnh kênh hiện đại (Modern Trade — MT: siêu thị, cửa hàng tiện lợi), theo các báo cáo thị trường thường niên của Nielsen và Kantar Worldpanel Vietnam. Với một nhà phân phối hoặc nhãn hàng vận hành đội sales field phủ hàng trăm đến hàng nghìn điểm bán GT rải rác trong các con hẻm, khu dân cư mật độ cao, bài toán tối ưu lộ trình càng phức tạp hơn nhiều so với các thị trường có hạ tầng đường sá quy hoạch đơn giản.

Chi phí logistics của Việt Nam nói chung được Ngân hàng Thế giới và Hiệp hội Doanh nghiệp Dịch vụ Logistics Việt Nam (VLA) ước tính ở mức 16–20% GDP — cao hơn đáng kể so với mức 8–14% tại các nền kinh tế phát triển. Phần lớn khoảng chênh lệch này không nằm ở chi phí vận tải đường dài, mà ở khâu phân phối chặng cuối (last-mile) — chính xác là nơi bài toán TSP xuất hiện mỗi ngày.

Từ lý thuyết đến sản phẩm: AI Route Planning hoạt động thế nào

Một hệ thống AI route planning thực tế — như module trong ZenTSP — không chỉ giải TSP thuần tuý mà giải một biến thể có ràng buộc: thứ tự ghé điểm bán tối ưu, có tính đến khung giờ mở cửa của từng điểm, thời gian phục vụ ước tính, và vị trí xuất phát của từng nhân viên. Đầu vào là danh sách điểm bán trong ngày (có thể đến từ dữ liệu CRM hoặc kế hoạch tuần), đầu ra là thứ tự ghé thăm cùng ETA (thời gian dự kiến đến) cho từng điểm — sẵn sàng để nhân viên mở app và đi ngay, không cần tự nghĩ.

Với các triển khai thực tế, kết quả đo được nằm trong khoảng giảm 15–25% tổng quãng đường di chuyển so với lộ trình tự sắp xếp, và thời gian lập kế hoạch cho toàn bộ đội sales rút từ 2–3 tiếng mỗi sáng của điều phối viên xuống còn vài phút xử lý tự động.