組合せ最適化

組合せ最適化問題に対して実用的な近似解法の開発を目指して研究を行います．
組合せ最適化問題は，問題の解が定義される空間や制約などが離散的である問題で，社会で現れる様々な問題は組合せ最適化問題として表現できます．しかし，それらは多くの場合，NP困難な問題で，現実的な計算時間で最適解を得ることは非常に困難です．その一方で，現実の問題では厳密な最適解が必要とされることはまれで，適度な精度の近似解を現実的な計算時間で求める解法で十分に実用的であると考えられています．このような状況では，効率よく近似最適解を求める解法が有用となります．

1. 配置問題

   配置問題とは，配置すべきもの（製品と呼ぶ）の集合と配置される空間が与えられたとき，製品を空間内に，様々な制約の下で効率よく配置する問題です．この問題は，古典的な組合せ最適化問題の１つです．
   2次元配置問題について，一般の図形配置問題の中でも特に大規模な問題に焦点を絞り，性能の高い近似解法の構築を目的とします．一般の図形配置問題では，図形の配置に対して重なりがあるか否かを判定する際，計算コストの高い計算幾何的な処理が必要となり，さらに，それに起因する数値誤差が問題となります．本研究では一般の図形をビットマップ形式で表現された図形で近似したビットマップ図形配置問題を考えます．ビットマップ図形は垂直もしくは水平線分で描かれるレクトリニア図形として捉えることができ，図形の重なりを容易に判定することができます．さらに，レクトリニア図形は長方形と似た構造を持っており，長方形配置問題に対する知見・成果を利用して，高速・高性能なアルゴリズムを設計できます．
   以下の配置の例はレクトリニア多角形を長方形の領域に詰め込む問題に対して，三つの構築型解法により得られたものです．
   

2. 配送計画問題

   配送計画問題は, 様々な制約条件の下で, 複数の車両を用いて複数の客を訪問するような経路の中で, コストが最小のものを求める問題です. 解は客の車両への割り当てと各車両に割り当てられた客の訪問順序により定まります．配送計画問題に対する最も有望な解法の一つは局所探索法です．また，局所探索法を基本ルーチンとして戦略的に探索するなどの方法により，多少時間はかかってもより精度の高い解を求める枠組はメタ戦略とよばれます．局所探索法およびメタ戦略は，単純で普遍的なアイデアであり，解の評価手段と近傍の定義があれば，容易に実現することができます．ただし，高性能な解法を実現するには，データ構造などを工夫した効率的な近傍探索手法が必要不可欠です．

3. スケジューリング問題

   スケジューリング問題は，様々な制約の下で，与えられた全ての業務を行うようにスケジュールを作成するとき，人件費等のコストを最小化することを目的とする問題です．一般にスケジューリング問題には非常に多くの制約があり，すべての制約を満たしつつ効率のよいスケジュールを作成することは極めて困難です ．
   航空乗務員スケジューリング問題に対して，集合被覆問題に基づく列生成アプローチを用いた解法を提案しました．この問題は，一人の乗務員が担当するフライト集合をフライト列と呼ぶことにすると，そのフライト列の組み合わせを求める集合被覆問題として定式化できます．本手法は，有望なフライト列の集合を保持しておき，そのフライト列集合に対する集合被覆問題の線形緩和問題の情報を用いて新たなフライト列を生成する操作を反復する手法です．列生成段階では，動的計画法を用いた分枝限定法で現在の線形緩和問題の解を改善するフライト列を生成します．そして，有望なフライト列集合に対する集合被覆問題を解くことで最終的な解を得ます．