搬送最適化とは
概要
搬送最適化の前に、物流最適化について解説する。物流最適化とは、物流業務全体におけるコスト削減、効率向上、労働環境改善などを目的とした取り組みである。 物流最適化には、以下のような具体的な方法がある。
- トラックの最適な配送ルートの計画
- データ活用で在庫管理の効率化
- 自動倉庫システムによる作業効率の向上
上記の中でも、特に自動倉庫システムなど、倉庫内における貨物搬送を最適化する必要が出てくる。これを搬送最適化と呼ぶ。
実例
今回は実例として、株式会社Mujinの記事を取り上げる。 (動画リンクも含めて非常にイメージが湧きやすい。)
上の図にあるとおり、複数の台車(AGV, Auto Guided Vehicle)が荷物を運ぶ為に通路を走っている。 この際, 台車同士が衝突しないように制御を行わなければならない。 この制御が上手く機能しない場合は渋滞が発生し、荷物の到着が大幅に遅れる可能性がある。
上記の制御は非常に難易度が高く、マルチエージェント経路探索(MAPF)という名前で、現在でも盛んに研究されている。 今回紹介する論文は、数理最適化を用いて台車が走行するルートを計算することが目的である。
論文の内容
概要
- 論文の情報
- 題名
- 著者
- Pavel Surynek
- Ariel Felner
- Roni Stern
- Eli Boyarski
- 発行年度
- 2016年
- 発表された場所
- 出版
- IOS Press
まずは論文の概略(日本語訳)を提示する
マルチエージェント経路探索(MAPF)のタスクは複数のエージェントの競合しない経路を見つけることである。
本論文では, MAPFのコスト和変形のための最初のSATソルバを提案する。 コスト和の下界とメイクスパンの上界を用いることで、妥当な数の変数を持つことができる。
次に探索ベースのソルバであるICTSにならい、実験評価を行った。 その結果、多くのシナリオで新しいSATベースの手法が、従来のコスト和探索型ソルバーであるICTSとICBSアルゴリズムを上回ることが分かった。
前章でも言及したが、MAPFは現在でも盛んに研究されている。 今回の手法では、MAPFをSATの問題に変換し、ソルバにより厳密解を求める。 ※SATとは、 与えられた命題論理式を真にする値割り当てが存在するか否かを判定する問題である。
数式の詳細
本論文では、MAPFをグラフ理論の言葉に置き換えている。問題の定義は以下の通りである。
続いて、問題を解く方針について述べる。 まずはMAPFが持つグラフ情報から、各エージェントごとに時間発展グラフ(Time Expansion Graph, TEG)を生成する。
例として、シンプルなMAPFからのTEG生成を挙げる。
上図では、3つの頂点を1つのエージェントが渡る状況を描いている。 エージェントa0は頂点u1からスタートし、頂点u3を目指す。 時間ステップμは本来であれば3で充分であるが説明の為にμを4にしている。
MAPFを数学に落とし込む為、グラフが持つ各オブジェクトに対して変数を設定する
続いて, Booleanと整数を対応付けた求解用の変数を定義する
以降は、大文字のBoolean変数を小文字の0-1変数に書き換えながら定式化を追う。
定式化
制約式C0
制約式C1
制約式C2
制約式C3
制約式C4
制約式C5&C6->目的関数
定式化をまとめると, 以下のようになる.
まとめ
以上の形で、グリッド上の経路探索を整数最適化で置き換えることが出来た。ただし, 以上の定式化は変数量/計算量が多く、実用的とは言い難い状況である。 今後はコンピュータの計算速度を上げることも重要だが、アルゴリズムの高速化を図ることも重要である。
記事執筆者
小澤 陽介
パーソルキャリア株式会社
テクノロジー本部 デジタルテクノロジー統括部 デジタルビジネス部 アナリティクスグループ
前々職は半導体製造会社にて、リソグラフィ工程のプロセスエンジニアリングに従事。前職では機械系メーカーR&Dにて数理最適化のアプリケーション開発及び工程可視化に従事。パーソルキャリアに入ってからはアナリストとして、主に生成系AIに関連するアプリケーション開発や検証に従事。意思決定の為の計算機開発にも携わっている。
