最適化一口話

仕事として数理最適化を実践している立場から、その中身や可能性について概説しております。

「重ね合わせ」タイプのモデル応用その二: ネットワーク問題

ネットワークというと何か面倒そうに聞こえますが、 「双六」に沢山の枝分かれが付いたものをイメージすれば大体合っていて、 駒の止まるマスと、マスを継ぐ線からできているひとまとまりを言います。 とある高校の球技大会でのことです。 2年は「バスケ」のあとに「野球」、 3年は「サッカー」のあとに「テニス」が組まれています。 学校としては時間の読めるバスケとサッカーを先にして、 時間の読めない「野球」と「テニス」を後半に持ってくるよう 気を効かせたつもりだったのですが、 不幸にして「バスケ」と「サッカー」の終了時刻が揃ってしまったため 応援の2年全員が体育館から野球場に、 3年がグラウンドからテニスコートに、それぞれ同時に大移動、 渡り廊下(点線)で渋滞を起こして大半が応援に間にあわない、 といった事態になりました。 下にあるのが試合会場の位置関係と廊下の接続具合を示した「双六」もとい、「ネットワーク」の絵です。 2年の「振り出し」/「上がり」は青、3年のは赤で示しました。 数理最適化に現れる「双六」にはこのように「振り出し」と「上がり」が二つ以上現れたりします。

f:id:optimizationTanabe:20160425182613p:plain

渋滞の理由は 2年、3年が取った標準的な経路(下の絵)を見ると明らかです。 2年、3年の取る経路が途中の廊下で重なっていたためですね。

f:id:optimizationTanabe:20160425182655p:plain

解消するには次に示すような別の経路に適宜生徒を誘導すればよいはず。

f:id:optimizationTanabe:20160425182719p:plain

ただ、3年は遠まわりになりますし、こちらはこちらで経路が重なっています。 全員をこのように誘導すると、カーナビのせいで裏道が混んでしまうのと同じで 今度は外回りの経路で渋滞しそうですから、 生徒を「標準の経路」と「別の経路」に配分して誘導する必要がありますが、 さあどうすればよいでしょう?

じつはこの問題、「重ねあわせ」のパターンの一つの典型的な応用になります。 廊下に番号を振ってみました。 例えば 2年の青い経路に人を一人通すと、 その経路を構成する廊下{1,4,8,9} が一人分混む。 3年の同じく真ん中の経路に一人通すと、廊下{3,4,6}が一人分混む。 すなわち「経路」に一人通すと、対応する「廊下」が複数「セット」になって混みます。

f:id:optimizationTanabe:20160425182742p:plain

生徒は 2年,3年がそれぞれ 100 人ずつ居るとしましょう。 問題の狭い渡り廊下(4番)の容量は 50人分, その他の廊下の容量は 150人分 とします。 容量を超えないように 2年,3年の経路を二つずつ適当に重ね合わせるという 気持を表現すると次の数理最適化モデルになります。 これまで見てきた「重ねあわせ」タイプのモデルと同じ構造をしてますね。

f:id:optimizationTanabe:20160425182813p:plain

経路が一つしか通ってないので容量超えの心配のないところは 抑え(制約)を入れていません(数理最適化では意味のない制約をこうして 削るのが効率化のコツ)。果たして最適化の答は..? 次のようになりました。 3年の経路を二つに割って、渡り廊下の容量をぎりぎりまで使う (この経路は短かいので推奨されます)。 そして、他は適宜合わせるというものです。

f:id:optimizationTanabe:20160425182846p:plain

当たり前すぎて面白くない ? 確かに。 この程度ならば人間が瞬時に導くことができます。 しかしこのネットワークの規模が大きくなるとどうでしょう。 考えられる「経路」の数は「○」と「-」の数を大きく上回る勢い (我々の業界の言葉ではこれを「組み合わせ的に」とか言います)で増えて、 「○」が数十個の規模のネットワークでも 人間が場当たり的に最適解を作ることはすぐにできなくなってしまいます。 一方、機械にとっては「経路」(=「詰め合わせのセット」)を列挙して量産することはじつに簡単。 かくして数理最適化は「道路交通網」の渋滞の緩和とか「通信網」におけるルーティングといった 問題に広く応用されるようになっています (実際の渋滞の緩和モデルではもっと精緻に容量の上限と 実際に通っている人の比率で通過速度が決定する、といったモデルになります)。

ネットワークが数千、数万といった規模になって、 経路が無限に近いくらいになったらさすがの数理最適化も困るだろうって? そんな状況にも「列生成法」という解決がちゃんと用意されています。 その話もまた別の機会に。