» 柳浦睦憲　教授｜名古屋大学情報学部

情報を最大限に活かす「組合せ最適化」

柳浦睦憲　教授

【所属】大学院情報学研究科　数理情報学専攻
【担当】情報学部　自然情報学科

「最適」な「組合せ」は仕事効率化・資源節約のキーとなる

-先生の研究はどんな研究ですか？

与えられたいろいろな条件のもとで、なるべく良い解や方法を求めようとする「組合せ最適化」です。身近な例では、宅配業者などが荷物を配達する際になるべく短時間で回れる道順を考える、というようなことが挙げられます。主な研究には、与えられた多角形を入れ物に無駄なく詰め込むには？洋服の部品を大きな布から効率よく切り出すには？トラックや飛行機に隙間なく荷積みするには？を考える「図形パッキング」があります。また自動車をつくるための鉄板をいかに無駄なく切り出すかという問題では、無駄を1％削減するだけで費用を年間億単位で減らせます。このような生産効率の問題は環境問題にもつながるため、重要なことなのです。

企業でも、たとえば看護師の勤務スケジュールを組むソフトウェアの開発をしているところがあります。病院としては看護師にどの時間帯にもいてもらいたいという要望があります。一方看護師としては体に無理なく法の範囲内でしか働けないという制約があります。両者を考慮した上で最適な勤務スケジュールを考えるのは至難の技です。そのようなスケジュールを自動で設計できるように組合せ最適化の技術が利用されています。

アルゴリズム設計のために必要な力 ≒ パズルを解く論理力

-どんな知識が必要ですか？どんな人が向いていますか？

数学やプログラミングの知識を使いますが、必ずしも両方が得意である必要はありません。どちらかが好きであれば組合せ最適化を好きになる素養があると思います。コンピュータに何か問題を解かせるためには、コンピュータがどう動くかを決める「アルゴリズム」をつくらなければなりません。「アルゴリズム」とは、問題を解くなどの目的を達成するために行う計算手順のことで、プログラムを書くための手順書や仕様書のようなものです。プログラムには、文法上こうでなければならないといった、それぞれの言語のルールがあるのですが、アルゴリズムはどんな言語ででも書けるよう、手続きの大事な部分だけが、「変数xに7を代入せよ」というような、人が理解できる表現で書いてあるのです。アルゴリズム自体は紙と鉛筆で書き、ちゃんと動くことを確かめるためにコンピュータを使うというイメージです。アルゴリズムが速く正しく動くことを証明するのに数学も使います。アルゴリズムの歴史はとても古く、素数を発見するものや最大公約数を求めるものなど、紀元前からあるんですよ。もともとは数学用語なのです。

数独やお絵かきロジックなどのパズルが好きな人も、この分野の研究には向いていると思います。可能性が少ないところから攻め、これは有り得ないといえる選択肢を論理的につぶしていって答にたどり着くという、パズル的な要素が組合せ最適化の研究にはあるからです。

カーナビ、鉄道のダイヤ、プロスポーツ、さまざまな分野を支える技術

-先生の研究は、どんな形で私たちの暮らしの中で見かけることができますか？

一番わかりやすいのは、目的地への最短ルートを見つけてくれるカーナビです。そのためのアルゴリズムが無ければ、カーナビは存在しなかったと言えます。鉄道のダイヤをどう組めば、列車同士の接続が良く車両を効率的にやりくりできるか？野球やサッカーなどプロスポーツで、リーグ全体でどのようにホームゲームとアウェイゲームを組めば、効率的な移動と平等性が確保できるか？また、理系の人がよく使う、文章のレイアウトソフト上で、英文の文書の行の右端を揃えるには？といったことにも最適化が応用され、さまざまな分野を支えています。

試行錯誤してうまく証明できた時の快感が忘れられない、だからやめられない

-先生はなぜ、この研究を志したのですか？

数学が好きで、「数」の文字が付いていることにひかれたという安易な理由で選んだ数理工学科で何となく面白そうと思って入った研究室でたまたまこの分野に出会いました（笑）。最適化は生産、物流、サービスなど、あらゆるものの効率化に役立つ学問であるという魅力が進学して研究を続けようと思った理由のひとつです。実際私が教えている学生にも、研究室を選んだ理由はパソコンや数学が好き、何となく（笑）などいろいろですが、純粋な数学に比べ、応用が見えて面白いと言う人が多くいます。

実験で良い結果が出た時、試行錯誤して証明できた時の快感も大きいですね。先ほどの自動車工場での鉄板の話ですが、鉄板って厚みが均一ではなく、製品によってはなるべく真ん中から切り出したいなどの要望があるのです。単純に無駄が少なければよいという問題でも難しいのですが、そのような要望が加わるとますます問題が難しくなります。こんな風に問題が難しくなると、うまくいった時の喜びも一層大きくなります。やめられないですね（笑）。

看護師の話ですが、より少ない人数で病院の要望を満たすスケジュールを作るという方針だけで最適化してしまうと、病院にとっては良くても、現場で働く看護師にとっては必ずしも嬉しいものになっていない可能性があります。実際にはいろいろな要因を考える必要があって、たとえば看護師同士の平等性を考慮することがしばしば求められますが、これは容易ではありません。母が心理学を専攻しており、自分もやってみようと思ったこともありました。平等と感じるかどうかを考えるのに例えば心理学とかけあわせると、何かできるかもしれませんね。

あるだけの情報では意味がない。活きた情報にかえ、新しい価値を産み出そう

-情報学部を目指す受験生へのメッセージをお願いします。

私が学生だった頃の計算機は、何百万円もするものであっても性能は今のノートパソコンより低く、そのような計算機で実験していました。当時、理論的には面白いが使えないとか、時間がかかって不可能と言われていたことが、今ではできるようになってきています。それを実現する高性能な計算機が安く手に入るようになったということです。しかも、交通情報、気象情報、人々の買い物情報などあらゆる情報が、大量にリアルタイムで蓄積されるようになり、より正確なデータにもとづき綿密な最適化ができるようになりました。将来はもっと進んでいるに違いないと思います。そういう技術を活かせるかどうかは、良いアルゴリズムをつくれるか否かにかかっています。