複雑な組合せから最適な答えを探す新手法を開発 ～「カオス」の力を自動調整し、物流ルートや勤務シフトの効率化に貢献～
東京理科大学
【研究の要旨とポイント】
配送ルートの決定、勤務シフトの作成などでは、膨大な選択肢の中から、条件を満たしつつ最適な組合せを短時間で見つけることが求められます。
本研究では、粒子群最適化をカオス探索法に組み込むことで、探索中に主要なパラメータを自動的に調整する新たな手法を開発しました。
容量制約付き配送計画問題を対象とした数値実験により、提案手法が従来のカオス探索法やフィードバックベースの調整法よりも、解の質と頑健性に優れることを確認しました。
本成果は、配送ルート、勤務シフト、生産計画、IT、通信ネットワークなど、社会のさまざまな場面で必要とされる組合せ最適化技術の高性能化につながる可能性があります。
【研究の概要】
東京理科大学大学院 工学研究科 情報工学専攻の郭 豊愷氏（2026年度 博士課程3年）、日本工業大学 先進工学部 データサイエンス学科の松浦 隆文准教授、東京都市大学 情報工学部 知能情報工学科の木村 貴幸教授、東京理科大学 工学部 情報工学科の池口 徹教授らの共同研究グループは、「組合せ最適化問題（＊1）」をより安定して解くため、粒子群最適化（＊2）を組み込んだカオス探索法（＊3）を開発しました。
組合せ最適化問題は、勤務シフトの作成、工場での生産計画など、私たちの生活を支えるさまざまな場面に関わっています。しかし、選択肢の数が少し増えるだけでも、考えられる組合せの数は急激に増加するため、限られた時間で最適解を効率よく探す手法が求められてきました。このような手法の一つに、カオスダイナミクスを利用したカオス探索法があります。一方で、従来のカオス探索法には、性能がカオスニューラルネットワーク（＊4）のパラメータ（＊5）設定に大きく左右されるという課題がありました。問題の種類や探索の段階に応じて適切なパラメータは変化するため、経験的なパラメータ調整だけでは、安定して高い性能を維持することが困難でした。
本研究ではこの課題を改善するため、群知能最適化の一種である粒子群最適化をカオス探索法に組み込みました。粒子群最適化は、探索を行う複数の粒子が互いの情報を共有しながら、より良い条件を探す手法です。今回開発した手法では、探索の進み具合に応じてカオス探索法の主要なパラメータを粒子群最適化により自動的に調整し、安定した最適解の探索を実現しました。
研究グループは、車両の積載量に制約がある中で配送経路を最適化する「容量制約付き配送計画問題（＊6）」を対象に、数値実験を行いました。その結果、提案手法は、従来のカオス探索法やフィードバックベースの調整法と比べて、より良い解を安定して得られることが確認されました。
本成果は、カオス探索法の性能を左右していたパラメータ設定の課題を、探索中の自動調整によって改善するものです。今後、物流、勤務シフト、生産計画、通信ネットワークなど、私たちの生活を支える仕組みをより効率よく動かす技術につながる可能性があります。
本研究成果は、2026年7月1日に
国際学術誌「NOLTA, IEICE」にオンライン掲載されました。
【研究の背景】
配送ルートの決定、勤務シフトの作成、工場での生産計画、IT、通信ネットワークの設計・運用などでは、膨大な選択肢の中から、与えられた制約を満たしつつ最適な組合せを見つける必要があります。このような問題を「組合せ最適化問題」といいます。しかし選択肢の数が増えると、考えられる組合せの数は爆発的に増加するため、すべての候補を調べて最適な解を求めることは現実的ではありません。
限られた計算時間の中で良い解を効率よく探すため、これまでに多くのヒューリスティック手法やメタヒューリスティック手法が研究されてきました。メタヒューリスティック手法の一つであるカオス探索法は、カオスダイナミクスにより解空間を広範囲に探索できる点が最大の強みです。特に、解の候補が膨大で、局所最適解が多数存在するために探索が停滞しやすい場面で威力を発揮します。そのため、配送計画問題、ネットワークの経路制御、バイオインフォマティクスにおける配列解析など、これまでにさまざまな組合せ最適化問題への応用が検討されてきました。一方、その性能はカオスニューラルネットワークのパラメータ設定に強く依存します。パラメータが適切でない場合、探索が早い段階で行き詰まったり、探索効率が低下したりする可能性がありました。
【研究結果の詳細】
本研究では、カオス探索法の性能がパラメータ設定に左右されるという課題に対して、粒子群最適化を組み込んだ新たなカオス探索法を提案しました。粒子群最適化が探索中に主要なパラメータを動的に調整することで、組合せ最適化問題における解の改善を実現します。この手法は、パラメータを調整する外側と、実際に解を探索する内側の二層で構成されています。外側では、粒子群最適化がカオス探索法のパラメータの候補を複数用意し、それぞれの候補がどの程度良い解につながるかを評価します。内側では、それぞれのパラメータを用いてカオス探索法を実行し、配送経路などの解を改善します。この処理を繰り返すことで、探索の進み具合に応じて、より適したパラメータを見つけられるようにしました。
提案手法の有効性を検証するため、容量制約付き配送計画問題を対象に数値実験を行いました。実験では、標準的なベンチマークデータを用いて、従来のカオス探索法およびフィードバックベースの調整法、今回提案した粒子群最適化を組み込んだカオス探索法を比較しました。その結果、提案手法は、従来法と比べて、最適解を安定して得られることが確認されました。特に、多くの中小規模問題で、既知の最適解またはそれに近い解に到達しました。また、同じ問題を複数回解いた場合の結果のばらつきも小さく、パラメータ設定に対する頑健性（＊7）が高いことが示されました。
一方で、粒子群最適化によるパラメータ探索を加えるため、従来のフィードバックベースの調整法よりも計算時間は長くなりました。論文では、提案手法が解の質と頑健性を高める一方で、計算効率の改善が今後の課題であることも示されています。
本成果は、カオス探索法にオンラインのパラメータ調整を組み込むことで、組合せ最適化問題をより安定して解くための基盤技術を示したものです。将来的には、物流、勤務シフト、生産計画、通信ネットワークなど、私たちの生活を支える仕組みをより効率よく動かす技術につながる可能性があります。
本研究を主導した池口教授は、「私は1990年代後半より、カオスダイナミクスを組合せ最適化に応用するという観点から研究を継続してきました。今回、容量制約付き配送計画問題においてその効果を検証しましたが、本成果はシフトスケジューリング、工場における生産計画、ITおよび通信ネットワークなど幅広い分野への応用が期待でき、人々の生活に大きく貢献できるものと考えています」と、コメントしています。
- 本研究は、日本学術振興会（JSPS）科研費（20H00596、22K04602、22K18419、23K04274、23K21706、25H00447、25K08182）および東北大学電気通信研究所共同プロジェクト研究（R05/A19、R05/B13、R06/B02）の助成を受けて実施したものです。
【用語】
＊1 組合せ最適化問題
多数の選択肢の中から、与えられた条件を満たしつつ、最も良い結果となる組合せを見つける問題。例えば、宅配便の配送では、どのトラックがどの家庭を回るか、どのような順番で回れば走行距離を短くできるか、といった組合せを決める際に用いられる。
＊2 粒子群最適化
鳥や魚の群れのように、複数の候補が互いの情報を共有しながら、より良い条件を探す最適化手法。本研究では、配送経路そのものではなく、カオス探索法をうまく働かせるための主要なパラメータを調整するために用いられる。
＊3 カオス探索法
カオスとは、決定論的なルールに従いながらも複雑で予測しにくい振る舞いを示す現象を指す。その複雑な振る舞いを利用して、局所最適解にとどまらず、より広い範囲から最適解を探すことを目指す手法。
＊4 カオスニューラルネットワーク
カオス的な振る舞いを示すニューロンモデルを組合せたネットワーク。本研究では、どの局所探索操作を実行するかを制御する仕組みとして用いられる。
＊5 パラメータ
計算手法やモデルの動作を決める調整値のこと。本研究では、カオス探索法の探索のしやすさや安定性に関わる主要なパラメータを、探索中に自動的に調整することを目指した。
＊6 容量制約付き配送計画問題
複数の車両を使って荷物などを配送する際に、各車両の積載量の上限を守りながら、すべての配送先を回り、全体の走行距離などをできるだけ小さくする問題。物流分野に関わる代表的な組合せ最適化問題の一つ。
＊7 頑健性
条件が多少変わっても性能が大きく低下せず、安定して働く性質。問題の種類や探索の段階が変わっても、安定して良い解を得られるかどうかを評価するうえで重要。
【論文情報】
[表:
https://prtimes.jp/data/corp/102047/table/261_1_e21c1053aad25d74ceff49b4326a5286.jpg?v=202607061115 ]
※PR TIMESのシステムでは上付き・下付き文字や特殊文字等を使用できないため、正式な表記と異なる場合がございますのでご留意ください。正式な表記は、東京理科大学WEBページ（
https://www.tus.ac.jp/today/archive/20260708_8123.html）をご参照ください。
プレスリリース提供：PR TIMES
記事提供：PRTimes
