貨物船向けの数理最適化技術
(research.google)- Google ResearchのOperations Researchチームが、定期コンテナ船のネットワーク設計・スケジュール・コンテナ経路を一体で最適化するShipping Network Design APIを公開
- この問題では、船舶の港への寄港順序、到着・出発時刻、コンテナの出発地-目的地経路を同時に決める必要があり、WorldLarge基準で500隻の船舶・200港規模まで複雑化する
- 初期アプローチの二重列生成とCP-SATは小・中規模では証明可能な最適解を見つけたが、大規模問題には大規模近傍探索と可変近傍探索を組み合わせたヒューリスティックが必要だった
- LINERLIBベンチマークでは、WorldSmall、EuropeAsia、Pacific、Mediterraneanのコンテナ取扱量がそれぞれ**35%、14%、35%、32%**増加し、使用船舶数は7%、15%、4%、23%減少
- Googleはこの手法を、WorldLarge規模のネットワーク設計とスケジューリング問題を解ける初の手法と位置づけ、Shipping Network Design APIを今後Operations Research APIsの一部として提供する
コンテナ海運ネットワークを同時に最適化する問題
- 世界中の商品の**90%**は海上輸送で運ばれており、大型貨物船は全長0.25マイル、重量25万トン、1万2000個のコンテナ、総額10億ドル相当の貨物を積載できる
- 貨物船は航空機、列車、トラックとは異なり、ほぼ継続的に運航され、海上で循環ルートに沿って移動する
- 非効率なルートやスケジュールは、コンテナの港湾滞留、船舶の洋上待機、物流の遅延を生み、製品価格にも影響する
- GoogleのShipping Network Design APIは、この問題に対する新しい解法を実装している
- 既知の従来手法より高速で、より高いスケーラビリティを持つ
- コンテナ船社の利益を2倍にし、13%多くのコンテナを輸送し、15%少ない船舶で運用できる
LSNDSPで同時に解くべき3つの意思決定
- Liner Shipping Network Design and Scheduling Problem、すなわちLSNDSPは3つの意思決定を同時に扱う
- ネットワーク設計: 船舶がどの順序で港を訪れるかを決める
- ネットワークスケジュール: 船舶がいつ到着し、いつ出発するかを決める
- コンテナの経路割り当て: コンテナが出発地から目的地までどのような旅程をたどるかを選ぶ
- コンテナ海運会社はこの3つの問題をすべて解かなければならないが、通常は順番に処理する
- 3つを同時に解くと難易度は上がるが、より良い解が得られる可能性が高まる
- ネットワーク設計の結果は、少数の船舶が従うサービスラインにつながる
- たとえば東アジアからスエズ運河を通って南ヨーロッパへ向かうルートなどがある
- サービスラインは日付付きで公開されるため、荷主はいつどこにコンテナを準備すべきかを把握できる
港湾バース、トランシップ、遅延が生む制約
- コンテナ船は望むタイミングで港に接岸できるわけではなく、事前に決められたバーススロットを使わなければならない
- 船舶は港に接近した後、接岸可能になるまで沖待ちで錨を下ろして待機できる
- 港が混雑していれば、沖待ちで数時間から数日間とどまることがある
- 正確なネットワークスケジュールは、単に何日に接岸するかだけでなく、何時に接岸するかまで含む
- 特定の時刻に合わせるために速度を上げることができる
- 燃料節約のために速度を落とす選択も可能
- 港に接岸するとクレーンがコンテナを荷下ろしし、次航海で運ぶコンテナを再び船に積み込む
- スケジュールが遅れると、予定されたコンテナをすべて積み切る前に港を離れるcut-and-runが発生することがある
- 残ったコンテナは後続の船舶が積載することになる
- コンテナが出発地から目的地へ向かう途中の港で時間を過ごすことをトランシップと呼ぶ
- トランシップはLSNDSPにおける可能な解の数をさらに大きく増やす
- コンテナ経路生成に作用する多くの制約の1つである
最適化手法: 列生成から近傍探索まで
- あらゆる最適化問題は、変数、変数に対する制約、最小化または最大化する目的関数で構成される
- 例: 船舶と港は変数
- 例: 船舶に積載できるコンテナ数は制約
- 例: 輸送コンテナ数の最大化は目的関数
- 変数と制約は通常行列で表現され、列は変数、行は制約を表す
- 大規模問題を分解する一般的手法として列生成が使われる
- 最初は変数の一部だけを考慮する
- その後、元の問題をよりよく近似するために新しい変数、すなわち新しい列を生成する
- Googleは問題を分析し、どの列を生成するのが有効かを予測するソフトウェアライブラリを開発した
- このライブラリは、数理プログラミングフレームワークのMathOptを通じてオープンソース公開される予定
2つの基本アプローチの限界
- 二重列生成は、ネットワーク設計とコンテナ経路割り当てを相互に結び付いた2つの問題として捉える
- 各問題は、最適な選択肢を選ぶ主問題と、妥当な選択肢を見つける補助的な生成問題で構成される
- 各問題ペアに最短経路アルゴリズムを適用して妥当な選択肢を生成する
- その後、線形計画ソルバーGlopを使って各問題の最良の選択肢を選ぶ
- 2つの問題に列生成を同時適用し、一方の問題の中間結果が他方の進行に影響するようにする
- 証明可能な最適解を見つけられたが、中規模問題までしかうまくスケールしなかった
- CP-SATベースの実装も試みた
- Googleの制約プログラミングソルバーCP-SATを使用
- 中規模ネットワークまではうまく動作したが、世界規模の海運問題にはスケールしなかった
- どちらのアプローチも小・中規模問題では証明可能な最適解を見つけたが、大規模なスケーラビリティが不足していた
大規模化のためのヒューリスティック
- スケーラビリティを高めるため、既存解の周辺にある近傍を調べて改善機会を探すローカルサーチの派生手法を2つ適用した
- 大規模近傍探索は、解の一部を固定したうえで前述の手法を適用する
- 例: 「この船舶は隔週火曜日にLos Angelesへ寄港する」といった条件を固定する
- 探索空間を縮小し、スケーラビリティを高める
- 可変近傍探索は、ネットワークとスケジュールの両方の近傍を探索する
- 探索を並列化し、複数マシンに分散して多くの近傍を同時に評価する
- 探索空間を制限しつつ、Operations Researchと海運業界の知見を反映できる
- どちらのアプローチも、有望な解の一部を固定し、すでに良い解から出発してさらに良い解へ改善していく漸進的手法を用いる
- 以前の試みでは、問題解決がはるかに難しくなることを理由に輸送時間を考慮していなかったが、Googleは輸送時間を含めることで解の品質が大きく改善することを確認した
LINERLIBベンチマーク結果
- 性能評価には、海運ネットワーク設計問題向けの業界ベンチマークLINERLIBを使用
- ベンチマークには、コンテナ海運シナリオにおける船隊、港、コンテナ需要が含まれる
- テストシナリオにはWorldSmall、EuropeAsia、WorldLargeが含まれる
- WorldLargeには500隻の船舶、200港、約14万個のコンテナが含まれる
- 最適化の目的は、単にコンテナ数の最大化や船舶数の最小化ではない
- コンテナ数だけを最大化すると、より多くの船舶を投入して運用コストが増える可能性がある
- 船舶数だけを最小化すると、1隻で全コンテナを運ぶような非現実的に長い配送時間になる可能性がある
- LINERLIBは、定時配送の収益から航海コストと港湾でのコンテナ取扱コストを差し引いた推定利益でバランスを取る
- ベースラインと比較して、Googleの手法はより少ない船舶でより多くのコンテナを経路割り当てできた
- WorldSmall: コンテナ取扱量35%増、船舶数7%減
- EuropeAsia: コンテナ取扱量14%増、船舶数15%減
- Pacific: コンテナ取扱量35%増、船舶数4%減
- Mediterranean: コンテナ取扱量32%増、船舶数23%減
- LINERLIBの経済的前提に基づけば、想定利益率も大幅に改善する
APIと今後の公開資料
- Googleはこの手法を、WorldLarge規模のネットワーク設計とスケジューリング問題を解ける初の手法と見ている
- 結果の詳細はLSNDSPベンチマークページで確認できる
- Shipping Network Design APIは、今後追加されるOperations Research APIsの1つとなる予定
1件のコメント
Hacker Newsのコメント
自分はこの業界のターミナル側にいるが、面白い一方でかなり学術的に見える
実際に船会社と協業して作ったのか気になる。ターミナル側では今、コンテナ最適化に深く取り組んでいるが、本当に悪夢に近い。同じ会社が所有するターミナル同士でも運用方法が大きく異なり、用語ですら社内で違うことが多い。あるターミナル向けに最適化しても、次のターミナルでは80%を作り直さなければならないので、どんな解法でもスケールさせるのが非常に難しい
たとえばドイツのエンジニアたちは、量産前の車両の機能をロックすることに反発した。余暇で使えなくなるからだ。医療現場では残業コストが数十億円規模に達していて、勤務計画の改善は簡単そうに見えたが、労組の制約が多く、人材供給も不足していた。Googleの解法がどれほど現実的なのか気になる。フーシ派のミサイルのような制約も入るのだろうか。経験上、証明可能な最適解よりも、予想外の変化に容易に適応できる解法のほうが価値があることが多かった
客観的な最適化が概して学術的だという点には同意する。標準化されたプロセスの最も効率的な版をそのまま守るのが難しい、あるいは不可能な理由は常にある。ときには人間のせいで生じる「ばかげた」理由だし、しばしば天候・ダウンタイム・サプライチェーンの寸断・季節性による需要シグナルと予測の凸凹といった外部要因を反映した合理的な理由でもある。それでも、既知の例外を基準に標準プロセスを作るより、最も効率的なプロセスから始めて例外処理を付け足すほうが、ほぼ常に良いと思う。例外をルールにしてしまうと、最適より常に低い効率で運用することになる
この業界は難しく、港湾労働者の労組が伝統的に強いので、政治的な地形はさらに難しい。きれいに切り分けて名前を付けられる問題も、現実には互いに絡み合っていて、アルゴリズムがユーザーのために「魔法のように」解いてくれると期待すると、ほぼ確実に失敗する。「要するに巡回セールスマン問題 / 制約ソルバー / 好きなアプローチを回せばいいんでしょ？」と考えて飛び込むソフトウェア強者を、この業界は簡単にのみ込む。賢い人材は確かに必要だが、謙虚に始めて、まず実際のユーザーと話すべきだ。プロフィールに連絡先がないように見えるが、この業界の他社と考えを共有したいならメールしてほしい。特に複合輸送の比率が高い年間100万TEU未満のターミナルのセグメントで面白いことをやっている
コンテナ化初期の歴史を扱ったThe Boxを読んでいるが、本当に面白い
工学、設計、ビジネス、歴史が混ざった楽しい読み物を探している人に強く勧めたい。自分が直面している小さなコーディングの問題が滑稽に思えてくることもある
反論が多く出そうだが、本気で言うと、20フィート海上コンテナが世界に与えた影響は、大規模言語モデルが今後達成しうる影響より大きかったと思う。まずその本を読んで、なぜ自分が間違っているのか言ってほしい。もちろん自分は間違っていないが
非常に大きな船団ではコンテナ最適化がまだ未解決の問題だったようだ。知らなかった
Google のオペレーションズ・リサーチが既存の解法に比べて利用率を10〜20%改善したなら、驚異的だ
https://en.wikipedia.org/wiki/Packing_problems
公開されたこの API エンドポイントを実際に使っているところがあるのか、とても気になる: https://developers.google.com/optimization/service/shipping/...
それでもかなりクールだ
代表例として、Route Optimization API も企業向けオペレーションズ・リサーチチームがこのような形で公開し、その後いくつかのアルファ顧客からの入力を受けて、その上に Fleet Engine ソリューションが作られた。オペレーションズ・リサーチ API が Google Cloud 経由で公開されるまでは、SLA や信頼性保証がないので、学術用途以外では使わないほうがよいと思う。以上、自分の2セント
https://developers.google.com/maps/documentation/transportat...
[1]: https://killedbygoogle.com/
滞船料が考慮されていないなら、本当に試す価値があるのか分からない
https://developers.google.com/optimization/service/reference...
Omega Tau Podcast がコンテナ海運について非常に良いエピソード[0]を出していて、コンテナ配置の最適化や経路計画も扱っている。強くおすすめする
[0]: https://omegataupodcast.net/146-container-shipping/
「飛行機と違って貨物船はほぼずっと運航している」という表現は、少し検討の余地がある
貨物船は航海中に多くの保守作業を行うが、それ以外の違いはずっと小さいと思う。港では何日もかけて荷下ろしと積み込みをして回し、バース待ちで数時間から数日待機することもある。Delta A350 の事例を見ると、空港での3時間のターンアラウンド時間を除けば、実質的には24時間ずっと動いている: https://www.flightradar24.com/data/aircraft/n513dz
近所の飲食店のような場所で、店主やマネージャーがアルバイトのシフト作成に頭を抱え、それが高い給料をもらう理由だとまで言うのを思い出す
アルゴリズムで解けるのではないかと思っていた
従業員の半分が Taylor Swift を見に行った夜の穴を埋めることはできるかもしれないが、そうやって人を呼び出すと、その人たちの次の勤務もまた誰かが埋めなければならず、それが続くと、一度も一緒に働いたことのない人たちだけでまったく別のシフト表ができあがってしまう。制約を追加すれば修正はできるが、それをすべて書き出して優先順位を付けるだけでも簡単ではない。人は レゴブロック ではない
オペレーションズ・リサーチの背景があるので、いつも不思議に感じる。問題は一般的なソルバーでモデル化して解くには単純に見え、高度な手法がなくても価値は大きそうだ。問題は、オペレーションズ・リサーチ全般の敷居が高いことにある。よくサポートされたソルバーの多くは、数学的パラダイムで問題を定義することを求めるが、「普通の人」はそれを見ただけで圧倒される。よくあるシフト問題向けの既製ソリューションもあるが、最初からそれを使っていなければ、各事業所には固有の変種があるため完全導入が難しい。その変種をサポートしていないか、ツールの中にどう押し込めばいいのか分からない。シフトをもっと上手く解こうという意思があっても、見つかる講座はたいてい相当なプログラミングか数学の事前知識を前提にしている。Excel では足りないがオペレーションズ・リサーチの専門家を雇えない「普通の人」でも使える、シフト問題向けの ノーコードのモデリング環境 を作れるはずだと思う
ほぼすべての大規模 HR / 人員管理システムに関連オプションが入っている。たとえば https://www.workday.com/en-us/products/workforce-management/... や https://www.oracle.com/human-capital-management/workforce-ma... があり、専業ベンダーも多い。ただし、他の人が言っているように、こうしたシステムには論争もあった。正常な人間的必要を考慮しない形で使われることがあるためだ。たとえば連続勤務を割り当てたり、短い通知でシフトを変更したり、人間のマネージャーなら反映できる育児のような現実事情を考慮できなかったりすることがある
しかし問題は、各事業所ごとに制約が異なることだ。1つのシフトに応急手当ができる人が最低1人必要だとか、Alice と Bob は仲が悪いとか、土曜日を2週連続で働いてはいけないとか、シフトが2週間ごとに変わるとか、勤務の間に最低12時間必要だとか、そういうものだ。かなりの数の組織が使えるだけの柔軟性を持つツールは、結局は複雑すぎて使いにくくなる気がする
このような船舶の 積み付け計画 がまだ気になっている。
各コンテナの経路計画の次の段階で近似的に解くべき問題のように思える。積み付け計画は後で出てきて、グローバルなシステムレベルの観点よりもはるかに状況依存の制約を持つ。おおまかに楽観的に見ても、岸壁クレーンは1時間に30〜50回移動し、船舶1隻あたり2台または4台、多ければ6台が付き、殻をむくように層ごとに解かなければならない。Ultra Large Container Vessel は 14,501 TEU 以上、New Panamax は 10,000〜14,500 TEU、Post-Panamax は 5,101〜10,000 TEU、Panamax は 3,001〜5,100 TEU である。24,000 TEU を40フィートコンテナ1.2万本とすると、4台 × クレーン1台あたり1時間50本 × 1日24時間 = 1日あたり約1,200本のコンテナになる。
https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
船舶の積み付け計画には、港での利用可能性のほかにも、重量、バランス、電力、貨物価値の許容基準がある。記事で港からの早期出航に触れていたので、このようなオーバーヘッドが気になり、おおまかな計算をしてみた。
実際にこの分野に関わっている立場から見ると、自分で仕事を楽にする方法は多い。ハッチカバーごとのブロック単位で計画し、コンテナを目的地・サイズ・重量ごとにまとめて代替可能なものとして扱うのは基本だ。その後、作業開始前に船舶からターミナルへ計画を送れば、ターミナル側もヤード内のコンテナ位置を把握しているので、最適化や再配置ができる。各コンテナの詳細を無視してグループだけに注目すると決めれば、積み付け計画ははるかに容易になる。はるかに少ない作業で結果は非常によく似たものになり、ターミナルが運用を最適化する柔軟性もさらに高まる。