研究室紹介: 柳浦・胡研究室

「寄りたいお店が10箇所位あるが時間がないから5箇所位しか寄れない．どれに行こう?」とか「今いる所から目的地に最も早く着くにはどうしたらよいだろう?」ということを考える機会がときどきあると思います．このように最も良い方策を見つける問題を一般に最適化問題と呼びます．私達の研究室では，このような最適化問題の中でもとくに組合せ的な構造を持つ組合せ最適化問題に興味を持って研究を行っています．

図1. 直方体の詰込み

たとえば，さまざまな形の箱をできるだけ隙間なくコンテナに詰め込む，看護師の要望をできるだけ反映した勤務表を作成する，宅配便の効率的な配送計画を行うなど，解決すべき組合せ最適化問題は世の中に無数に存在します．直方体の箱をコンテナに詰め込んだ一例を図1に示します．

このように形状をできるだけ隙間なく詰め込むという問題は，2次元や3次元のさまざまな形状に対して研究されており，倉庫やトラック等に物をなるべくたくさん詰め込むというような効率よい詰込みを求める応用の他に，大きな布から洋服の部品を切り出したり，大きな鉄板から船や自動車等の製品の部品を切出し，製品にならない無駄な部分をできるだけ少なくするというような応用もあります．2次元の場合の例として，服の部品を切り出すレイアウトの一例（図2）と，レクトリニア図形すなわち縦横の線のみからなる図形を詰め込むレイアウトの一例（図3）を紹介しておきます．

図2. 服の部品を切り出すレイアウト
図3. レクトリニア図形の詰込み

最適化の対象は効率化だけではありません．夏休みに片道切符1枚でどれだけ長く鉄道旅行できるかを考えるのも，最適化問題のひとつです．

このような問題をコンピュータを用いて解くには，問題を解くための手続きを設計する必要があります．そのような手続きのことをアルゴリズムと呼びます．出発地から目的地までの最短のルートを求める問題には効率の良いアルゴリズムがあり，カーナビなどに応用されています．しかし，「いくつかのお店で買い物をして自宅に帰るまでの最短のルートを求める」という問題は，一見出発地から目的地までの最短ルートを求める問題に似ているように思えるにもかかわらず，難しいことが知られています．問題の難しさを解明したり，効率の良いアルゴリズムを開発するのが主要な研究テーマです．

身近な現実問題を解決するソフトウェアの開発にも力を入れています．たとえば京都大学数理解析研究所(RIMS)では，毎年数十件の研究集会が開催されています．それらの日程と開催場所のスケジューリングは，これまで人手で行われており，かなりの時間を要していましたが，この作業を支援するソフトウェアを作成し，RIMSの共同利用掛に提供しました．また，名古屋大学の電気系の学生実験において学生を実験テーマに割り当てる作業など，先生方がこれまで人手で行われていた大変な作業を自動化するソフトウェアを作り，作業担当者に提供しました．

日頃の活動が評価され，研究室のメンバーがいくつかの賞をいただいています．研究室の学生の受賞に関する情報については以下のURLを参照してください．
http://www.co.mi.i.nagoya-u.ac.jp/~yagiura/jusho-gakusei-etc.html
最適化の対象は効率化だけではありません．多くの現実問題を解決できる便利なアルゴリズムを作りたいと思っています．

注．胡先生は2020年春に東京理科大に移動されました．これは胡先生が在籍中の記事ですが，胡先生の異動後も上述のテーマをはじめとして胡先生との共同研究を続けています．

連絡先と関連ページ

数理情報学専攻研究アクティビティ, 研究グループ紹介, 数理情報学専攻, 自然情報学科, 数理情報系, 組合せ最適化, アルゴリズム

Posted by 柳浦 睦憲