💡要約
- 農薬散布のルート作成を組合せ最適化問題として定式化
- Rust でヒューリスティクスソルバを実装
- 実際の運用を見据えると、最適化ソルバの実装だけでは不十分
- 最適化モデルの精度、入力データの精度、最適化ソルバの性能のバランスが大事
🌅はじめに
こんにちは、R&D の河内です。最近は農業と最適化に取り組んでいます。
この記事では、2024年に弊社が取り組んだ組合せ最適化の事例について紹介します。
私は過去に高専プロコンや AtCoder などのヒューリスティクス系の競技プログラミングに触れてきました。社内では ID 基盤の OPTiM ID の開発や、測量アプリ Geo Scan の研究開発を経験してきましたが、業務で組合せ最適化に取り組むのは今回が初めてでした。
この開発プロジェクトは、私に加え、Rust に精通したエンジニア2名との計3名体制で進めてきました。
最新の AI 技術ではありませんが、最適化問題のモデリング、Rust によるソルバ実装、パフォーマンスチューニング… などなどエンジニアリングの視点でも面白い内容だと思いますので、ぜひこの記事を通して関連技術に興味を持っていただけたらと思います。
- 💡要約
- 🌅はじめに
- 🌾ドローン農薬散布×組合せ最適化
- 🤔最適化問題を作る
- 🏗️最適化問題のインスタンスを作る仕組みを作る
- 🦀Rust で最適化ソルバを作る
- ⚡高速化
- 🎚️最適化のチューニング
- 🌐Web システムとの連携
- 🏃💨初期の運用とバックアッププラン
- 📚おわりに
🌾ドローン農薬散布×組合せ最適化
オプティムではドローンで農薬を散布するサービス、ピンポイントタイム散布 (PTS) を提供しています。
サービスの概要については、以下の動画をご覧ください。
ドローン散布サービスでは、事前の計画が重要です。 事前に計画しておくべきことはいくつかありますが、その一つが当日の散布計画です。
ドローン散布では、 複数のパイロット が対象地域の圃場群を分担し散布作業を行います。 そのため、当日の散布計画においては
- いつ、誰が、どの順番で圃場を散布するのか
- 指定された時刻までに散布が完了できるか
- 十分な人数のパイロットが割り当てられているか
- 散布ルートは無駄が無いか
- 各パイロットの散布エリアが近接しすぎていないか
など…考慮すべき点は多岐にわたります。
この当日散布計画を自動化するために、2024年度では 組合せ最適化による自動化 を導入しました。 組合せ最適化を解くためのアプローチはいくつかありますが、大規模な入力も現実的な時間で解くため、ヒューリスティクスな手法 (経験則に基づく近似解法) を採用しています。
🤔最適化問題を作る
最適化の実装に取り掛かる前に、何を最適化すれば良いのか？について明らかにする必要がありました。
ざっくりですが、以下の役割分担で 散布作業のモデル と 解くべき最適化問題 を設計しました。
- 散布作業をモデリング、解の要求を整理 (企画チーム)
- 実装できそうな形に調整、定式化 (R&D チーム)
企画チームは実際の散布現場も経験しており、散布作業に関してはプロフェッショナルです。 当初は一般的な VRP (Vehicle Routing Problem) の枠組みに落とし込めないか考えていましたが、 企画チームとの議論で散布作業固有の特性が明らかになり、独自の最適化問題を定義しました。
ちなみに、私も散布現場を見学しました。(散布用ドローンは大迫力…!)
初期検討の過程では以下を実施しました。
- 既存のツールや商用ソルバの検討
- Python によるプロトタイプ実装
プロトタイプ実装は簡易的なソルバだけでなく、シミュレータや可視化の機能も含んでいます。
特に可視化機能は役立ったと感じています。 可視化のおかげで、何を最適化すべきかについて企画チームとうまく議論できるようになりました。
Python によるプロトタイプ実装においては、以下のパッケージを活用しました。
- OSMnx: OpenStreetMap からのデータ取得
- NetworkX: 道路ネットワークの解析
- Shapely: 圃場ポリゴン、道路ネットワークの解析
- utm: 座標系の変換
- folium: 地図タイル、ポリゴンの可視化
- altair: シミュレーション結果の可視化
最終的に、最適化問題を定式化し、以下の内容をドキュメントに整理しました。
* 問題の概要 * 用語 * 入力 * 出力 * 最適化問題 * 定数 (入力) * 決定変数 * 目的関数 * 制約条件 * 補足 * 例 * 小さな問題インスタンスの例 * 実行可能解の例 * 実行不可能な例
このドキュメントでは、最適化に詳しくないメンバも理解できるように概要を記載しつつ、基本的に数式で最適化問題を定義しています。 ただし数式で完全に表現することは目指さず、一部の関数や制約は日本語で定義し、実装方法についてはある程度柔軟に対応する方針としています。
また、例として散布作業において NG な解の例、避けたい解の例を記載しています。 解の例の図はプロトタイプの可視化結果と同等の表現を採用することで、理解しやすい形を目指しました。
🏗️最適化問題のインスタンスを作る仕組みを作る
最適化問題はあくまで問題を定義しただけなので、最適化を運用する上では現実のデータを最適化問題の定義に従って変換する必要があります。
データを変換し最適化できる形式に整えたものを、問題インスタンスと呼びます。
現実のデータ ↓ (最適化問題の定義に従い変換) 問題インスタンス ↓ (ソルバにより最適化) 最適解
散布ルートの最適化における現実のデータとは、主に以下のようなものです。
- 散布計画に関するデータ (制限時間など)
- 散布対象の圃場ポリゴン群
- 散布に割り当てられたパイロットのデータ
- 散布対象地域の道路ネットワークデータ
これらを元データとして問題インスタンスを生成する…のですが、この変換処理の設計や検討にはかなりの時間を割きました。
おそらく最適化問題の定義よりも時間がかかったと思います。 というのも、今回の散布作業モデルは最適化問題側ではなくこの変換処理側で考慮しなければならない点が多かったからです。
問題インスタンスの設計においては、最適化問題だけを考えれば良いというわけではなく、モデリングやシステム全体を考慮した設計が必要でした。
🦀Rust で最適化ソルバを作る
問題インスタンスが用意できれば、あとは目的関数と制約に従って最適化するだけです。
今回の最適化問題は構造としては VRP と近しいため、初期検討においては以下の選択肢を検討しました。
しかし OR-Tools は解きたい問題の規模に対応できず、VROOM は散布作業モデルをそのまま表現することはできませんでした。
最終的には VROOM の設計を一部参考にしつつ、局所探索法ベースの最適化手法をフルスクラッチで実装する方針としました。
また合わせて、問題インスタンス生成を含め最適化に関する処理はすべて Rust に移植 しシングルバイナリ化しています。
Rust の選定理由は以下の通りです。
- 高速なパフォーマンスを実現できること
- チーム内で実績があり、Rust に詳しいメンバーがいたこと
大規模な問題インスタンスを効率的に処理する必要があったため、言語のパフォーマンス特性は重要な選定基準でした。Rust はゼロコスト抽象化の原則に基づいており、安全性を犠牲にせずに C/C++ に匹敵する実行速度を実現できます。 また私自身は Rust の経験が無かったものの、Rust 経験者のレビューを受け、実装を進めることができました。
Rust について知りたい方は、こちらの記事 も参照ください。
ソルバにおける工夫点は以下の通りです。
- 多スタート戦略を採用
- 乱数生成は比較的高速な rand::rngs::SmallRng を採用
- tokio、rayon を使い実行環境の CPU 数に合わせ処理を並列化
- 一部のデータ構造は bitvec を活用し高速化
- anyhow、thiserror を使ったエラーハンドリング
ソルバ実装の段階では、Python プロトタイプの処理を Rust に移植しつつ、解の品質の改善も同時に行いました。品質改善の方法としては、前処理の工夫や目的関数、制約の追加、探索アルゴリズムの改善などです。
コアな最適化ロジックの変更がある場合は、マージリクエスト単位で各目的関数の値と実行速度を計測するようにしました。また、そのために ベンチマーク用の問題インスタンス集 を用意しています。
ただし大域的な最適解とのギャップの評価までは実施できていません。 大域的な最適解が必ずしも現実の問題を解決できているとも限らないため、目的関数や制約の設計の調整を優先しました。 現時点では重要な目的関数の値は注視しつつ、人による定性的な評価を重視する方針としています。
⚡高速化
最適化ソルバを実用可能にするために、高速化は必須でした。 高速化のため行った対応についていくつか紹介します。
問題インスタンス生成の高速化
問題インスタンスへの変換では、圃場と道路の位置関係を考慮し、 散布作業モデルに従って移動ルートをあらかじめ列挙する処理があります。
Python によるプロトタイプ実装ではこのルート列挙処理が遅く、 小〜中規模の問題インスタンスでは最適化処理よりも問題インスタンスの生成処理に時間がかかる状態となってしまっていました。
この問題インスタンス生成処理を含め Rust に移植することで高速化しました。
この Rust 移植では、以下のクレートが役立ちました。
- geo: ポリゴンなど地理空間データに関する計算
- petgraph: 道路ネットワークに関する計算 (グラフ理論)
- rstar: 道路ネットワークに関する計算 (地理空間的なクエリ)
- utm: 座標変換
- osmpbfreader: OpenStreetMap のデータ読み込み
Rust 移植後は、Python プロトタイプにおいて小規模な問題インスタンスで 40 秒ほどかかっていた処理が 300〜400 ミリ秒程度に改善 できました。
起動の高速化
インフラ構成をシンプルにするべく、Rust 実装の最適化ソルバは AWS Lambda で動作させ、Docker コンテナ内に OpenStreetMap の地図データを配置 しておく方法を採用しました。構成の意図は Web システムとの連携の章で後述します。
そこで問題になったのがプログラムの起動時間です。OpenStreetMap の地図データは、日本国内に絞っても PBF 形式で数 GB 以上になります。API のリクエストによりプログラムが起動した際に、地図データの読み込みと前処理 (R*-tree の構築など) を実行する必要があり、この処理に 12 秒程度かかっていました。
この地図データの読み込み処理は、以下の工夫によって高速化しました。
- 地図データを読み込みやすい独自のバイナリ形式に事前に変換
- 地物のバウンディングボックスを階層化
- OpenStreetMap の Way 及び Node を地理空間上の配置を考慮しモートン符号により並び換えておく
- API リクエスト時 (Lambda 起動時) は memmap2 により必要なデータのみを読み込み
高速化後は、もともと 12 秒程度かかっていた読み込み処理が 45 ミリ秒程度に改善 しました。また、ピークメモリ使用量も数 GB から数十 MB オーダーに削減しました。
最適化ソルバの高速化
最適化ソルバの高速化には、2 つの方針があると思います。
- 探索手法自体を改善する
- 探索手法は変えずに処理を高速化する
1 の方針のほうが効果的だと思いますが、問題に特化した専用の探索手法までは開発していません。 高速化のために、全体の構成を見直すタイミングは数回ありましたが、基本的には局所探索法のフレームワークのなかに留まっています。 運用のなかで要求が変化しても、柔軟に対応できる点が局所探索法の強みだと思います。
一方で、近傍操作については企画の要求を汲み取りつつ、目的関数の改善に大きく寄与する近傍設計を追求しました。一部の近傍は Variable Depth Search のような手法も採用しています。
また、複数ある近傍操作が何回評価され、何回遷移したか等の統計値を確認できるようにしています。この指標により、解の品質にあまり寄与しない近傍については早めに廃止することができました。
2 の方針の高速化は、改修のたびに検討しています。目的関数や制約の追加に伴い処理が遅くなっていくので、改修前の速度を可能な限り維持できるようにリファクタのような高速化は都度入れるようにしていました。
Rust の高速化にはプロファイリングツールの samply が役に立ちました。プロファイリングをすることでボトルネックが明らかになり、高速化の方針が立てやすくなります。
高速化のパターンとしては以下を意識しましたが、ケースバイケースだと思います。まずは計測せよ、ですね。
- メモリの動的確保の回避
- 軽量なデータ構造への置き換え
Rust は .clone() を明示する必要があったりとメモリ周辺の挙動が比較的わかりやすく、高速化しやすいと感じました。
🎚️最適化のチューニング
散布ルートの最適化は多目的の最適化問題です。目的関数が複数ある場合の最適化方法はいくつかあると思いますが、シンプルに係数をかけて足し合わせる方法を採用しました。
そこで問題になるのが、係数をどう決めるか、という点です。
開発初期は決め打ちで係数を決定し、運用前に係数のチューニングを実施しました。チューニングには Optuna を使い、サンプル問題のデータセットを与えれば自動で調整してくれるスクリプトを用意しています。
ただ全ての問題インスタンスにとって良いパラメータというのは存在せず、チューニングには苦悩しました。
問題インスタンスの規模や特性により係数を調整したり、探索の過程で係数を調整するなどアダプティブな方法が良いと思いますが、そこまでは検討できていません。 他の最適化プロジェクトでも似たような課題はあり、今後良い方法を探りたいです。
🌐Web システムとの連携
散布ルートの最適化は、ピンポイントタイム散布 (PTS) の一機能として Web システムと連携しています。
おおまかなインフラ構成としては、AWS Lambda の Function URLs を使い HTTP の API として最適化処理を提供しています。AWS Lambda を使うことで、負荷の高い最適化処理を楽にオートスケールできます。
AWS Lambda を使う上で考慮すべき点は以下の通りでした。
- 実行時間は最大 15 分
- コンテナイメージの最大容量 10 GB
- CPU 数はメモリ容量によって変化
- x86 か ARM (Graviton 2) か
最適化処理のために CPU 数は可能な限り増やしたいので、メモリ容量は最大の 10240 MB に設定しています。また動作確認したところ x86 よりも ARM (Gravition 2) のほうが高速だったため、ARM アーキテクチャを採用しています。
API 仕様は OpenAPI で定義し、Web システム側開発チームのレビューを受けました。そして最適化実行のための画面開発や API の繋ぎ込みを経て、最適化ソルバが実運用に組み込まれました。このあたりは通常の Web 開発と同じですね。 私は以前 ID 基盤 OPTiM ID の開発を担当していたこともあり、Web 開発に関する知見が活きました。
また 問題インスタンスのエクスポート機能 を Web アプリの機能として用意したことで、一部の大規模案件やパラメータ調整が必要な案件への対応も柔軟に行うことができました。散布ルートの最適化が社内運用重視の機能であることの側面も強いと思いますが、イレギュラーな問題インスタンスへの対処策として役に立ったと思います。
最適化ソルバの API 化にあたっては、以下のツール、クレートを活用しました。
- Cargo Lambda: AWS Lambda 向けのビルドツール
- lambda_http: AWS Lambda で HTTP リクエスト、レスンポンスを扱う
- aws-config、aws-sdk-s3: Amazon S3 へのログ保存
- serde、serde_json: リクエスト及びレスポンスのデシリアライズとシリアライズ
- validator: リクエストのバリデーション
Cargo Lambda を使うことで、ローカルで AWS Lambda 向けのビルドや動作確認が簡単に行えます。Zig cc によるクロスコンパイル がデフォルトとなっており、AWS Lambda の ARM 向けビルドについては特に何も考えずで OK でした。
🏃💨初期の運用とバックアッププラン
農薬散布の案件は、小規模なものから大規模なものまで多岐にわたります。また個別の条件を考慮してルート作成を行いたいケースもありました。
大規模な案件については問題インスタンスのエクスポート機能を活用し、一時的に性能の高いマシンでソルバを動作させ対処しました。1 案件だけ個別のパラメータチューニングも実施しています。
そのような個別のケースに対応するために、チーム内のRustに精通したメンバーが egui を使用したローカルマシン向けGUIフロントエンドツールを開発しました。このツールは一部Webブラウザでも動作し、Webシステム側の改修を待たずに新機能を試したり、細かなパラメータ調整を迅速に行ったりすることを可能にしています。
初期の運用では、イレギュラーな問題インスタンスへの対処策を用意しておくことが重要だと感じました。組合せ爆発による計算時間の増大はもちろんのこと、思わぬコーナーケースが潜んでいる可能性もあります。
📚おわりに
2024年はありがたいことにピンポイントタイム散布 (PTS) のサービス規模が大幅に拡大しました。散布ルート作成にかける人員や工数は最適化の力によって前年度に比べても削減できており、効果を感じています。
振り返ってみると、最適化ソルバの実装よりも周辺の構成や運用の設計に苦労した数ヶ月間でした。 実際の運用においては、以下の 3 つのバランスが重要だと感じました。
- 最適化モデルの精度 (現実を正しくシミュレーションできるか)
- 入力データの精度 (モデルを十分に機能させられるか)
- 最適化ソルバの探索性能 (十分な品質の解を出せるか)
3 つのうち 1 つでも欠けると、使い物にならなくなります。競技プログラミング等では 3 が重視されると思いますが、1、2 もとても興味深く、面白い領域です。
今回のプロジェクトを通じ、組合せ最適化が実際に使える技術であることを社内で実証できたのは良かったです。今後も最適化技術を推進していこうと思います。
R&D では今回紹介したルート最適化意外にも、いくつか組合せ最適化技術を活用しています。ヒューリスティクス系の解法だけでなく、混合整数計画 (MIP) や 制約プログラミング (CP) も使っていますので、機会があれば紹介したいと思います。
オプティムでは、組合せ最適化を実装するエンジニアを募集しています。
