Route Optimization là gì? Thuật toán, ràng buộc và API

Route optimization là việc sắp xếp thứ tự điểm dừng và phân công xe để đội xe hoàn thành công việc trong ít thời gian, khoảng cách hoặc chi phí nhất. Đó là sự khác biệt giữa một tài xế giao hàng kết thúc lúc 4 giờ chiều và một tài xế khác kết thúc lúc 7 giờ tối với cùng chiếc van và cùng các điểm dừng. Bên dưới mỗi nút "optimised route" trong một app logistics là một solver vừa chạy qua hàng triệu thứ tự khả thi và chọn ra một.

Bài viết này giải thích route optimization thực sự là gì, cách solver tiếp cận nó, nơi nó xuất hiện trong thế giới thực và những ràng buộc, cạm bẫy phân biệt một demo với production.

Route optimization thực sự là gì

Trong khoa học máy tính, route optimization nằm trong hai bài toán kinh điển. Travelling Salesman Problem (TSP) hỏi: cho một danh sách thành phố và khoảng cách giữa chúng, lộ trình ngắn nhất đi qua mỗi thành phố đúng một lần và quay lại điểm xuất phát là gì? Đó là bài toán một xe. Vehicle Routing Problem (VRP) tổng quát hóa cho đội xe: cho một kho, một tập khách hàng và nhiều xe, nên chia khách hàng giữa các xe ra sao và mỗi xe nên đi qua khách của mình theo thứ tự nào?

Cả hai bài toán đều NP-hard. Số thứ tự khả thi tăng theo giai thừa với số điểm dừng. Hai mươi điểm dừng đã tạo ra hơn 10 mũ 18 lộ trình khả thi. Không thuật toán chính xác nào có thể duyệt không gian đó theo thời gian thực. Optimization, trong production, do đó không phải là tìm câu trả lời hoàn hảo. Nó là tìm một câu trả lời rất tốt đủ nhanh để hành động.

Solver tiếp cận bài toán thế nào

Vì không gian tìm kiếm khổng lồ, các solver thực kết hợp nhiều kỹ thuật.

Cho bài toán nhỏ (dưới khoảng 15 điểm dừng), phương pháp chính xác như branch-and-bound hoặc integer programming có thể trả về lời giải tối ưu chứng minh được trong vài giây. Vượt qua quy mô đó, phương pháp chính xác không còn thực tế và lĩnh vực chuyển sang heuristic.

Một pipeline điển hình bắt đầu với một heuristic dựng như nearest-neighbour hoặc thuật toán savings Clarke-Wright để tạo lộ trình khởi tạo. Lộ trình đó sau đó được giao cho một metaheuristic, lặp lại việc đổi điểm dừng, đảo ngược sub-tour hoặc chuyển điểm dừng giữa các xe để cải thiện hàm mục tiêu. Simulated annealing, tabu search, large neighbourhood search và genetic algorithm là các lựa chọn phổ biến nhất. Mỗi cái có cùng cấu trúc: thử một thay đổi, quyết định có chấp nhận hay không, lặp lại trong một ngân sách thời gian cố định.

Input quan trọng còn lại là distance matrix: bảng tính trước về thời gian và khoảng cách di chuyển giữa mọi cặp điểm dừng. Optimizer truy vấn matrix hàng triệu lần trong quá trình tìm kiếm, nên matrix được dựng một lần ngay từ đầu bởi routing engine và giữ trong bộ nhớ trong khi solver chạy.

Route optimization xuất hiện ở đâu

Route optimization âm thầm vận hành một danh sách dài các doanh nghiệp vận hành.

• Last-mile delivery: hãng vận chuyển bưu kiện, giao hàng tạp hóa và fulfilment thương mại điện tử đều sắp xếp hàng chục đến hàng trăm điểm dừng cho mỗi van mỗi ngày
• Field service: kỹ thuật viên HVAC, lắp đặt viễn thông và nhân viên y tế tại nhà thăm khách trong một vùng với time window cuộc hẹn và yêu cầu kỹ năng
• Mobile workforce: đội ngũ công ích, đọc đồng hồ và thanh tra phủ vùng lãnh thổ với loại công việc hỗn hợp
• Giao đồ ăn: ứng dụng tổng hợp nhà hàng gộp nhiều đơn vào một chuyến đi của shipper khi địa lý phù hợp
• Thu gom rác: xe tải đô thị chạy vòng cố định hàng tuần, nơi sắp xếp lại nhỏ tiết kiệm nhiên liệu thật
• Sales rep: lập kế hoạch lãnh thổ nơi rep thăm 8 đến 12 khách mỗi ngày và thứ tự ảnh hưởng đến thời gian lái xe và mật độ cuộc gặp

Trong mọi trường hợp người dùng thấy danh sách điểm dừng theo đúng thứ tự. Công việc diễn ra trong optimizer phía sau.

Những ràng buộc quan trọng

Một solver chỉ giảm thiểu khoảng cách là một đồ chơi. Routing production được định nghĩa bởi các ràng buộc.

• Sức chứa xe: mỗi van có giới hạn trọng lượng, thể tích hoặc pallet mà các điểm dừng được gán không được vượt qua
• Time window: khách hàng kỳ vọng giao hàng trong khoảng, ví dụ 9 đến 11 giờ sáng, và đến lúc 11:05 là thất bại
• Ca tài xế: số giờ làm việc tối đa, các đợt nghỉ bắt buộc, xuất phát và kết thúc tại kho cụ thể
• Khớp kỹ năng hoặc loại xe: lắp tủ lạnh cần đội hai người, giao hàng cold-chain cần van làm lạnh
• Đa kho: đội xe lớn dispatch từ nhiều kho và solver quyết định kho nào xử lý điểm dừng nào
• Quay về cơ sở: một số tuyến mở (tài xế kết thúc tại nhà), một số tuyến đóng (tài xế quay về kho)

Mỗi ràng buộc thu hẹp tập tuyến khả thi và đẩy solver về phía những lời giải trông hơi tệ trên giấy nhưng thực sự thực hiện được.

Cạm bẫy trong production

Route optimization là một mảng nơi demo luôn chạy được và rollout thường thì không.

Tối ưu sai mục tiêu. Giảm thiểu khoảng cách là mặc định, nhưng với nhiều đội xe thì doanh thu hoặc tuân thủ service level quan trọng hơn số km tiết kiệm. Một tuyến giao thêm một bưu kiện đổi lấy 2 km thường là thắng.

Thời gian free-flow vs nhận biết giao thông. Một matrix dựng từ tốc độ đường thô sẽ nói tuyến mất 4 giờ trong khi giờ cao điểm thật mất 6. Hãy dùng routing engine bộc lộ thời gian di chuyển nhận biết giao thông cho khoảng giờ tuyến sẽ chạy.

Không có replanning thời gian thực. Kế hoạch trôi đi ngay khi tài xế gặp tắc đường bất ngờ, khách hủy hoặc có điểm dừng mới đến. Đội vận hành cần cách re-optimize các điểm dừng còn lại giữa ngày mà không vứt bỏ công sức buổi sáng.

Kế hoạch đóng băng cũ kỹ. Một tuyến cố định hàng tuần trông tối ưu vào tháng Một và giờ tệ hơn 20 phần trăm vì khách đã chuyển, sản lượng đã đổi và một con đường một chiều đã xuất hiện. Hãy chạy lại optimization định kỳ và so sánh kế hoạch mới với kế hoạch đang chạy trước khi áp đặt thay đổi cho tài xế.

Route Optimization trong MapAtlas

MapAtlas Optimize Route API giải quyết bài toán routing một xe và đội xe với những ràng buộc mà đội vận hành thực sự cần: sức chứa, time window, ca, kỹ năng và setup đa kho. Nó trả về kế hoạch có thứ tự cho mỗi xe kèm thời gian đến và đi dự đoán cho mọi điểm dừng.

Nó kết hợp tự nhiên với hai endpoint khác trong stack MapAtlas. Distance Matrix API dựng bảng thời gian di chuyển mà solver tiêu thụ, với thời gian nhận biết giao thông để kế hoạch trụ vững vào giờ cao điểm. Directions API vẽ đường đi turn-by-turn thực tế giữa các điểm dừng liên tiếp khi thứ tự đã cố định, để app tài xế có thể hiển thị polyline thật chứ không phải đường thẳng.

Route optimization sẽ không trông hào nhoáng trong slide deck. Nó là một solver, một matrix và một danh sách ràng buộc. Nhưng đó là lớp quyết định liệu một đội xe có hoàn thành ngày làm việc đúng giờ và đúng ngân sách hay không, và làm đúng nó là điều phân biệt một tính năng routing được ship với một tính năng bị âm thầm tắt đi.