膨大な計算時間を要する組み合わせ最適化問題に10分で回答できる多目的最適化技術を開発

パナソニックグループ

2024年9月3日 11時50分

パナソニックコネクト株式会社（本社：東京都中央区、代表取締役執行役員プレジデント・CEO：樋口泰行、以下、パナソニックコネクト）は、進化計算のトップカンファレンス、GECCO 2024（※1）の多目的化コンペティション「The Travelling Thief Problem（TTP）」にて巡回セールスマン問題（Travelling Salesperson Problem）とナップサック問題（Knapsack Problem）の2つの組み合わせを前提とし、全ての都市を訪れて荷物を収集する際の、都市訪問時間の最小化と荷物価値の最大化を同時に行うタスクに取り組み、データ規模に応じて適切にアルゴリズムを選択するパナソニックコネクト独自開発の多目的最適化技術により、処理制限時間10分間でタスクに回答し、世界で2位の評価を獲得しました。独自開発の多目的最適化技術には、本コンペティション2023年2位公開手法（データ規模に応じたアルゴリズム切替）（※2）をベースとし、2023年にオーストラリア連邦科学産業研究機構（CSIRO）他により報告された走行時間・荷物価値の協調探索手法CoCo（Cooperation Coordination）アルゴリズム（※3）を用いました。

■開発の背景

パナソニックコネクトでは、製造現場の計画立案に要する作業時間を削減する単目的最適化技術を保有しており、製造現場での生産計画作成に活かしてきました。例えば、複数の製品を扱う現場で切り替え作業が発生する場合に、切り替え作業時間が少なくなるよう各製品の生産順序を並び替え、効率的な生産計画を提案します。昨今増加している多品種少量生産、また急な市場の変動要因による柔軟な計画変更等のニーズの高まりを受け、このような技術はより重要となります。

さらに、実際の現場では切り替え時間のみならず、複数のファクターを考慮した生産計画立案が求められる場合があります。例えば、各々の製品の生産優先順位を保ちながら、切り替え作業時間を最小化するにはどのような順番で生産するべきか、といった切り替え時間の最小化と生産優先順位遵守が同時に求められる場合がこれに該当します。従来の手法では、切り替え時間を最小化するアルゴリズムに、生産の優先順位を遵守するためのアルゴリズムをプログラミングにより追加実装する必要がありました。従来手法においてはこの追加のプログラミングにかかる時間が大きなネックとなっていました。

この問題を解決し、今後、現場の多様な制約条件に対応していくために、複数のファクターを考慮しつつ、制約条件に合わせたアルゴリズムの追加なしで最適化を行う多目的最適化技術の獲得を目的として本コンペに出場し、新たな技術を開発しました。

※1 The Genetic and Evolutionary Computation Conference

※2 本コンペティション2023年2位公開手法（データ規模に応じたアルゴリズム切替）

出典元：https://github.com/fontanf/travellingthiefsolver

正式名称：Travellingthiefsolver

※3 2023年にオーストラリア連邦科学産業研究機構（CSIRO）他により報告された走行時間・荷物価値の協調探索手法CoCo（Cooperation Coordination）アルゴリズム

出典元：Namazi, M., et al.：Solving travelling thief problems using coordination based methods. Journal of Heuristics 29(4), 487–544 (2023).

正式名称：Cooperation Coordination

全文は以下プレスリリースをご覧ください。

▼[プレスリリース]膨大な計算時間を要する組み合わせ最適化問題に10分で回答できる多目的最適化技術を開発（2024年8月30日）

https://news.panasonic.com/jp/press/jn240830-3

＜関連情報＞