2017年02月24日計算機数理科学専攻 情報数理モデル論講座
柳浦・胡研究室（柳浦睦憲教授，胡艶楠助教）
「今いる所から目的地に最も早く着くにはどうしたらよいだろう」
ということを考える機会がときどきあると思います．
このように最も良い方策を見つける問題を一般に最適化問題と呼びます．
私達の研究室では，このような最適化問題の中でもとくに組合せ的な構造を持つ
組合せ最適化問題に興味を持って研究を行っています．
たとえば，
さまざまな形の箱をできるだけ隙間なくコンテナに詰め込む，
看護師の要望をできるだけ反映した勤務表を作成する，
宅配便の効率的な配送計画を行うなど，
解決すべき組合せ最適化問題は世の中に無数に存在します．
以下に直方体の箱をコンテナに詰め込んだ一例を示します．
このように形状をできるだけ隙間なく詰め込むという問題は，
2次元や3次元のさまざまな形状に対して研究されており，
倉庫やトラック等に物をなるべくたくさん詰め込むというような
効率よい詰込みを求める応用の他に，
大きな布から洋服の部品を切り出したり，
大きな鉄板から船や自動車等の製品の部品を切出し，
製品にならない無駄な部分をできるだけ少なくするというような応用もあります．
2次元の場合の例として，服の部品を切り出すレイアウトの一例と，
レクトリニア図形すなわち縦横の線のみからなる図形を詰め込む
レイアウトの一例を紹介しておきます．
最適化の対象は効率化だけではありません．
夏休みに片道切符1枚でどれだけ長く鉄道旅行できるかを考えるのも，
最適化問題のひとつです．
このような問題をコンピュータを用いて解くには，
問題を解くための手続きを設計する必要があります．
そのような手続きのことをアルゴリズムと呼びます．
出発地から目的地までの最短のルートを求める問題には
効率の良いアルゴリズムがあり，カーナビなどに応用されています．
しかし，「いくつかのお店で買い物をして自宅に帰るまでの最短のルートを求める」
という問題は，一見最初の問題に似ているように思えるにもかかわらず，
難しいことが知られています．
問題の難しさを解明したり，
効率の良いアルゴリズムを開発するのが主要な研究テーマです．
身近な現実問題を解決するソフトウェアの開発にも力を入れています．
たとえば京都大学数理解析研究所(RIMS)では，毎年数十件の研究集会が
開催されています．それらの日程と開催場所のスケジューリングは，
これまで人手で行われており，かなりの時間を要していましたが，
この作業を支援するソフトウェアを作成し，
RIMSの共同利用掛に提供しました．
また，電気系の学生実験において学生を実験テーマに割り当てる作業など，
先生方がこれまで人手で行われていた大変な作業を自動化するソフトウェアを作り，
作業担当者に提供しました．
日頃の活動が評価され，2016年には研究室のメンバーが以下のような賞をいただきました．
研究室の学生の受賞に関する情報については以下のURLを参照してください．
http://www.co.cm.is.nagoya-u.ac.jp/~yagiura/jusho-gakusei-etc.html
・水野竜太郎，スケジューリング学会 奨励賞，2016
・澤井佑樹他，スケジューリング学会 学術賞，2016
・澤井佑樹，日本オペレーションズ・リサーチ学会 学生論文賞，2016
・董航，日本オペレーションズ・リサーチ学会研究部会「評価のOR」学生奨励賞，2016
・胡艶楠，エクセレントドクター賞 名古屋大学大学院情報科学研究科，2016
・松下健，第12回キャンパスベンチャーグランプリ全国大会 審査委員会特別賞，2016
最適化の対象は効率化だけではありません．
多くの現実問題を解決できる便利なアルゴリズムを作りたいと思っています．