Mỗi sáng, trước trung tâm hậu cần, nhiều chiếc xe tải chất hàng xong và chờ xuất phát. Hôm nay có hàng chục điểm cần giao, phải quyết định xe nào phụ trách nhà nào và đi theo thứ tự ra sao. Dù chở cùng một lượng hàng đến cùng những ngôi nhà, cách vạch đường đi vẫn làm quãng đường chạy trong ngày, tiền xăng dầu và giờ tan làm của tài xế khác nhau rất nhiều.
Nói một cách dễ hiểu, bài toán định tuyến phương tiện (Vehicle Routing Problem) là “bài toán tìm tập hợp các tuyến đường có tổng chi phí thấp nhất khi nhiều xe xuất phát từ kho, chia nhau ghé thăm nhiều khách hàng rồi quay về”. Năm 1959, George Dantzig và John Ramser lần đầu giới thiệu nó như bài toán điều xe tải chở xăng đến các trạm xăng, và ngày nay nó đã trở thành phép tính cơ bản của giao hàng chuyển phát và hậu cần phân phối.
Trong bài viết này, chúng ta sẽ lần lượt xem xét cấu trúc cơ bản của bài toán định tuyến phương tiện, lý do số trường hợp bùng nổ, các điều kiện mà thực tế bổ sung, và những cách tìm ra lời giải.
Phép tính lên đường đi cho nhiều xe tải cùng một lúc
Cấu trúc cơ bản của bài toán định tuyến phương tiện
Chỉ cần xác định vài yếu tố, hình hài của bài toán định tuyến phương tiện sẽ trở nên rõ ràng.
(1) Kho và phương tiện
Mọi xe đều xuất phát từ một kho duy nhất, tức là căn cứ xuất phát, và sau khi làm xong việc lại quay về đó. Có bao nhiêu xe và mỗi xe chở được bao nhiêu đã được định sẵn từ đầu.
(2) Khách hàng và nhu cầu
Mỗi điểm giao đều có vị trí và lượng hàng cần nhận. Mỗi khách hàng phải được phục vụ đúng một lần, và chỉ bởi một xe.
(3) Chi phí di chuyển
Khoảng cách, thời gian hay tiền bạc cần cho việc đi lại giữa hai điểm được tính trước. Nếu tìm trước đường ngắn nhất trên mạng lưới đường thực tế, chi phí giữa các điểm có thể được xử lý như một bảng duy nhất.
(4) Mục tiêu
Mục tiêu phổ biến nhất là giảm tổng chi phí di chuyển. Tùy trường hợp, mục tiêu cũng có thể là dùng ít xe nhất hoặc chia đều khối lượng công việc cho từng xe.
Vì sao số trường hợp bùng nổ
Bài toán tìm thứ tự ngắn nhất để một xe tải đi một vòng qua mọi ngôi nhà được gọi là bài toán người bán hàng du lịch (Traveling Salesman Problem). Bài toán định tuyến phương tiện là sự mở rộng bài toán này cho nhiều xe, nên ít nhất cũng khó bằng nó.
Nếu có 10 điểm cần ghé, chỉ riêng thứ tự đi đã cho khoảng 3,62 triệu khả năng. Với 20 điểm, con số đó phình lên khoảng 2,43 tỷ tỷ. Hơn nữa còn phải quyết định xe nào phụ trách khách nào, nên cách xem xét từng trường hợp một nhanh chóng chạm giới hạn.
Trong toán học, những bài toán như vậy được xếp vào loại NP-khó (NP-hard). Điều này có nghĩa là khi số khách hàng tăng lên, thời gian để tìm lời giải chính xác có thể tăng nhanh đến mức không chịu nổi. Vì thế ngoài thực tế, người ta thường chọn tìm nhanh một lời giải đủ tốt thay vì lời giải hoàn hảo.
Các điều kiện mà thực tế bổ sung
Hiện trường giao hàng thực tế phức tạp hơn nhiều so với bài toán trong sách giáo khoa, và mỗi điều kiện được thêm vào lại sinh ra một bài toán biến thể mới.
- Ràng buộc tải trọng (Capacitated Vehicle Routing Problem): mỗi xe chỉ chở được trọng lượng hoặc thể tích có giới hạn, nên phải chia khách hàng sao cho không vượt quá giới hạn đó.
- Ràng buộc khung thời gian (Vehicle Routing Problem with Time Windows): mỗi khách hàng có khung giờ nhận hàng nhất định và xe phải đến trong khoảng đó.
- Lấy hàng và giao hàng (Vehicle Routing Problem with Pickup and Delivery): xử lý cùng lúc việc chất hàng ở nơi này và dỡ xuống ở nơi khác.
- Nhiều kho (Multi-Depot Vehicle Routing Problem): có nhiều kho để xe xuất phát và quay về.
- Bài toán định tuyến xe điện (Electric Vehicle Routing Problem): cân nhắc cả quãng đường pin cho phép đi và các điểm sạc.
Ngoài ra, còn nhiều biến thể khác được nghiên cứu tùy theo hoàn cảnh thực tế, chẳng hạn trường hợp xe không cần quay về kho hay trường hợp mỗi ngày đi về kho nhiều lần.
Những cách tìm lời giải
Các cách giải bài toán định tuyến phương tiện chia thành hai hướng lớn: tìm lời giải chính xác và tìm nhanh một lời giải tốt.
Phương pháp chính xác
Người ta lập bài toán bằng mô hình toán học gọi là quy hoạch nguyên, rồi khéo léo loại bỏ các trường hợp khả dĩ để tìm lời giải tốt nhất. Chất lượng lời giải chắc chắn, nhưng khi khách hàng tăng thì thời gian tính toán tăng mạnh, nên chủ yếu dùng cho các bài toán quy mô nhỏ.
Thuật toán tiết kiệm
Đây là phương pháp do G. Clarke và J. W. Wright đề xuất năm 1964. Ban đầu giả định mỗi khách hàng được gửi một xe tải riêng, sau đó gộp dần các cặp khách hàng, bắt đầu từ cặp có khoảng cách giảm được lớn nhất khi nối vào một tuyến, tức là mức tiết kiệm lớn nhất. Cách tính đơn giản và kết quả dùng được, nên đến nay vẫn được dùng rộng rãi.
Siêu heuristic
Đây là các phương pháp như thuật toán di truyền, tìm kiếm tabu, mô phỏng luyện kim, tức là sửa dần từng chút tuyến đường ban đầu để tìm ra lời giải tốt hơn. Những phương pháp xuất sắc gần đây được cho là thu hẹp chênh lệch với lời giải tối ưu xuống khoảng 1 phần trăm, ngay cả với bài toán có từ hàng trăm đến hàng nghìn điểm.
Bài toán định tuyến phương tiện trông như việc kẻ đường trên bản đồ, nhưng phía sau là phép tính nhằm giảm đồng thời chi phí, thời gian và sức lao động của con người. Việc các hãng làm phần mềm lập kế hoạch tuyến đường quảng bá mức tiết kiệm chi phí từ 5 đến 30 phần trăm cũng cho thấy sức mạnh của phép tính này.
Không ngừng tính lại tuyến đường để chở cùng một lượng hàng trên con đường ngắn hơn, đó là bước đầu tiên của giao hàng hiệu quả.
