2024年12月11日
- 技術・研究開発
- トピックス
Adobe Acrobat Readerの特定のバージョンに、一部のPDFが開けないバグが発生しております。PDFが開けない場合、お使いのAcrobat Readerを最新版へアップデートの上お試しください。
2024年8月30日
技術・研究開発 / プレスリリース
進化計算の世界トップカンファレンス「GECCO 2024」の多目的最適化コンペティションでパナソニック コネクトが世界で2位の評価を獲得
パナソニック コネクト株式会社(本社:東京都中央区、代表取締役 執行役員 プレジデント・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)を用いました。
当社では、製造現場の計画立案に要する作業時間を削減する単目的最適化技術を保有しており、製造現場での生産計画作成に活かしてきました。例えば、複数の製品を扱う現場で切り替え作業が発生する場合に、切り替え作業時間が少なくなるよう各製品の生産順序を並び替え、効率的な生産計画を提案します。昨今増加している多品種少量生産、また急な市場の変動要因による柔軟な計画変更等のニーズの高まりを受け、このような技術はより重要となります。
さらに、実際の現場では切り替え時間のみならず、複数のファクターを考慮した生産計画立案が求められる場合があります。例えば、各々の製品の生産優先順位を保ちながら、切り替え作業時間を最小化するにはどのような順番で生産するべきか、といった切り替え時間の最小化と生産優先順位遵守が同時に求められる場合がこれに該当します。従来の手法では、切り替え時間を最小化するアルゴリズムに、生産の優先順位を遵守するためのアルゴリズムをプログラミングにより追加実装する必要がありました。従来手法においてはこの追加のプログラミングにかかる時間が大きなネックとなっていました。
この問題を解決し、今後、現場の多様な制約条件に対応していくために、複数のファクターを考慮しつつ、制約条件に合わせたアルゴリズムの追加なしで最適化を行う多目的最適化技術の獲得を目的として本コンペに出場し、新たな技術を開発しました。
今回のタスクを解くに当たり、データ規模に応じて適切なアルゴリズムの導入を実施しました。
本コンペでは、都市数が280、4,461、33,810か所、各都市に置いてある荷物の数が1~10といったパラメーターの異なる9つの問題や、都市数や荷物数が非公開の9つの問題が用意されています。各問題に対する最終的なスコアは、荷物価値から走行時間に応じたナップサックのレンタル料を差し引いて算出されます。荷物には重さと価値の数値が与えられており、先に軽くて価値の高い荷物をナップサックに詰める(以下、「パッキングする」)ことでより早く都市を訪問でき、逆に先に価値が高くても重い荷物をパッキングすると重さによる速度低下で他の都市を回るのに時間がかかってしまうという仮説が立てられます。
これらの複雑な条件を満たして、より良いスコアが得られるよう、以下のようにデータ規模に応じて適切にアルゴリズムを自動選択する多目的最適化技術を開発しました。
具体的には、2023年2位公開手法(以下、「既存手法」)をベースに、データ規模(都市数)に応じたアルゴリズムの見直しを行いました。都市数100~120の問題の場合には既存手法よりも時間はかかるが網羅的に経路(都市順)と荷物パッキング案(どの荷物をパッキングするか)を探索できる局所探索手法の導入、都市数121~1050の場合には既存手法を活用、都市数が中規模・大規模の場合には走行時間と荷物価値の協調探索手法であるCoCo(Cooperation Coordination)を導入しました。
ただし、今回ベースとした既存手法には課題がありました。既存手法において、特に中規模・大規模都市数向けのアルゴリズムでは、走行距離と荷物パッキング案の探索を独立に行っており、単目的の探索(経路のみの探索や荷物パッキング案のみの探索)に時間を要してしまい、非効率になりがちでした。
そこで、走行時間・荷物の重さ・荷物の価値を総合的に参照でき、走行時間と荷物価値の協調探索手法であるアルゴリズムCoCo(Cooperation Coordination)に着目し、中規模・大規模の都市数の問題データ向けに導入しました。CoCoでは、経路と荷物パッキング案を少しずつ変更し、スコアが高いものを採用していきます。また、数回連続してスコア更新が無い場合は経路と荷物の変更を止め、ランダムスタートで新しい経路と新しい荷物パッキング案でやり直すことにより、早く良い解にたどり着く可能性を高めています。
自動探索時に、本コンペのスコア計算を用いて、“例えば、数回スコアが上がったらこの調子で地点をまた少し変更してスコアを見てみよう、数回スコアが下がったら可能性が低いので一旦破棄して最初からやり直そう”というルールで、良くない解を早めに諦めてリセットすることで、膨大な数の解の中から、既存手法よりも早く、より良い回答を得られます。
この度開発した都市数に応じて最適なアルゴリズムを自動選択する新たな技術を用いることで、都市数33,810×荷物数10個という大規模な問題に対しても、処理制限時間10分という非常に短い時間の中で高精度な回答を得ることを可能にし、本コンペで2位の評価を獲得しました。
当社の保有する従来の単目的最適化技術では、複数のファクターを考慮するためにプログラミングによる追加実装が必要であり、現場ごとに異なる制約条件への対応に時間を要していました。この度開発したデータ規模に応じて適切にアルゴリズムを自動選択する多目的最適化技術により、パナソニック コネクトが事業領域として注力しているサプライチェーンの領域、製造、物流、流通の現場で、複数の制約条件下でも短い時間で最適な回答を算出し、かつ現場ごとに異なる制約条件への対応スピードの加速が図れるようになります。
製造現場における生産時間×生産優先順位を考慮した計画最適化や、製造/物流現場における無人搬送車(Automatic Guided Vehicle, AGV)の走行経路×部材収集搬送の計画最適化など、多様な制約条件を持つ製造/物流現場への適用に向けて、本コンペ参加で獲得した多目的最適化技術をベースに技術レベルを上げていきます。計画立案業務に対する大幅な工数の削減を実現することで、最適な計画の無い現場で発生する様々な業務から人々を解放し、人がさらに創造的な業務に時間を割くことを可能にします。
当社は、「現場から 社会を動かし 未来へつなぐ」というパーパスを掲げ、現場にイノベーションをもたらすことで多様な人々が幸せに暮らせる、持続可能な社会の実現を目指してまいります。
※1 The Genetic and Evolutionary Computation Conference
https://gecco-2024.sigevo.org/HomePage
※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
パナソニック コネクト株式会社は2022年4月1日、パナソニックグループの事業会社制への移行に伴い発足した、B2Bソリューションの中核を担う事業会社です。グローバルで約28,300名の従業員を擁し、売上高は1兆2,028億円(2023年度)を計上しています。「現場から 社会を動かし 未来へつなぐ」をパーパス(企業としての存在意義)として掲げ、製造業100年の知見とソフトウェアを組み合わせたソリューションや高度に差別化されたハードウェアの提供を通じて、サプライチェーン、公共サービス、生活インフラ、エンターテインメント分野のお客様をつなぎ、「現場」をイノベートすることに取り組んでいます。また、人と自然が共存できる豊かな社会・地球の「サステナビリティ」と、一人ひとりが生きがいを感じ、安心安全で幸せに暮らすことができる「ウェルビーイング」の実現を目指しています。
また、「人権の尊重」と「企業価値の向上」を目的に、DEI(Diversity, Equity & Inclusion)推進を経営戦略の柱のひとつに位置づけ、多様な価値観を持つ一人ひとりがイキイキと力を発揮できる柔軟性の高い企業文化の改革に取り組んでいます。
▼パナソニック コネクト株式会社 ウェブサイト
https://connect.panasonic.com
▼パナソニック コネクト Newsroom
https://connect.panasonic.com/jp-ja/newsroom
▼パナソニック コネクト DEI(Diversity, Equity & Inclusion)
https://connect.panasonic.com/jp-ja/about/sustainability/dei
記事の内容は発表時のものです。
商品の販売終了や、組織の変更等により、最新の情報と異なる場合がありますのでご了承ください。