研究分野紹介
私は 組合せ最適化 と呼ばれる分野の中でも特に 配送計画問題 とそれに類する問題の研究をしており， メタヒューリスティクス を用いた，より汎用的な解法の開発を目指しています．現実社会の問題を組合せ最適化としてモデル化し，メタヒューリスティクスを適用するというアプローチでの オペレーションズ・リサーチ の研究も行っています．
本ページでは私の研究分野である組合せ最適化やメタヒューリスティクスなどの紹介をしています．内容に間違いが無いように気を配っていますが，読みやすさを優先したため表現が曖昧となっている箇所もあります．ご了承ください．
目次
組合せ最適化
組合せ最適化とは解の集合が離散的であるような最適化問題のことを指します．ここで最適化問題とは ある制約の元で目的関数の値が最小（または最大）となる状態を求める問題 です．これだけではわかりにくいかもしれませんが，実は普段の生活の中にも組合せ最適化は様々な形で潜んでいます．
あなたは引っ越しをする際に段ボールに物を詰めた経験はあるでしょうか．詰める順番や向きによって微妙な隙間ができたり，表面がデコボコして後から大きな物が入れられないなど，なかなか難しい作業であるかと思います．これはまさに組合せ最適化の１つの例で，
縦横高さが一定の箱
に，
入れる物が傾かないように
物を詰めなければならないという制約の元で
箱に詰め込む物の個数
を最大化する問題であると言えます．
他にも，セールスマンが複数の会社に営業に行くとき，営業先をなるべく効率的に回って移動時間を短くしたいと考えたとします．これは すべての訪問先を１回ずつ訪れる という制約の元で 巡回路の長さを最小化する という問題です．これは組合せ最適化の中でも有名な 巡回セールスマン問題（travelling salesman problem, TSP） の一例です．
配送計画問題
１人の人間が複数の訪問先を回るときにそのルートの長さを最小化する問題は 巡回セールスマン問題 と言えます．しかし現実では複数の人間が分担して複数の訪問先を回ることも多くあります．セールスマンの営業でも複数で分担することは多いでしょうし，宅配便で住宅に荷物を運ぶ場合や，郵便ポストを回って郵便物を回収する場合も同様です．このように，巡回セールスマン問題を複数のルートに拡張した問題を 配送計画問題（vehicle routing problem, VRP） と呼びます．
配送計画問題は古くから研究がなされている分野であり，実社会で求められるような様々な制約を考慮したモデルやそれらに対する解法が提案されています．典型的な設定としては 訪問時間の指定 や 複数の種類の車が混在する場合 などがあります．他にも，例えば複数の荷物をトラックで運ぶ際に，積み下ろしが楽になるように配達順の逆順に荷物を積み込むことがあります．この時，荷物によっては他の荷物を上に積むことができないものもあり，その場合は積み込み順だけでなく配達順を前後させて調整する必要があります． 荷物を積み込む際の制約 を考慮しつつ 配達順序を決める ということは純粋な配送計画問題では取り扱うことはできません．
また，最近では都市部の宅配業務において，トラックをある程度の位置に停めてそこから徒歩でいくつかの配達先に荷物を届けるという方法が採られることがあります．これは
どの配達先にも台車による配達ができるような位置にトラックを停める
という制約の元で，
トラックの走行距離を最小化
するように
トラックの停車位置
と
その巡回路
を決める問題と見ることができます．この問題も一般的な配送計画問題では扱うことができず，例えば私の研究している
被覆制約付き配送計画問題
のような別のモデルを適用する必要があります．
組合せ最適化の研究において，現実に現れる問題をどのようにモデルとして表現するかは重要なポイントであり， なるべく多くの現実問題を網羅できるようなモデル を考えることは，現実へ応用する上でも，また学問として研究する上でも非常に面白い部分です．
現実問題への応用
現実の問題を数理的・統計的に解析して解決しようとする研究は オペレーションズ・リサーチ（operations research, OR） と呼ばれ古くから研究されており，世界中に研究者がいます．私も現実社会の問題を組合せ最適化としてモデル化し，メタヒューリスティクスを適用するというアプローチでのORの研究も行っています．
実際，現実の社会には組合せ最適化の問題として考えることができる問題が多くあります．例えばトラックによる荷物の配達（ 配送計画問題 ），コンテナへの荷物の積み込み（ パッキング問題 ），アルバイトのシフトスケジュールの作成（ スケジューリング問題 ），従業員や機械への仕事の割り当て（ 一般化割当問題 ）などもすべて最適化問題と言えます．
応用の難しさ
現実の複雑な問題であったとしても，組合せ最適化のモデルとして考え，それに対する解法を開発することができれば，あとはコンピュータを用いて良い答えを得ることができます．しかしこれらの問題は未だに
人間の頭で
その都度考えられている現場も多くあります．単純作業の自動化と違い，こういった複雑な問題はどう自動化すればよいのか見当もつかない場合が多く，なんとなく面倒な仕事だと感じながら放置されていることが多いのではないでしょうか．
また組合せ最適化であるということがわかっても，『 現実の問題 』から『 解を得る 』という所までの道のりが全くわからないという人も多いでしょう．ある程度知識のある人ならば，CPLEXやGUROBIなどの 汎用ソルバー を用いることができると気づく人がいるかもしれません．しかし汎用ソルバーを用いるにも現実問題をいかに線形計画問題や整数計画問題などで 定式化 するかという部分には専門的な知識が必要とされます．また定式化の仕方で性能が大きく変わったり，汎用ソルバーで解きやすい／解きにくい問題があったりすることなどを知っていないと，上手く使いこなすことはできません．
中にはメタヒューリスティクスを知っている人もいると思います．
遺伝的アルゴリズム（genetic algorithm, GA）
などは聞いたことがある人も比較的多いのではないでしょうか．ある程度のプログラミングの知識があれば実際に動作するプログラムを作成することもできるでしょう．しかし，現実で求められる多種多様な制約を考慮しながらこれらの解法を実装していくと，
計算時間
が極端に増えてしまったり，思ったような
精度
の解が出なかったり，そもそも
制約を満たす
ような解が出ないということも有り得ます．
現実の複雑な問題を解くためには，その問題はどのような問題としてモデル化できるのかやその問題にはどのようなアプローチが有効かといったことを見抜く力が必要です．さらに実際に解法を考える際には，経験や思いつきから来る アイデア とアルゴリズムやデータ構造などの 知識 の双方が必要とされ，研究分野として難しくも楽しい部分と言えます．