[市場動向]

2024年8月30日(金)日川 佳三（IT Leaders編集部）

リスト

　パナソニック コネクトは、巡回セールスマン問題などの組み合わせ最適化問題を高速に解くための手法「多目的最適化技術」を開発した。従来技術と比べた特徴は、データの規模に応じて適切なアルゴリズムを自動で選択することで、現場ごとの制約条件に依存せず、多目的に使えるようにしたことである（図1）。

図1：全都市を訪れながら荷物を収集するタスクの概要（出典：パナソニック コネクト）
拡大画像表示

　多目的最適化技術を開発するまで同社は、製造現場の計画立案に要する作業時間の削減に「単目的最適化技術」を利用してきた。複数の製品を扱う現場で切り替え作業が発生するといったケースで、切り替え作業時間が少なくなるように各製品の生産順序を並び替え、効率的な生産計画を提案する技術である。

　「ところが、実際の現場では切り替え時間だけでなく、複数のファクターを考慮した生産計画立案が求められる場合がある。例えば、各々の製品の生産優先順位を保ちながら切り替え作業時間を最小化するケースでは、どのような順番で生産するべきかなど、切り替え時間の最小化と生産優先順位遵守が同時に求められる場合が該当する」（同社）

　従来手法では、切り替え時間を最小化するアルゴリズムに、生産の優先順位を順守するためのアルゴリズムをプログラミングによって追加実装する必要があった。このプログラミングにかかる時間が大きなネックとなっていたという。今回開発した多目的最適化技術はこの問題を解決する。

　パナソニック コネクトは、製造現場における「生産時間×生産優先順位」を考慮した計画最適化や、製造・物流現場における無人搬送車の「走行経路×部材収集搬送」の計画最適化など、さまざまな制約条件を持つ製造・物流現場への適用に向けて技術レベルを上げていくとしている。

データ規模に応じて適切なアルゴリズムを自動選択

　パナソニック コネクトは多目的最適化技術を、進化計算のコンファレンス「GECCO 2024」の多目的化コンペティション「The Travelling Thief Problem（TTP）」に合わせて開発した。

　取り組んだタスクは、巡回セールスマン問題とナップサック問題の組み合わせを前提に、全都市を訪れて荷物を収集するケースにおいて、都市訪問時間の最小化と荷物価値の最大化を同時に実現するというもの。

　コンペでは、都市数が「280」「4461」「3万3810」、各都市に置かれた荷物の数が「1～10」といったパラメータの異なる9つの問題と、都市数や荷物数が非公開の9つの問題が出題された。各問題に対する最終的なスコアは、荷物価値から走行時間に応じたナップサックのレンタル料を差し引いて算出する。荷物には重さと価値の数値が与えられているという。

　「仮説では、先に軽くて価値の高い荷物をナップサックに詰めることで、より早く都市を訪問できる。逆に、価値が高くても重い荷物を先にナップサックに詰めると、重さによる速度低下で他の都市を回るのに時間がかかる」（同社）

　同社はタスクを解くにあたって、多目的最適化技術の手法により、データ規模ごとに適切なアルゴリズムを使い分けることにした。都市数に応じて最適なアルゴリズムを自動選択することで、都市数3万3810と荷物数10個という大規模な問題に対しても、処理制限時間の10分以内に高精度な回答が得られ、コンペで2位の評価を獲得した。

●Next：多目的最適化技術で用いる協調探索アルゴリズム「CoCo」とは