Công nghệ tối ưu hóa toán học cho tàu chở hàng
(research.google)- Nhóm Operations Research của Google Research đã công bố Shipping Network Design API, tối ưu hóa đồng thời thiết kế mạng lưới·lịch trình·định tuyến container cho tàu container chạy tuyến cố định
- Bài toán này phải đồng thời xác định thứ tự tàu ghé cảng, thời gian đến·rời cảng, và lộ trình từ điểm đi đến điểm đến của container, nên trở nên cực kỳ phức tạp ở quy mô 500 tàu·200 cảng theo chuẩn WorldLarge
- Cách tiếp cận ban đầu gồm sinh cột kép và CP-SAT đã tìm được nghiệm tối ưu có thể chứng minh ở quy mô nhỏ và vừa, nhưng với bài toán lớn thì cần heuristic kết hợp large neighborhood search và variable neighborhood search
- Trên benchmark LINERLIB, lưu lượng xử lý container của WorldSmall, EuropeAsia, Pacific và Mediterranean tăng lần lượt 35%, 14%, 35%, 32%, còn số tàu sử dụng giảm 7%, 15%, 4%, 23%
- Google xem đây là phương pháp đầu tiên có thể giải bài toán thiết kế mạng lưới và lịch trình ở quy mô WorldLarge, và sẽ cung cấp Shipping Network Design API như một phần của Operations Research APIs trong tương lai
Bài toán tối ưu hóa đồng thời mạng lưới vận tải container đường biển
- 90% hàng hóa toàn cầu được vận chuyển bằng đường biển, và một tàu chở hàng cỡ lớn có thể dài 0,25 dặm, nặng 250.000 tấn, chở 12.000 container, với tổng giá trị hàng hóa lên tới 1 tỷ USD
- Khác với máy bay, tàu hỏa hay xe tải, tàu chở hàng gần như vận hành liên tục và di chuyển theo tuyến vòng lặp trên biển
- Tuyến đi và lịch trình kém hiệu quả làm container lưu lại cảng lâu hơn, tàu phải chờ ngoài khơi, dòng logistics bị chậm trễ và cuối cùng ảnh hưởng đến giá sản phẩm
- Shipping Network Design API của Google hiện thực hóa một lời giải mới cho bài toán này
- Nhanh hơn và mở rộng tốt hơn các cách tiếp cận đã biết trước đây
- Có thể giúp hãng tàu container tăng gấp đôi lợi nhuận, vận chuyển thêm 13% container và vận hành với ít hơn 15% số tàu
Ba quyết định mà LSNDSP phải giải cùng lúc
- Liner Shipping Network Design and Scheduling Problem, tức LSNDSP, xử lý đồng thời ba quyết định
- Thiết kế mạng lưới: quyết định tàu sẽ ghé các cảng theo thứ tự nào
- Lập lịch mạng lưới: xác định thời điểm tàu đến và rời cảng
- Định tuyến container: chọn hành trình mà container sẽ đi từ nơi xuất phát đến nơi đích
- Các hãng vận tải container đều phải giải cả ba bài toán này, nhưng thường xử lý theo tuần tự
- Giải đồng thời cả ba làm độ khó tăng lên, nhưng cũng tăng khả năng tìm được nghiệm tốt hơn
- Kết quả của thiết kế mạng lưới dẫn tới các service line mà một số ít tàu sẽ cùng khai thác
- Ví dụ, đó có thể là tuyến từ Đông Á qua kênh đào Suez đến Nam Âu
- Service line được công bố kèm ngày cụ thể để chủ hàng biết khi nào và ở đâu cần chuẩn bị container
Các ràng buộc do cập cảng, trung chuyển và chậm trễ tạo ra
- Tàu container không thể cập cảng bất cứ lúc nào mong muốn mà phải dùng berthing slot được sắp trước
- Sau khi tiếp cận cảng, tàu có thể neo chờ ở khu neo ngoài khơi cho tới thời điểm được phép cập bến
- Nếu cảng tắc nghẽn, tàu có thể phải chờ ở đó nhiều giờ hoặc nhiều ngày
- Lịch trình mạng lưới chính xác không chỉ là cập bến vào ngày nào mà còn là cập bến vào giờ nào
- Tàu có thể tăng tốc để kịp một mốc thời gian cụ thể
- Hoặc giảm tốc để tiết kiệm nhiên liệu
- Khi cập cảng, cần cẩu sẽ dỡ container xuống và lại xếp lên tàu các container cho chặng tiếp theo
- Nếu lịch bị trễ, có thể xảy ra hiện tượng cut-and-run, tức tàu rời cảng trước khi kịp xếp hết số container đã lên kế hoạch
- Các container còn lại sẽ được tàu sau chở đi
- Trường hợp container lưu lại tại một cảng trung gian trong hành trình từ điểm đi tới điểm đến được gọi là trung chuyển
- Trung chuyển làm số lượng nghiệm khả dĩ của LSNDSP tăng mạnh hơn nữa
- Đây là một trong nhiều ràng buộc tác động đến việc tạo tuyến cho container
Phương pháp tối ưu hóa: từ sinh cột đến tìm kiếm lân cận
- Mọi bài toán tối ưu hóa đều gồm biến, ràng buộc áp lên biến, và hàm mục tiêu cần tối thiểu hóa hoặc tối đa hóa
- Ví dụ: tàu và cảng là biến
- Ví dụ: số container có thể xếp lên tàu là ràng buộc
- Ví dụ: tối đa hóa số container được vận chuyển là hàm mục tiêu
- Biến và ràng buộc thường được biểu diễn bằng ma trận, trong đó cột là biến và hàng là ràng buộc
- Một kỹ thuật phổ biến để phân rã bài toán lớn là sinh cột
- Ban đầu chỉ xét một phần các biến
- Sau đó sinh thêm biến mới, tức các cột mới, để xấp xỉ bài toán gốc tốt hơn
- Google đã phát triển một thư viện phần mềm dự đoán nên sinh những cột nào sau khi phân tích bài toán
- Thư viện này dự kiến sẽ được mã nguồn mở qua MathOpt, một framework lập trình toán học
Giới hạn của hai cách tiếp cận cơ bản
- Sinh cột kép xem thiết kế mạng lưới và định tuyến container là hai bài toán gắn kết với nhau
- Mỗi bài toán gồm một bài toán chính để chọn phương án tốt nhất và một bài toán phụ để sinh ra các phương án hợp lý
- Thuật toán đường đi ngắn nhất được áp dụng cho từng cặp bài toán để sinh phương án hợp lý
- Sau đó bộ giải quy hoạch tuyến tính Glop được dùng để chọn phương án tốt nhất cho từng bài toán
- Sinh cột được áp dụng đồng thời cho cả hai bài toán, để kết quả trung gian của bài toán này ảnh hưởng đến tiến trình của bài toán kia
- Cách này tìm được nghiệm tối ưu có thể chứng minh, nhưng chỉ mở rộng tốt tới các bài toán cỡ trung bình
- Google cũng thử một triển khai dựa trên CP-SAT
- Sử dụng bộ giải lập trình ràng buộc CP-SAT của Google
- Hoạt động tốt tới các mạng lưới cỡ trung bình nhưng không mở rộng được tới quy mô bài toán vận tải biển toàn cầu
- Cả hai cách tiếp cận đều tìm được nghiệm tối ưu có thể chứng minh ở quy mô nhỏ và vừa, nhưng thiếu khả năng mở rộng cho quy mô lớn
Heuristic để mở rộng lên quy mô lớn
- Để tăng khả năng mở rộng, Google áp dụng hai biến thể của tìm kiếm cục bộ, tức tìm cơ hội cải thiện bằng cách xem xét lân cận của nghiệm hiện có
- Large neighborhood search áp dụng các phương pháp nói trên sau khi cố định một phần nghiệm
- Ví dụ: cố định điều kiện như “tàu này ghé Los Angeles vào thứ Ba cách tuần”
- Việc này thu hẹp không gian tìm kiếm để cải thiện khả năng mở rộng
- Variable neighborhood search khám phá lân cận ở cả phía mạng lưới lẫn lịch trình
- Việc tìm kiếm được song song hóa và phân tán trên nhiều máy để đánh giá nhiều lân cận cùng lúc
- Cách này vừa giới hạn không gian tìm kiếm vừa phản ánh tri thức từ Operations Research và ngành vận tải biển
- Cả hai đều dùng cách tiếp cận tăng dần, khóa lại một phần của nghiệm hứa hẹn và cải thiện dần từ nghiệm đã tốt sang nghiệm tốt hơn
- Các thử nghiệm trước đây không xét đến thời gian vận chuyển vì sẽ khiến bài toán khó hơn nhiều, nhưng Google xác nhận rằng đưa yếu tố này vào giúp chất lượng nghiệm cải thiện đáng kể
Kết quả benchmark LINERLIB
- Đánh giá hiệu năng sử dụng LINERLIB, benchmark công nghiệp cho bài toán thiết kế mạng lưới vận tải biển
- Benchmark này bao gồm đội tàu, cảng và nhu cầu container của các kịch bản vận tải biển container
- Các kịch bản thử nghiệm gồm WorldSmall, EuropeAsia và WorldLarge
- WorldLarge bao gồm 500 tàu, 200 cảng và khoảng 140.000 container
- Mục tiêu tối ưu hóa không đơn giản chỉ là tối đa hóa số container hay tối thiểu hóa số tàu
- Nếu chỉ tối đa hóa số container, có thể phải đưa thêm nhiều tàu vào khai thác làm tăng chi phí vận hành
- Nếu chỉ tối thiểu hóa số tàu, có thể xuất hiện thời gian giao hàng dài phi thực tế, chẳng hạn một tàu chở toàn bộ container
- LINERLIB cân bằng các yếu tố này bằng lợi nhuận ước tính, lấy doanh thu giao hàng đúng hạn trừ chi phí hành hải và chi phí xử lý container tại cảng
- So với baseline, phương pháp của Google định tuyến được nhiều container hơn với ít tàu hơn
- WorldSmall: lưu lượng container tăng 35%, số tàu giảm 7%
- EuropeAsia: lưu lượng container tăng 14%, số tàu giảm 15%
- Pacific: lưu lượng container tăng 35%, số tàu giảm 4%
- Mediterranean: lưu lượng container tăng 32%, số tàu giảm 23%
- Dựa trên các giả định kinh tế của LINERLIB, tỷ suất lợi nhuận kỳ vọng cũng được cải thiện đáng kể
API và tài liệu công bố tiếp theo
- Google xem đây là phương pháp đầu tiên có thể giải bài toán thiết kế mạng lưới và lịch trình ở quy mô WorldLarge
- Có thể xem chi tiết hơn kết quả tại trang benchmark LSNDSP
- Shipping Network Design API là một trong các Operations Research APIs sẽ được bổ sung trong thời gian tới
1 bình luận
Ý kiến trên Hacker News
Tôi làm ở phía terminal trong ngành này; khá thú vị nhưng trông rất hàn lâm
Tôi khá tò mò không biết nó có thực sự được làm cùng với các hãng tàu hay không. Ở phía terminal, hiện tại chúng tôi đang đào rất sâu vào tối ưu hóa container và nó thực sự gần như là ác mộng. Ngay cả giữa các terminal cùng thuộc một công ty thì cách vận hành cũng khác nhau rất nhiều, và ngay cả thuật ngữ cũng thường khác nhau trong nội bộ công ty. Tối ưu hóa cho một terminal xong thì sang terminal tiếp theo lại phải làm lại 80%, nên bất kỳ lời giải nào cũng rất khó mở rộng quy mô
Ví dụ, các kỹ sư Đức từng phản đối việc khóa tính năng của xe trước khi đưa vào sản xuất hàng loạt, vì như vậy họ không thể dùng xe đó cho mục đích giải trí. Trong lĩnh vực y tế, chi phí làm thêm giờ lên tới hàng tỷ nên việc cải thiện lịch trực có vẻ dễ, nhưng lại có rất nhiều ràng buộc công đoàn và nguồn cung tuyển dụng cũng thiếu. Tôi tò mò không biết giải pháp của Google thực tế đến đâu. Nó có tính cả những ràng buộc như tên lửa Houthi không? Theo kinh nghiệm của tôi, đôi khi một lời giải dễ điều chỉnh trước những thay đổi bất ngờ còn giá trị hơn một nghiệm tối ưu có thể chứng minh được
Tôi đồng ý rằng tối ưu hóa khách quan phần lớn mang tính học thuật. Luôn có lý do khiến việc bám sát phiên bản hiệu quả nhất của một quy trình đã được chuẩn hóa là khó hoặc bất khả thi. Đôi khi đó là những lý do “ngớ ngẩn” do con người tạo ra, và cũng thường là những lý do hợp lý phản ánh các yếu tố ngoại sinh như thời tiết, thời gian ngừng máy, gián đoạn chuỗi cung ứng, hay độ gồ ghề của tín hiệu nhu cầu và dự báo theo mùa vụ. Dù vậy, tôi gần như luôn cho rằng tốt hơn là bắt đầu từ quy trình hiệu quả nhất rồi gắn xử lý ngoại lệ vào, thay vì xây quy trình chuẩn dựa trên các ngoại lệ đã biết. Nếu để ngoại lệ trở thành quy tắc, bạn sẽ luôn vận hành kém hiệu quả hơn mức tối ưu
Ngành này rất khó, và các công đoàn lao động cảng truyền thống vốn rất mạnh nên bức tranh chính trị còn khó hơn. Những bài toán có thể được chia tách gọn gàng và đặt tên rõ ràng trên lý thuyết thì trên thực tế lại quấn chặt vào nhau, và nếu kỳ vọng thuật toán sẽ “thần kỳ” giải quyết thay người dùng thì gần như chắc chắn thất bại. Ngành này rất dễ nuốt chửng những cao thủ phần mềm nhảy vào với suy nghĩ kiểu “chẳng phải chỉ là bài toán người bán hàng rong / bộ giải ràng buộc / cứ chạy cách tiếp cận mình thích là xong sao?”. Rõ ràng là cần người thông minh, nhưng phải bắt đầu một cách khiêm tốn và nói chuyện với người dùng thật trước. Tôi không thấy thông tin liên hệ trong hồ sơ; nếu bạn muốn trao đổi ý tưởng với một công ty khác trong ngành này, hãy gửi email cho tôi. Chúng tôi đang làm một số việc thú vị, đặc biệt trong phân khúc terminal dưới 1 triệu TEU/năm với tỷ trọng vận tải đa phương thức cao
Tôi đang đọc The Box, viết về lịch sử giai đoạn đầu của container hóa, và nó thực sự rất hay
Rất đáng đọc cho bất kỳ ai muốn tìm một cuốn sách thú vị kết hợp giữa kỹ thuật, thiết kế, kinh doanh và lịch sử. Nó cũng khiến những vấn đề lập trình nhỏ nhặt tôi đang gặp phải trông thật buồn cười
Có lẽ sẽ bị phản đối nhiều, nhưng nói thật lòng thì tôi cho rằng container vận tải biển 20 foot đã tạo ra tác động lên thế giới còn lớn hơn tác động mà các mô hình ngôn ngữ lớn có thể đạt được trong tương lai. Hãy đọc cuốn sách đó trước rồi quay lại nói tôi sai ở đâu. Dĩ nhiên là tôi không sai
Có vẻ như với các đội tàu rất lớn, tối ưu hóa container vẫn là một bài toán chưa có lời giải. Tôi không biết điều đó
Nếu bộ phận nghiên cứu tác nghiệp của Google đã cải thiện mức độ tận dụng thêm 10–20% so với các giải pháp hiện có thì đó là mức cực kỳ ấn tượng
https://en.wikipedia.org/wiki/Packing_problems
Tôi thực sự rất tò mò không biết có nơi nào dùng endpoint API công khai này ngoài đời thật không: https://developers.google.com/optimization/service/shipping/...
Dù sao thì nó cũng khá ngầu
Ví dụ điển hình là Route Optimization API cũng được một nhóm nghiên cứu tác nghiệp trong doanh nghiệp công bố theo cách như vậy, rồi sau đó dựa trên đầu vào của một vài khách hàng alpha mà giải pháp Fleet Engine được xây dựng trên đó. Trước khi các API nghiên cứu tác nghiệp được đưa ra qua Google Cloud, tôi nghĩ tốt hơn là không nên dùng chúng ngoài mục đích học thuật, vì sẽ không có SLA hay đảm bảo về độ tin cậy. Chỉ là ý kiến cá nhân của tôi thôi
https://developers.google.com/maps/documentation/transportat...
[1]: https://killedbygoogle.com/
Nếu không tính phí lưu tàu, thì tôi không chắc việc này có thực sự đáng để thử hay không
https://developers.google.com/optimization/service/reference...
Omega Tau Podcast có một tập[0] rất hay về vận chuyển container, cũng đề cập đến tối ưu hóa sắp xếp container và lập kế hoạch tuyến đường. Rất đáng nghe
[0]: https://omegataupodcast.net/146-container-shipping/
Cách nói “không giống máy bay, tàu hàng gần như chạy liên tục” có hơi cần xem xét lại
Tàu hàng đúng là làm khá nhiều bảo trì trong lúc hải hành, nhưng ngoài ra tôi nghĩ khác biệt nhỏ hơn nhiều. Ở cảng, chúng quay vòng trong vài ngày để dỡ và xếp hàng, và cũng có thể phải chờ vài giờ hoặc vài ngày để đợi cầu cảng. Nhìn vào trường hợp chiếc Delta A350 thì nếu bỏ 3 giờ quay vòng ở sân bay, nó thực tế cũng di chuyển gần như 24/24: https://www.flightradar24.com/data/aircraft/n513dz
Điều này làm tôi nhớ đến chuyện chủ hoặc quản lý những nơi như quán ăn trong khu phố hay than phiền rằng việc xếp lịch cho nhân viên làm thêm rất đau đầu, thậm chí còn nói đó là lý do họ được trả lương cao
Tôi từng nghĩ chẳng phải có thể giải bằng thuật toán sao
Có thể bạn lấp được ca tối mà một nửa nhân viên đi xem Taylor Swift, nhưng nếu cứ gọi người như vậy vào làm thì ca sau của những người đó lại phải được ai khác lấp vào, và cứ thế tiếp diễn thì cuối cùng sẽ tạo ra một bảng lịch hoàn toàn khác với những người thậm chí chưa từng làm cùng nhau. Có thể sửa bằng cách thêm nhiều ràng buộc hơn, nhưng chỉ riêng việc viết ra hết và xếp thứ tự ưu tiên cho chúng cũng đã không đơn giản. Con người không phải khối Lego
Tôi có nền tảng về nghiên cứu tác nghiệp nên chuyện này luôn thấy khá lạ. Các bài toán này có vẻ đủ đơn giản để mô hình hóa và giải bằng solver thông dụng, và giá trị mang lại dường như rất lớn ngay cả không cần kỹ thuật cao cấp. Vấn đề là nghiên cứu tác nghiệp nói chung khá khó tiếp cận. Hầu hết các solver được hỗ trợ tốt đều yêu cầu định nghĩa bài toán theo một mô hình toán học, và “người bình thường” sẽ thấy choáng ngay từ cái nhìn đầu tiên. Cũng có các giải pháp dựng sẵn cho bài toán lịch phổ biến, nhưng nếu không dùng ngay từ đầu thì mỗi nơi làm việc lại có những biến thể riêng nên rất khó triển khai trọn vẹn. Hoặc là chúng không hỗ trợ biến thể đó, hoặc không ai biết phải nhét nó vào công cụ như thế nào. Dù có ý muốn giải lịch tốt hơn thì các khóa học tìm được thường cũng giả định sẵn kiến thức lập trình hoặc toán học ở mức khá. Tôi nghĩ lẽ ra phải có thể tạo ra một môi trường mô hình hóa no-code cho bài toán xếp lịch mà “người bình thường” dùng được — những người đã vượt quá khả năng của Excel nhưng cũng không thể thuê chuyên gia nghiên cứu tác nghiệp
Gần như mọi hệ thống HR/quản lý nhân sự lớn đều có tùy chọn liên quan. Ví dụ có https://www.workday.com/en-us/products/workforce-management/... và https://www.oracle.com/human-capital-management/workforce-ma..., ngoài ra còn nhiều nhà cung cấp chuyên biệt khác. Tuy vậy, như người khác đã nói, các hệ thống này cũng từng gây tranh cãi. Một phần vì chúng được dùng theo cách không tính đến những nhu cầu bình thường của con người. Ví dụ như xếp các ca làm liền nhau, đổi lịch với thông báo quá gấp, hoặc không tính đến những hoàn cảnh thực tế như chăm con mà một quản lý con người có thể cân nhắc
Nhưng vấn đề là mỗi nơi làm việc lại có ràng buộc khác nhau. Ví dụ như trong một ca phải có ít nhất 1 người biết sơ cứu, hoặc Alice và Bob không hợp nhau, hoặc không được làm thứ Bảy hai tuần liên tiếp, hoặc ca làm thay đổi mỗi 2 tuần, hoặc phải có ít nhất 12 giờ nghỉ giữa các ca, v.v. Một công cụ đủ linh hoạt để nhiều tổ chức sử dụng có lẽ cuối cùng sẽ quá phức tạp nên khó dùng
Vẫn còn tò mò về kế hoạch xếp hàng của những con tàu như thế này.
Có vẻ đây là một bài toán cần được giải gần đúng ở bước tiếp theo sau khi lập kế hoạch tuyến đường cho từng container. Kế hoạch xếp hàng xuất hiện muộn hơn và có các ràng buộc phụ thuộc tình huống nhiều hơn hẳn so với góc nhìn ở cấp độ hệ thống toàn cục. Ước tính lạc quan thì cẩu bờ di chuyển 30–50 lần mỗi giờ, mỗi tàu có 2 hoặc 4 cẩu, nhiều thì 6 cẩu, và phải dỡ theo từng lớp như bóc vỏ. Ultra Large Container Vessel là từ 14.501 TEU trở lên, New Panamax là 10.000–14.500 TEU, Post-Panamax là 5.101–10.000 TEU, còn Panamax là 3.001–5.100 TEU. Nếu coi 24.000 TEU tương đương 12.000 container 40 feet, thì 4 cẩu × 50 container mỗi giờ cho mỗi cẩu × 24 giờ một ngày = khoảng 1.200 container mỗi ngày.
https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
Ngoài khả dụng tại cảng, kế hoạch xếp hàng trên tàu còn có các tiêu chí về trọng lượng, cân bằng, điện năng và mức chấp nhận theo giá trị hàng hóa. Bài viết có nhắc đến việc tàu rời cảng sớm nên tôi tò mò về các chi phí phụ trội này và đã thử tính sơ bộ.
Từ góc nhìn của người thực sự tham gia vào lĩnh vực này thì có nhiều cách để tự làm cho công việc dễ hơn. Lập kế hoạch theo khối cho từng nắp hầm hàng, rồi gom container theo điểm đến, kích thước và trọng lượng để coi chúng là có thể thay thế cho nhau, là cách làm cơ bản. Sau đó, nếu gửi kế hoạch từ tàu sang terminal trước khi bắt đầu công việc, terminal cũng biết vị trí container trong bãi nên có thể tối ưu hóa và sắp xếp lại. Nếu quyết định bỏ qua chi tiết của từng container và chỉ tập trung vào các nhóm, thì kế hoạch xếp hàng sẽ dễ hơn rất nhiều. Khối lượng công việc ít hơn nhiều nhưng kết quả rất tương tự, đồng thời terminal cũng có thêm độ linh hoạt để tối ưu hóa vận hành.