掲載情報は2025年5月現在
| 所属 | 大学院情報理工学研究科 情報・ネットワーク工学専攻 |
MURAMATSU Masakazu |
| メンバー | 村松 正和 教授 | |
| 所属学会 | 日本オペレーションズ・リサーチ学会、応用数理学会、情報処理学会、国際数理計画学会（MPS）、国際応用数理学会（SIAM）、電子情報通信学 | |
| 研究室HP | https://muramatsu-lab.jp/ | |
| 印刷用PDF |
連続最適化、凸最適化、錐線形最適化、アルゴリズム、機械学習、深層学習、強化学習
ある制約条件の下で複数の選択肢から最適なものを選ぶ数学の理論である「最適化」は、今や学術分野のみならず、シミュレーションやモノづくりといった産業分野から社会問題の解決まで、あらゆる領域で使われている手法です。
例えば地震や台風、洪水などの災害時を一つとっても、情報収集やその発信方法、避難誘導、安定的な電力供給や復興計画の策定など、最適化を適用できる問題は数多くあります。最適化といっても必ずしも厳密な最適解を求めているわけではなく、応用先によっては近似解で十分な問題も少なくありません。
最適化とは、問題を定量的にとらえ、最も効率的な解法を科学的に探る「オペレーションズ・リサーチ（OR）」の理論的な柱の一つです。オペレーションは「作戦」という意味で、第二次世界大戦中に英国が軍事研究として使ったことが始まりとされています。現代においては、ORは「問題解決学」と言えるでしょう。
村松研究室ではこの最適化とORに関する研究を手がけており、その中でも村松正和教授は、最適化問題の基礎問題の一つである「凸最適化問題」や「錐線形最適化問題」について、理論と応用の両面から取り組んでいます。特に、大規模かつ複雑な問題の最適解を効率良く解くアルゴリズムを研究していますが、理論的な研究は、すぐにその場で役に立つような性質のものではありません。
例えば、村松教授が取り組んできた「２次錐最適化」と呼ばれる錐線形最適化に関する研究は1990年代に始まりましたが、2000年代になってようやく理論が整備され、アルゴリズムが実装されるようになりました。2010年代半ばになると、整数最適化問題を解く最適化ソルバーに標準的に搭載されるようになり、現在は各社がそのモデルをPRしている状況です。世の中に普及するまでにはまだ数年はかかりますが、理論の研究とはこのように長いスパンでの取り組みが必要です。村松教授が手がけているのは、こうした20年―30年先を見すえた研究なのです。
最近は、従来の効率的な解法を適用しにくい錐線形最適化問題において、「内点許容解」が存在する等価な錐線形最適化に変形する「Facial Reductionアルゴリズム（FRA）」と呼ばれる手法を使ったアイデアを研究しています。そのほか、これを拡張し、同次対称錐最適化問題の内点実行可能解を求める新しいアルゴリズムなども開発しています。
理論としては、線形最適化問題や半正定値最適化問題、多項式最適化問題、および非線形最適化などを扱っていますが、こうした最適化手法をさまざまな実問題にも応用しています。
例えば、需要の変動に応じてネットワークを柔軟に切り替え、消費電力を約30％減らす基幹ネットワークの最適な構築方法を提案したり、点が与えられた時に、これらを結ぶ三角形の面積の総和が最大になるような線の引き方（三角形総面積最大化問題）を提案したりしています。後者は、あるゲームにおいて得点を最大にしたい、というところから現れる問題です。
目的地へ効率良くたどり着くための経路を探す「最短経路問題」は典型的な最適化問題ですが、ウォーキングを趣味にするある学生は、東京23区を一日で歩いて踏破するための最短ルートを割り出す問題を卒業研究のテーマとし、実際にそのルートを踏破しました。
近年は、最適化問題の応用を目指し、働き方改革関連法の施行やトラックドライバー不足などを背景とする「物流の2024年問題」に向け、荷物をいかに効率良く積み込むかというトラック積載荷姿問題や、トラックの工場到着時刻の等間隔スケジューリング、部品配送最適化問題といった研究テーマに企業と共同で取り組んできました。
積載荷姿問題では、同じ種類の部品を詰めた数量やサイズの異なる荷物を毎日、一般的な15トントラックで輸送するケースを考えます。部品は箱に入れ、その箱をパレットに載せてトラックに積み込みます。この問題に対し、ランダム要素のある貪欲法で初期解を生成し、それを改善する「貪欲ランダム化適応探索法（GRASP）」と呼ばれるアルゴリズムを改良して適用しました。その結果、既存手法では10万箱を運ぶのに最大80台必要だと算出されたトラックの台数を、計算時間はやや長くなるものの、最大72台まで減らせることを確認しています。
また、1台のトラックが複数の工場を巡回するより効率的な輸送ルートにおいて、各工場にトラック便を等間隔に到着させる複雑なスケジューリング問題を解くモデルも提案しました。これにより、「1台のトラックが倉庫と1工場間をピストン運行する単一ルートに対し、人手では管理が難しかった多様なルートについても到着時刻の等間隔スケジューリングが可能になる」と村松教授は見通しています。そのほか、工場間の部品の輸送に必要なトラック台数を最小化する配送経路を決める最適化問題なども扱っています。
最適化の面白い点は、その手法をさまざまな分野へ適用できるところです。例えば、インフルエンサーマーケティングにおいて、その影響を最大化する問題にも取り組んでいます。オンラインソーシャルネットワークの発展に伴い、テレビや新聞などの従来のアプローチとは異なり、SNS上で影響力のあるインフルエンサーによる口コミなどをマーケティングに活用する動きが広がっています。最適解を求めるBenders分解と呼ばれる手法を使い、通常の最適化ソルバーを使うよりも高速にその問題を解くことができました。
最適化はその応用の広さに対して、理論の研究者は世界でもそう多くないのが現状です。新しいアルゴリズムが実際に社会へ受け入れられるまでには長い時間を要しますが、村松教授は最適化の理論の研究を長年追究しており、世界を相手に多くの論文を発表していることが大きな強みです。
機械学習、なかでも深層学習や強化学習の応用についても企業と共同で研究しています。実は機械学習の原理は「最適化そのもの」であり、村松教授は最新の最適化アルゴリズムを駆使して企業の要求に応えています。最近の共同研究は特許を申請するまでに発展し、関連の研究において社会人ドクターも受け入れています。村松教授は「最適化や機械学習は未来の社会を変える重要な手法であり、産業界に眠る需要があれば、ぜひ一緒に取り組みたい」と考えています。
【取材・文＝藤木信穂】
