パナコネクト、組み合わせ最適化問題に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）」アルゴリズムに注目し、中規模・大規模の都市数を含む問題データに導入した。