2011年06月07日橋本英樹 助教（計算機数理科学専攻）2011/4/1着任

4月に名古屋大学へ着任してしばらく経ち、名古屋での生活も徐々に落ち着いてまいりました。実は、２年前に附属組込みシステム研究センターで研究員をしておりましたので、名古屋大学への着任は今回が２度目になります。再びこの名古屋大学で働くことができ、光栄に思います。

• 

私は、組合せ最適化問題について研究を行っています。組合せ最適化問題は、問題の解が定義される空間や制約などが離散的である問題で、制約を満たす解の中で与えられた指標を最小にするものを求めることが目的です。その適用範囲は非常に広く、社会で現れる様々な問題は組合せ最適化問題として表現できます。 その一例としてロジスティクスにおける配送計画問題があります。配送計画問題は、様々な制約条件の下で、複数の車両を用いて全ての客をちょうど1回ずつ訪問するような経路の中で、コストが最小のものを求める問題です。

図は車両数が３の例です。しかし、組合せ最適化問題は多くの場合、NP困難問題と呼ばれる難しい問題であり、現実的な計算時間で最適解を得ることは非常に困難です。その一方で、現実の問題では厳密な最適解が必要とされることはまれで、適度な精度の近似解を現実的な計算時間で求める解法で十分に実用的だと考えられています。 私の研究では、このような問題に対して、効率よく近似最適解を求めるアルゴリズムの開発を目指しています。具体的には、対象とする問題が持つ良い内部構造を見いだしそれをうまく利用した数理的な手法や、またアルゴリズム中で必要な操作を高速に実現するためのデータ構造の開発を行い、高性能なアルゴリズムの設計をしています。 現実社会に現れる問題は複雑で開発したアルゴリズムを単純に適用できない場合もありますが、より良い解決をするための基盤となる研究を行いたいと考えています。