Zenn
🎢

集まって移動する (数理最適化 Advent Calendar 2020)

2020/12/12に公開
Julia
数理最適化
tech

Twitter芸人名@cocomoffです．

この記事は数理最適化 Advent Calendar 2020の12日目の記事です．10日目はpandasを使ったすっきりした数理モデリングの話でした (著者; @ytakashina さん at Qiita)でした．pandasは便利ですね．11日目は双対を幾何学的に捉える (著者; @wosugi さん at Qiita)でした．双対はいつもわからなくなりますね…．

今日はコロナ時代にふさわしくない，集まって移動する問題に関してネットワークフローの立場から書きたいと思います．

移動する

ここではグラフ G=(V,E,w) 上でソース s からシンク t へ移動することを考えます．最短経路問題というやつですね．ネットワークフローを数理最適化の形で書くと，次のような問題です．各エッジ e\in E に対して，ある人がエッジ e を通るか通らないかを選択する2値変数 x_e\in\{0,1\} を用意します．そのためソース s からはある人が出発し，シンク t には到達し，s,t 以外のノードでは入フローと出フローが釣り合う，という制約になります．軽く式で書いておくと

  • 目的関数 : \min_{\{x_e\}} w(e) x_e
  • 制約条件 : \sum_{u\in\delta^+(v)} x_{v,u} - \sum_{u\in\delta^-(v)} x_{u,v} = \mathit{flow}(v)
    • \mathit{flow}(v)はv=sなら1，v=tなら-1，それ以外は0

となります (このあたりは書くのが面倒だったのでUme本開いてください…)．

世の中のライブラリ (例えばpythonのnetworkx) などでは，そのまま最短路アルゴリズムが実装されているので，気軽に呼ぶことができます．例を図に描いて見ました．赤色の線が経路，青色の丸が s，緑色の丸が t になっています．

画像です

複数人が移動する

一人で移動するのは寂しいですので，複数人で移動することを考えます (ここはコロナがない世界です)．ネットワークフローを使う定式化でも，例えば多品種フローなどの難しい定式化があります (このあたりを見てください | Weblio OR辞典)．この記事では個人が適当に最短経路を移動するような世界とすることにしましょう．

各個人に対してフロー制約が成り立つように解くか，もしくは人数分の最短経路を求めるということにします．各個人がバラバラに移動した世界だと，このような感じの図が生成されるでしょうか．

バラバラに移動需要がある世界

みんなで移動したいという世界観の話をしていたので，ここでは更に問題を限定的にし，ある唯一の目的地 (例えばオリンピックの開催会場あたりをイメージして，みんなで集合するような状態を考えてください) に移動するような問題とします．例の図としては，次のような感じを考えることにします．

ある目的地に移動する

集まる地点を選択する

複数の人が移動するのはいいですが，みんなが直接目的地に向かのは寂しい気がしてきました．ここで中間の合流地点にそれぞれの人が移動した上で，中間の合流地点からはオリンピック用の輸送バスで移動するみたいなありがち (たぶん) な状態を考えることにします．

まずは問題を定義していきます．グラフ G=(V, E, w) に対して，Vの中に2つの集合 A, Qを考えます．Q\subseteq Vは個人が所在する初期位置とします．A\subseteq Vは，オリンピック用輸送バスが待機してくれる位置だとします．最後に全員の共通の目的地であるオリンピック会場は t\in V とします．

個人のユーザは，おそらくできるだけ短い時間で移動したいという欲求があります．そのため，Aのうち最短で乗れるバスを選択するという気持ちを考え

\mathit{dist}(q, A) = \min_{a\in A} \mathit{dist}(q, a)

という項を考えておきます (これはグラフ上のノードqから，ノード集合Aへの距離として，最短なものを選択していますが，別のコストでも良いです)．これを用いて，ユーザが輸送バスまで移動するローカルなコスト LTC として

\mathit{LTC}(Q, A) := \sum_{q\in Q} \mathit{dist}(q, A)

を定義します．

一方輸送バスを運営する会社としては，できるだけ最短経路で多くの回数を輸送し，乗車運賃をたくさん稼ぎたいという気持ちになります．そこで輸送地点Aから目的地tの最短経路をコストとして背負ってもらうことにします (雑な前提です)．ただし全部の輸送地点Aから輸送バスを走らせるのは難しそうなので，k箇所の輸送バス線を営業させることにします．これを共通な移動コスト CTC として，A個の候補からS\subseteq A, |S|\leq kを選択すると仮定し，

\mathit{CTC}(S) := \sum_{a\in S} \mathit{dist}(a, t)

とします．なんとなくたくさんの人が乗るa\in Aはもう少し安くなったりしてほしい気がします (逆かもしれないですが) が，できるだけシンプルなモデルから始めることにしましょう．あとは適当なパラメータ \alpha \in [0, 1] を用意して全体コスト GTC として

\mathit{GTC}(Q, A, k) := \alpha \mathit{LTC}(Q, A) + (1 - \alpha) \mathit{CTC}(S)

これで目的関数が定義されました．ここまで読んでくるといつの間にかネットワークフローの話は忘れられて，ただの施設配置問題 (-likeな問題) になったという気がしますね．施設配置問題についてはOR辞典を参考にしてください (施設配置問題)

この問題を解いて図にしていい感じにしてみましょう．ここは数理最適化のAdvent Calendarとしては真面目に定式化して解けという気持ちなのですが，kが小さい場合には全列挙という簡単なアプローチが可能なので，全列挙してnetworkxを利用して解いてみることにします．解いた結果は次のような図になります．だいぶみんなで集まって移動する気配が出てきましたね．

ここでは適当に|Q|=10, |A|=4, k=2とした図を描いてみました．visualizerとgraphを適当に作った影響で若干変な経路が見えますが，ここでは無視することにします (ごめんなさい)．

問題の例 最小コストの解

左側の輸送バスに近い人は左側へ，右側の輸送バスに近い人は右側へ移動した上で，そこから中央の最終目的地へみんなで移動していますね．だいぶ仲が良い感じになってきました．

集まる地点を選択しない

「集まって移動する」最後のネタです．この章だけ2020年ではなく，自動運転が普及した2050年とします．これまでは輸送バスのような例えでやっていきましたが，ハードウェアの制約から解き放たれ，どの場所(ノード)でも好きな自動運転車に乗って移動できる，という感じにしておきます．また知り合いの自動運転車同士が出会った場合，いい感じに自動運転車が変形して一緒に移動できる素晴らしい世界です．

さて，このような問題を考えると，シュタイナー木に近そうな気持ちがしてきますね (気のせいですか？)．ここではシュタイナー木を数理最適化で解きましょう．シュタイナー木問題とは最小全域木問題に近い問題で，いくつかのノード集合 (ターミナルと呼ばれたりします) を結ぶ木を構成する問題です (詳しくはこのあたりを見てください: 離散最適化基礎論 第7回 集合に関する問題 (2)：発展，指数時間アルゴリズム入門)．

ここでは次のような発想で解いてもらうことにします．ターミナルQからフローを流し，コストを最小化します．ただし，ある1つのターミナルq_0\in Qからは他のターミナルへのフローとして|Q\setminus \{q_0\}|本のフローが出るとします．他のターミナルq\in Q\setminus\{q_0\}については，これまで通りフローが1本入るとします．

解いた結果を描いてみました．

だいぶ仲が良い感じになりましたね！

まとめ

世の中にはいろんな数理最適化問題がありますね～ (完)．この記事を書くために利用したプログラムは後ほどgithubに公開する予定です (やらないフラグでしょうか)．それまでの箸休め (?) に僕が書いた劣勾配法の記事でも読んでください(宣伝)．

また来年なにか書くつもりです．

Discussion