研究内容

組合せ最適化問題に対する実用的な近似解法の開発

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

主な研究テーマとして行った研究は，2次元と3次元の配置問題に対する近似解法の研究です．また，乗務員スケジューリング問題と配送計画問題に対する効率的な近似解法などの研究も挙げられます.

「研究テーマ」
配置問題：
配置問題とは，配置すべきもの（製品と呼ぶ）の集合と配置される空間が与えられたとき，製品を空間内に，様々な制約の下で効率よく配置する問題です．この問題は，古典的な組合せ最適化問題の１つであり，これまで多くの研究がなされてきました．これらの問題の直接的な応用先として，鉄鋼・ガラス・繊維などの素材産業，集積回路の設計，倉庫やトラックの効率的な運用などが挙げられます．計算の複雑度という観点から見ると，ほぼ全ての配置問題はNP困難に分類され，多項式時間で厳密な解を求める手法はおそらく存在しません．このような状況にあるため，性能の良い近似解法の開発が非常に重要であると考えられています．

配置問題について，現在は主に以下の問題，

• 長方形配置問題
• レクトリニア図形配置問題
• ビットマップ図形配置問題
• 曲線を含む一般の図形配置問題
• 直方体配置問題

に対する研究を行っています．

配送計画問題：
配送計画問題は, 様々な制約条件の下で, 複数の車両を用いて複数の客を訪問するような経路の中で, コストが最小のものを求める問題です．配送計画問題の一般化である被覆制約付き配送計画問題に対して，研究をおこないます．被覆制約付き配送計画問題は集合被覆問題と配送計画問題を組み合わせた問題です．この問題では，訪問できる点（訪問点）の集合とそれらに被覆される点（被覆点）の集合が与えられたときに，複数の車両を用いて全ての被覆点を被覆できるような一部の訪問点を訪問し，そのような経路の中で，コストが最小のものを求める問題です．

スケジューリング問題：
乗務員スケジューリング問題は，様々な制約の下で，与えられた全ての業務を運航するようにスケジュールを作成するとき，人件費等のコストを最小化することを目的とする問題です．一般に乗務員スケジューリング問題には非常に多くの制約があり，すべての制約を満たしつつ効率のよいスケジュールを作成することは極めて困難です．これまでは，航空乗務員スケジューリング問題や，バス乗務員スケジューリング問題に対して，集合被覆問題に基づく列生成アプローチを用いた解法を考えました．