Công nghệ tối ưu hóa toán học cho tàu chở hàng

Tối ưu hóa mạng lưới vận tải của tàu chở hàng: kỹ thuật tối ưu hóa toán học

Tổng quan

• Nhóm nghiên cứu của Google đã công bố API Shipping Network Design mới.
• API này giúp giải quyết các bài toán thiết kế mạng lưới và lập lịch cho tàu chở hàng.
• Giải pháp này nhanh hơn và hiệu quả hơn các phương pháp hiện có, giúp tăng gấp đôi doanh thu và vận chuyển được nhiều container hơn với ít tàu hơn.

Bối cảnh

• LSNDSP (bài toán thiết kế mạng lưới và lập lịch tàu) gồm ba thành phần: thiết kế mạng lưới, lập lịch mạng lưới và định tuyến container.
• Trước đây, các bài toán này thường được giải quyết riêng lẻ, nhưng nếu giải đồng thời thì có thể tìm ra lời giải tốt hơn.

Phương pháp

• Bài toán tối ưu hóa được cấu thành từ biến số, ràng buộc và hàm mục tiêu.
• Google sử dụng hai cách tiếp cận là Double Column Generation và CP-SAT để giải bài toán.
• Các phương pháp này cung cấp lời giải tối ưu cho các bài toán quy mô nhỏ và vừa, nhưng không phù hợp với các bài toán quy mô lớn.
• Để xử lý các bài toán lớn, Google sử dụng Large Neighborhood Search và Variable Neighborhood Search.
• Các phương pháp này thu hẹp không gian tìm kiếm và nâng cao hiệu quả thông qua xử lý song song.

Kết quả

• Hiệu năng được đánh giá bằng bộ benchmark LINERLIB.
• Giải pháp của Google cho phép vận chuyển nhiều container hơn với ít tàu hơn.
• Trong từng kịch bản, giải pháp này đều nâng cao hiệu quả và làm tăng đáng kể doanh thu.

Kết luận

• Kỹ thuật tối ưu hóa của Google là phương pháp đầu tiên có thể giải quyết các bài toán thiết kế mạng lưới và lập lịch tàu quy mô lớn.
• Nghiên cứu này được kỳ vọng sẽ góp phần nâng cao hiệu quả của chuỗi cung ứng toàn cầu.

Ý kiến của GN⁺

• Bối cảnh kỹ thuật: LSNDSP là một bài toán tối ưu hóa phức tạp, đòi hỏi phải đồng thời giải quyết thiết kế mạng lưới, quản lý lịch trình và định tuyến.
• Tầm quan trọng đối với ngành: 90% thương mại toàn cầu phụ thuộc vào vận tải biển, nên việc giải quyết bài toán này có tác động kinh tế rất lớn.
• Thách thức kỹ thuật: Để xử lý các bài toán quy mô lớn, cần những kỹ thuật nâng cao như xử lý song song và thu hẹp không gian tìm kiếm.
• Sản phẩm cạnh tranh: Các giải pháp tối ưu hóa khác có chức năng tương tự gồm IBM CPLEX, Gurobi, v.v.
• Điểm cần cân nhắc: Khi áp dụng công nghệ mới có thể phát sinh chi phí thiết lập ban đầu và đường cong học tập. Tuy nhiên, về dài hạn, nó có thể cải thiện đáng kể hiệu quả và lợi nhuận.

[GN⁺]

Ý kiến trên Hacker News

• Ý kiến từ phía terminal: Tối ưu hóa terminal rất phức tạp, và mỗi terminal lại có cách làm khác nhau nên khó mở rộng.
• Đề xuất sách "The Box": Đây là cuốn sách về lịch sử ban đầu của container hóa, là một bài đọc thú vị kết hợp giữa kỹ thuật, thiết kế, kinh doanh và lịch sử.
• Bài toán tối ưu container: Bài toán tối ưu container cho các đội tàu lớn vẫn chưa được giải quyết.
• Cải thiện của Google OR: Google OR cải thiện 10%-20% so với các giải pháp hiện có.
• Việc sử dụng API: Có người đặt câu hỏi liệu có đáng để thử hay không trong bối cảnh chưa tính đến demurrage (phí lưu tàu/chậm bãi).
• Sự tò mò về endpoint API: Có người tò mò liệu có thực sự sử dụng endpoint API do Google cung cấp hay không.
• Đề xuất Omega Tau Podcast: Có một tập rất hay về vận chuyển container và tối ưu hóa.
• Chạy trong Docker container: Chỉ hoạt động khi chạy trong Docker container.
• Đề xuất dùng thuật toán: Có người nghĩ rằng có thể dùng thuật toán để giải bài toán lập lịch cho nhân viên bán thời gian.
• Cung cấp OR-tools như một dịch vụ: Có vẻ như họ đã bắt đầu cung cấp OR-tools dưới dạng dịch vụ. Nếu có API tốt hơn, người dùng sẵn sàng trả chi phí điện toán GCP.
• Thắc mắc về kế hoạch xếp hàng: Kế hoạch xếp hàng là bài toán cần giải ở bước tiếp theo sau lập kế hoạch tuyến đường. Có đưa ra phép tính sơ bộ về tốc độ làm việc của cẩu và quá trình xếp/dỡ.
• Độ phức tạp của kế hoạch xếp hàng: Kế hoạch xếp hàng bao gồm các tiêu chí như trọng lượng, cân bằng, điện năng và khả năng chấp nhận theo giá trị. Vì sự phức tạp này nên đã thử các phép tính đơn giản.