パナコネクト、組み合わせ最適化問題に10分で回答できる技術を開発

パナソニックコネクトは8月30日、GECCO 2024の多目的化コンペティション「The Travelling Thief Problem（TTP）」にて、巡回セールスマン問題とナップサック問題の2つを組み合わせを前提とし、すべての都市を訪れて荷物を収集する際の都市訪問時間の最小化と荷物価値の最大化を同時に行うタスクに取り組み、独自の多目的最適化技術により、処理制限時間10分間でタスクに回答し、世界で2位の評価を獲得したことを発表した。

全都市を訪れながら荷物を収集する際の、荷物価値と走行時間に応じたスコアを最大化するコンペ

今回のタスクを解くにあたり、データ規模に応じて適切なアルゴリズムを導入。コンペでは、都市数が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位の評価を獲得した。

独自開発した中規模・大規模向け協調探索手法

同社が従来保有していた単目的最適化技術では、複数のファクターを考慮するためには追加のプログラミングが必要であり、現場ごとの異なる制約条件に対応するための時間がかかっていた。しかし、今回開発したデータ規模に応じて適切なアルゴリズムを自動選択する多目的最適化技術により、パナソニックコネクトが注力しているサプライチェーンの分野（製造、物流、流通）で、複数の制約条件下でも迅速に最適な解を算出できるようになったほか、現場ごとに異なる制約条件に対する対応スピードも大幅に向上した。

製造現場における生産時間と生産優先順位を考慮した計画最適化や、製造・物流現場での無人搬送車（AGV）の走行経路と部材収集搬送の計画最適化など、多様な制約条件を持つ環境への適用に向け、このコンペ参加で獲得した多目的最適化技術をベースに技術レベルを上げていくとしている。計画立案業務に対する工数を削減することで、最適な計画のない現場で発生する様々な業務から人々を解放し、人がより創造的な業務に専念できる環境を提供することをめざしているという。