Bài toán định tuyến xe (vehicle routing problem, VRP) hỏi: với một đội xe xuất phát từ kho và một danh sách điểm cần giao, nên chia đơn cho xe nào và mỗi xe đi theo thứ tự nào để tổng quãng đường hay thời gian là thấp nhất, trong khi vẫn tôn trọng sức chở, giờ hẹn và giờ làm việc. Bài toán được George Dantzig và John Ramser nêu năm 1959. Phần mềm xếp tuyến ngày nay giải nó bằng các phương pháp gần đúng, cho tuyến "đủ tốt" trong vài giây đến vài phút chứ không bảo đảm tối ưu tuyệt đối.
Từ một xe đến cả đội xe
Nếu chỉ có một người giao và muốn đi qua mọi điểm rồi quay về với quãng đường ngắn nhất, đó là bài toán người du lịch (TSP) quen thuộc trong toán học. Đời thật phức tạp hơn: có nhiều xe, mỗi xe chở có hạn, khách có giờ hẹn, người lái có giờ nghỉ. VRP là họ bài toán mở rộng TSP để mô tả những ràng buộc đó.
Bài báo năm 1959 của Dantzig và Ramser có tên "The Truck Dispatching Problem", xét bài toán phân phối xăng dầu từ một kho tới các trạm xăng bằng xe bồn. Từ đó, VRP trở thành một trong những bài toán được nghiên cứu nhiều nhất trong vận trù học, với hàng nghìn công trình và nhiều biến thể.
Các biến thể hay gặp
| Biến thể | Thêm ràng buộc gì | Gặp ở đâu ngoài đời |
|---|---|---|
| VRP có giới hạn tải (CVRP) | Mỗi xe chỉ chở được một khối lượng hoặc thể tích nhất định | Phân phối hàng cho cửa hàng, đại lý |
| VRP có khung thời gian (VRPTW) | Mỗi điểm chỉ được giao trong một khung giờ | Giao hàng hẹn giờ, giao cho nhà hàng trước giờ mở cửa |
| Lấy và giao (pickup and delivery) | Hàng lấy ở điểm A phải giao ở điểm B, trên cùng một xe | Giao đồ ăn, chuyển phát nội thành |
| Nhiều kho | Xe xuất phát từ nhiều điểm khác nhau | Mạng lưới bưu cục, kho vệ tinh |
| Động (dynamic) | Đơn mới phát sinh khi xe đang chạy | Giao hàng trong ngày, giao nhanh |
Vì sao không giải "chính xác" được
Số tuyến có thể có tăng nhanh khủng khiếp theo số điểm giao. Với vài chục điểm, số cách sắp thứ tự đã lớn hơn khả năng thử hết của bất kỳ máy tính nào. VRP thuộc nhóm bài toán NP-khó: chưa ai tìm ra thuật toán luôn cho lời giải tối ưu nhanh khi bài toán lớn. Có những phương pháp tìm lời giải tối ưu thật sự, nhưng chỉ làm được với số điểm vừa phải và tốn thời gian.
Vì thế phần mềm thực tế dùng phương pháp gần đúng: tìm lời giải tốt, rồi cải thiện dần trong thời gian cho phép.
Phần mềm xếp tuyến làm việc ra sao
Bước 1: chuẩn bị dữ liệu
Phần mềm cần biết vị trí từng điểm (toạ độ, chuyển từ địa chỉ), lượng hàng mỗi điểm, khung giờ hẹn, sức chở từng xe, giờ bắt đầu và kết thúc ca. Rồi nó tính ma trận thời gian di chuyển: từ mỗi điểm tới mỗi điểm khác mất bao lâu, dựa trên mạng đường và có khi cả dữ liệu tắc đường theo giờ.
Bước 2: dựng lời giải ban đầu
Một cách cổ điển là phương pháp "tiết kiệm" của Clarke và Wright (1964): bắt đầu bằng giả định mỗi điểm có một xe riêng đi rồi về, sau đó ghép dần các cặp điểm vào chung một tuyến nếu việc ghép tiết kiệm được nhiều quãng đường nhất mà vẫn không vượt sức chở. Một cách khác là chia điểm theo góc quanh kho rồi xếp tuyến cho từng múi. Cả hai đều nhanh và cho kết quả khá.
Bước 3: cải thiện
Từ lời giải ban đầu, phần mềm thử những thay đổi nhỏ: đổi chỗ hai điểm, chuyển một điểm sang xe khác, đảo ngược một đoạn tuyến. Thay đổi nào tốt hơn thì giữ. Các phương pháp như tìm kiếm tabu, mô phỏng luyện kim, thuật toán di truyền là những cách có hệ thống để tránh bị "kẹt" ở một lời giải tạm được.
Bước 4: xuất kết quả
Mỗi xe nhận một danh sách điểm theo thứ tự, giờ dự kiến đến mỗi điểm, và thường có sơ đồ trên bản đồ. Kho dùng danh sách này để xếp hàng lên xe theo thứ tự ngược.
Ý tưởng "tiết kiệm" làm bằng tay
Thử với hai khách A và B, cùng nằm ở phía đông kho. Nếu mỗi khách một chuyến riêng, xe đi kho → A → kho, rồi kho → B → kho: đoạn kho–A và kho–B mỗi đoạn đi hai lần. Nếu ghép thành một chuyến kho → A → B → kho, ta bỏ được một lần quay về từ A và một lần đi ra tới B, thay bằng một đoạn A → B. Phần tiết kiệm bằng (kho–A) + (kho–B) − (A–B). A và B càng xa kho mà càng gần nhau thì ghép càng lời.
Phương pháp Clarke–Wright chỉ là làm phép tính đó cho mọi cặp điểm, sắp các cặp theo mức tiết kiệm từ lớn đến nhỏ, rồi ghép dần. Người giao hàng làm điều tương tự mỗi ngày mà không gọi tên: "hai đơn này cùng phía, cùng xa, đi chung một chuyến".
Giới hạn: phần mềm chỉ tốt bằng dữ liệu
- Địa chỉ sai, toạ độ lệch: một điểm bị đặt nhầm sang khu khác sẽ kéo lệch cả tuyến.
- Thời gian phục vụ ước sai: giao ở chung cư cần gửi xe, lên thang máy, chờ khách xuống, mất nhiều thời gian hơn nhà mặt đường.
- Thực tế đường phố: hẻm vừa bị rào, chợ họp tràn ra đường, đoạn đang sửa không có trong dữ liệu.
- Yếu tố con người: khách vắng, khách đổi giờ, người giao cần nghỉ ăn trưa.
Vì vậy ở các đơn vị giao hàng có kinh nghiệm, người điều phối và người giao luôn có quyền chỉnh tuyến do phần mềm đưa ra. Phần mềm tốt là phần mềm học được từ những lần chỉnh đó, ví dụ cập nhật thời gian phục vụ thực tế ở từng toà nhà.
Lời giải "đủ tốt" là đủ tốt đến đâu
Với bài toán vài chục đến vài trăm điểm, các phương pháp gần đúng hiện đại thường cho tuyến rất sát với tuyến tốt nhất từng biết trên các bộ dữ liệu thử nghiệm chuẩn mà giới nghiên cứu dùng để so sánh. Trong thực tế, sai lệch do dữ liệu (tắc đường bất ngờ, khách vắng) thường lớn hơn nhiều so với khoảng cách giữa lời giải "đủ tốt" và lời giải tối ưu lý thuyết. Theo đuổi tối ưu tuyệt đối vì thế hiếm khi đáng công.
Góc nhìn hôm nay: người giao và thuật toán
Không cần biết toán để hưởng lợi từ những ý tưởng này. Cách gom đơn theo cụm, chia múi quanh kho, ghép hai điểm gần nhau vào cùng một chuyến, đảo thứ tự để tránh đi lại một đoạn đường: tất cả đều là phiên bản bằng tay của những gì phần mềm làm. Người muốn tìm hiểu sâu có thể đọc giáo trình vận trù học nhập môn, phần về định tuyến xe, hoặc thử các thư viện tối ưu mã nguồn mở có ví dụ VRP. Còn người làm nghề nên nhớ một điều: tuyến trên màn hình là bản nháp, người chạy ngoài đường mới là người hoàn thiện nó.
Câu hỏi thường gặp
Bài toán định tuyến xe VRP là gì?
VRP là bài toán chia các điểm giao cho một đội xe xuất phát từ kho và xếp thứ tự đi cho mỗi xe sao cho tổng quãng đường hoặc thời gian thấp nhất, trong khi vẫn tôn trọng sức chở, giờ hẹn và giờ làm việc. Bài toán được Dantzig và Ramser nêu năm 1959.
VRP khác bài toán người du lịch TSP thế nào?
TSP tìm tuyến ngắn nhất cho một người đi qua mọi điểm rồi quay về. VRP mở rộng cho nhiều xe, mỗi xe có sức chở giới hạn, có khung giờ giao và các ràng buộc thực tế khác, nên gần với bài toán giao hàng hơn.
Phần mềm xếp tuyến có cho tuyến tối ưu không?
Thường là không bảo đảm tối ưu tuyệt đối, mà cho lời giải gần đúng rất tốt trong thời gian ngắn. Trong thực tế, sai lệch do tắc đường hay khách vắng thường lớn hơn khoảng cách giữa lời giải đó và lời giải tối ưu lý thuyết.
Phương pháp tiết kiệm Clarke–Wright là gì?
Đây là cách dựng tuyến cổ điển công bố năm 1964: giả định mỗi điểm có một xe riêng, sau đó ghép dần các cặp điểm vào chung một tuyến theo mức tiết kiệm quãng đường lớn nhất, miễn không vượt sức chở của xe. Cách này đơn giản và vẫn được dùng làm lời giải ban đầu.
