Research Interests

本ページでは私の研究分野である組合せ最適化やメタヒューリスティクスなどの紹介をしています．内容に間違いが無いように気を配っていますが，読みやすさを優先したため表現が曖昧となっている箇所もあります．ご了承ください．

組合せ最適化

組合せ最適化とは解の集合が離散的であるような最適化問題のことを指します．ここで最適化問題とはある制約の元で目的関数の値が最小（または最大）となる状態を求める問題です．これだけではわかりにくいかもしれませんが，実は普段の生活の中にも組合せ最適化は様々な形で潜んでいます．

引っ越し準備で段ボールに物を詰め込む人のイメージ

あなたは引っ越しをする際に段ボールに物を詰めた経験はあるでしょうか．詰める順番や向きによって微妙な隙間ができたり，表面がデコボコして後から大きな物が入れられないなど，なかなか難しい作業であるかと思います．これはまさに組合せ最適化の１つの例で，縦横高さが一定の箱に，入れる物が傾かないように物を詰めなければならないという制約の元で箱に詰め込む物の個数を最大化する問題であると言えます．

他にも，セールスマンが複数の会社に営業に行くとき，営業先をなるべく効率的に回って移動時間を短くしたいと考えたとします．これはすべての訪問先を１回ずつ訪れるという制約の元で巡回路の長さを最小化するという問題です．これは組合せ最適化の中でも有名な巡回セールスマン問題（travelling salesman problem, TSP）の一例です．

配送計画問題

１人の人間が複数の訪問先を回るときにそのルートの長さを最小化する問題は巡回セールスマン問題と言えます．しかし現実では複数の人間が分担して複数の訪問先を回ることも多くあります．セールスマンの営業でも複数で分担することは多いでしょうし，宅配便で住宅に荷物を運ぶ場合や，郵便ポストを回って郵便物を回収する場合も同様です．このように，巡回セールスマン問題を複数のルートに拡張した問題を配送計画問題（vehicle routing problem, VRP）と呼びます．

配送計画問題は古くから研究がなされている分野であり，実社会で求められるような様々な制約を考慮したモデルやそれらに対する解法が提案されています．典型的な設定としては訪問時間の指定や複数の種類の車が混在する場合などがあります．他にも，例えば複数の荷物をトラックで運ぶ際に，積み下ろしが楽になるように配達順の逆順に荷物を積み込むことがあります．この時，荷物によっては他の荷物を上に積むことができないものもあり，その場合は積み込み順だけでなく配達順を前後させて調整する必要があります．荷物を積み込む際の制約を考慮しつつ配達順序を決めるということは純粋な配送計画問題では取り扱うことはできません．

宅配業者の人のイメージ

また，最近では都市部の宅配業務において，トラックをある程度の位置に停めてそこから徒歩でいくつかの配達先に荷物を届けるという方法が採られることがあります．これはどの配達先にも台車による配達ができるような位置にトラックを停めるという制約の元で，トラックの走行距離を最小化するようにトラックの停車位置とその巡回路を決める問題と見ることができます．この問題も一般的な配送計画問題では扱うことができず，例えば私の研究している被覆制約付き配送計画問題のような別のモデルを適用する必要があります．

組合せ最適化の研究において，現実に現れる問題をどのようにモデルとして表現するかは重要なポイントであり，なるべく多くの現実問題を網羅できるようなモデルを考えることは，現実へ応用する上でも，また学問として研究する上でも非常に面白い部分です．

現実問題への応用

現実の問題を数理的・統計的に解析して解決しようとする研究はオペレーションズ・リサーチ（operations research, OR）と呼ばれ古くから研究されており，世界中に研究者がいます．私も現実社会の問題を組合せ最適化としてモデル化し，メタヒューリスティクスを適用するというアプローチでのORの研究も行っています．

実際，現実の社会には組合せ最適化の問題として考えることができる問題が多くあります．例えばトラックによる荷物の配達（配送計画問題），コンテナへの荷物の積み込み（パッキング問題），アルバイトのシフトスケジュールの作成（スケジューリング問題），従業員や機械への仕事の割り当て（一般化割当問題）などもすべて最適化問題と言えます．

応用の難しさ

ノートを広げて鉛筆を持ちながら寝ている人のイメージ

現実の複雑な問題であったとしても，組合せ最適化のモデルとして考え，それに対する解法を開発することができれば，あとはコンピュータを用いて良い答えを得ることができます．しかしこれらの問題は未だに人間の頭でその都度考えられている現場も多くあります．単純作業の自動化と違い，こういった複雑な問題はどう自動化すればよいのか見当もつかない場合が多く，なんとなく面倒な仕事だと感じながら放置されていることが多いのではないでしょうか．

また組合せ最適化であるということがわかっても，『現実の問題』から『解を得る』という所までの道のりが全くわからないという人も多いでしょう．ある程度知識のある人ならば，CPLEXやGUROBIなどの汎用ソルバーを用いることができると気づく人がいるかもしれません．しかし汎用ソルバーを用いるにも現実問題をいかに線形計画問題や整数計画問題などで定式化するかという部分には専門的な知識が必要とされます．また定式化の仕方で性能が大きく変わったり，汎用ソルバーで解きやすい／解きにくい問題があったりすることなどを知っていないと，上手く使いこなすことはできません．

パソコンの前で腕を組んで悩む顔をしている人のイメージ

中にはメタヒューリスティクスを知っている人もいると思います．遺伝的アルゴリズム（genetic algorithm, GA）などは聞いたことがある人も比較的多いのではないでしょうか．ある程度のプログラミングの知識があれば実際に動作するプログラムを作成することもできるでしょう．しかし，現実で求められる多種多様な制約を考慮しながらこれらの解法を実装していくと，計算時間が極端に増えてしまったり，思ったような精度の解が出なかったり，そもそも制約を満たすような解が出ないということも有り得ます．

現実の複雑な問題を解くためには，その問題はどのような問題としてモデル化できるのかやその問題にはどのようなアプローチが有効かといったことを見抜く力が必要です．さらに実際に解法を考える際には，経験や思いつきから来るアイデアとアルゴリズムやデータ構造などの知識の双方が必要とされ，研究分野として難しくも楽しい部分と言えます．