OR-Tools là một phần mềm nguồn mở nhằm tối ưu hoá tổ hợp, nhằm tìm kiếm giải pháp tốt nhất cho một vấn đề trong số rất nhiều các giải pháp có thể có. Dưới đây là một số ví dụ về các vấn đề mà OR-Tools giải quyết:
- Định tuyến xe: Tìm tuyến đường tối ưu cho các nhóm xe đón khách và giao hàng theo các gói ràng buộc (ví dụ: "xe tải này không thể chứa nhiều hơn 20.000 cân Anh" hoặc "phải giao hàng trong vòng 2 giờ").
- Lên lịch: Tìm lịch biểu tối ưu cho một nhóm tác vụ phức tạp, một số tác vụ cần thực hiện trước những tác vụ khác, trên một nhóm máy cố định hoặc các tài nguyên khác.
- Đóng gói thùng rác: Đóng gói nhiều đối tượng có kích thước khác nhau nhất có thể vào các thùng chứa cố định có dung tích tối đa.
Trong hầu hết các trường hợp, những vấn đề như vậy sẽ có rất nhiều giải pháp khả thi – quá nhiều máy tính có thể tìm kiếm tất cả. Để khắc phục điều này, OR-Tools sử dụng các thuật toán hiện đại để thu hẹp tập hợp tìm kiếm nhằm tìm ra giải pháp tối ưu (hoặc gần với mức tối ưu).
OR-Tools bao gồm những trình giải quyết cho:
- Lập trình quy tắc ràng buộc
- Một bộ kỹ thuật để tìm những giải pháp khả thi cho một vấn đề được thể hiện dưới dạng những điều kiện ràng buộc (ví dụ: không thể sử dụng một phòng cho hai sự kiện cùng lúc hoặc khoảng cách đến cây trồng phải nhỏ hơn chiều dài của ống hoặc không được ghi quá 5 chương trình truyền hình cùng một lúc).
- Lập trình tuyến tính và kết hợp số nguyên
- Trình tối ưu hoá tuyến tính Glop tìm giá trị tối ưu của một hàm mục tiêu tuyến tính, dựa trên một tập hợp bất đẳng thức tuyến tính dưới dạng các ràng buộc (ví dụ: chỉ định công việc cho mọi người hoặc tìm mức phân bổ tốt nhất của một nhóm tài nguyên trong khi giảm thiểu chi phí). Glop và phần mềm lập trình hỗn hợp số nguyên SCIP cũng có sẵn thông qua Dịch vụ tối ưu hoá Google Apps Script.
- Định tuyến xe
- Một thư viện chuyên biệt giúp xác định các tuyến đường tốt nhất cho xe ô tô dựa trên các quy tắc ràng buộc.
- Thuật toán biểu đồ
- Mã để tìm các đường dẫn ngắn nhất trong biểu đồ, luồng chi phí tối thiểu, luồng tối đa và các phép gán tổng tuyến tính.
Phần tiếp theo sẽ giúp bạn bắt đầu sử dụng OR-Tools một cách nhanh chóng.