Một trong những nhiệm vụ tối ưu hoá phổ biến nhất là định tuyến xe, trong đó mục tiêu là tìm tuyến đường tốt nhất cho một nhóm xe ghé thăm một nhóm vị trí. Thông thường, "tốt nhất" có nghĩa là các tuyến đường có tổng quãng đường hoặc chi phí ít nhất. Dưới đây là một số ví dụ về các sự cố định tuyến:
- Một công ty giao hàng muốn chỉ định tuyến đường để người lái xe giao hàng.
- Một công ty truyền hình cáp muốn chỉ định tuyến đường cho các kỹ thuật viên thực hiện các cuộc gọi dịch vụ dân dụng.
- Một công ty đi chung xe muốn chỉ định tuyến đường để người lái xe đón và trả khách.
Vấn đề định tuyến nổi tiếng nhất là Vấn đề nhân viên bán hàng đi lại (TSP): tìm tuyến đường ngắn nhất cho nhân viên bán hàng cần ghé thăm khách hàng ở các vị trí khác nhau và quay lại điểm xuất phát. TSP có thể được biểu thị bằng một biểu đồ, trong đó các nút tương ứng với các vị trí và các cạnh (hoặc các bộ phận) biểu thị việc di chuyển trực tiếp giữa các vị trí. Ví dụ: biểu đồ bên dưới cho thấy một TSP có chỉ 4 vị trí, có nhãn A, B, C và D. Khoảng cách giữa hai vị trí bất kỳ được cho bằng số bên cạnh cạnh tiếp nối chúng.
Bằng cách tính khoảng cách của tất cả các tuyến đường có thể có, bạn có thể thấy rằng tuyến đường ngắn nhất là ACDBA, với tổng khoảng cách là 35 + 30 + 15 + 10 = 90.
Vấn đề trở nên khó khăn hơn khi có nhiều vị trí hơn. Trong ví dụ trên, chỉ có 6 tuyến đường. Nhưng nếu có 10 địa điểm (không tính điểm xuất phát), số tuyến đường sẽ là 362880. Đối với 20 vị trí, con số này sẽ là 2432902008176640000. Đảm bảo việc tìm kiếm toàn bộ mọi tuyến đường có thể sẽ tìm thấy tuyến đường ngắn nhất, nhưng việc này là không thể tính toán đối với tất cả các tập hợp vị trí nhỏ. Đối với các bài toán lớn hơn, cần có các kỹ thuật tối ưu hoá để tìm kiếm không gian giải pháp một cách thông suốt và tìm ra giải pháp tối ưu (hoặc gần như tối ưu).
Phiên bản chung hơn của TSP là vấn đề định tuyến xe (VRP), trong đó có nhiều xe. Trong hầu hết các trường hợp, VRP có các hạn chế: chẳng hạn như xe có thể chịu được trọng lượng hoặc thể tích tối đa của các vật phẩm mà chúng có thể mang theo, hoặc người lái xe có thể được yêu cầu ghé thăm các địa điểm trong khoảng thời gian cụ thể mà khách hàng yêu cầu.
OR-Tools có thể giải quyết nhiều loại VRP, bao gồm:
- Vấn đề nhân viên bán hàng đi lại, vấn đề định tuyến kiểu cũ, trong đó chỉ có một xe.
- Vấn đề định tuyến xe, một vấn đề tổng quát về TSP với nhiều xe.
- VRP có giới hạn về sức chứa, trong đó xe có sức chứa tối đa đối với các vật phẩm mà chúng có thể mang theo.
- VRP có khoảng thời gian, trong đó xe phải ghé thăm các địa điểm trong khoảng thời gian đã chỉ định.
- VRP có hạn chế về tài nguyên, chẳng hạn như không gian hoặc nhân viên để bốc xếp xe tại kho (điểm xuất phát của các tuyến đường).
- VRP có số lượt truy cập bị giảm, trong đó phương tiện không bắt buộc phải ghé thăm tất cả các vị trí, nhưng phải trả một hình phạt cho mỗi lượt ghé thăm bị loại bỏ.
Hạn chế trong việc giải quyết các vấn đề về định tuyến cho xe
Các vấn đề về định tuyến cho xe vốn rất khó giải quyết: khoảng thời gian cần thiết để giải quyết chúng tăng theo cấp số nhân cùng với quy mô của vấn đề. Đối với các vấn đề đủ lớn, có thể mất nhiều năm để tìm giải pháp tối ưu, có thể là OR-Tools (hoặc bất kỳ phần mềm định tuyến nào khác) . Do đó, đôi khi OR-Tools lại trả về các giải pháp tốt nhưng không tối ưu. Để tìm giải pháp tốt hơn, hãy thay đổi các tuỳ chọn tìm kiếm cho trình giải. Hãy xem phần Thay đổi chiến lược tìm kiếm để biết ví dụ.