グラフ上の合流に関する問題とアルゴリズム (データ構造とアルゴリズム Advent Calendar 2020)

この記事は「データ構造とアルゴリズム Advent Calendar 2020」19日目の記事です．18日目は@ryuhe1さん; 線形漸化的数列のN項目の計算，20日目は@tsugarさんです．

本記事ではグラフ上の経路探索に関して，ライドシェアやロジスティクスなどの応用において重要とされる合流に関する問題とデータ構造・アルゴリズムについて雑多に書きます．1つ目の問題として典型問題(?)である集合点を求める問題(Optimal meeting point (OMP) query)を紹介します．2つ目の問題としてOMPを拡張した選好経路に基づいた集合点に関する問題を紹介します．

1. Optimal Meeting Point query on graphs

これはいろんな場所に人々が点在しているときに，どこで待ち合わせしたらいいかを考える問題です (ここはコロナが存在しない世界ですので，集合しても問題ありません)．

問題の定義

距離関数を $d$ とします (グラフ上の距離$d$でも良いです)．OMPの世界では，一般に移動距離の和を最小化する点を見つけるmin-sum型と，最も遠い人からの距離を抑えるmin-max型の問題提議があります．

所与の地点 (顧客がいる地点や頂点の集合) を$Q=\{q_1,\dots, q_n\}$とすると

• min-sum型: $x^\star = \arg\min_{x} \sum_{i=1}^n d(x, q_i)$
• min-max型: $x^\star = \arg\min_{x} \max_{i} d(x, q_i)$

です．2次元の場合にどのような差がでるのか，(軽く離散化して手抜きをした)プロットの例から見てみます．maxを抑える場合は左の離れた点に引っ張られ，sumを抑える場合は，特に2次元平面上で$d$がユークリッド距離のため，重心に引っ張られます．

似たような問題をグラフ上でやってみると (このグラフはこちらの記事で使ったものをパクってきました: 集まって移動する (数理最適化 Advent Calendar 2020))，グラフ上の距離 (ネットワーク距離) を用いるという違いはありますが，似たような雰囲気の結果が得られます．

形式的に書いておくと，OMPは次のような問題です．

Input: グラフ$G=(V, E)$, 地点$Q$
Output: 目的関数を最適化する地点$x^\star\in V$

アルゴリズム

naive

想定している距離 $d$ がユークリッド距離のように，我々の平面上の直感がうまく働きそうな場合には，目的関数 (例えばmin-sum型の $\sum_{i} d(x, q_i)$) を微分し，徐々に解 $x$ の座標を更新していくことができました (min-max型ではもう少し工夫がいります)．

一方で距離がネットワーク距離になっている場合には，グラフ $G=(V, E)$ 上を探索していく気持ちになります．論文で示されている通り，解は $Q\cup V$ に含まれているためすべての候補を探索すれば良いです．具体的にはパラメータを$|Q|, |V|$としたとき，二乗オーダーぐらいのnaiveアルゴリズムを構築できます．事前に全頂点対最短経路や最短経路距離を前処理で格納しておくことで，(比較的)効率的に，かつ簡単な実装で求まりそうです．

改良

上に言葉だけで説明したアルゴリズムは，これまでの (論文以前の，という意味です) アプローチと比較して効率的ですが，$V$と$Q$の位置関係によっては，考慮する必要のない頂点$v\in V\cup Q$を探索することがありそうです．

例えば$Q$がある地域に集中している場合，直感的には$Q$を含む最小の凸包を考えると十分な気がしてきます (論文図3(a)を見てください)．凸包の計算は$O(n\log n)$のオーダですので，二乗オーダの全探索以前に計算しておくことで，探索する範囲が小さくなり，実験的には高速化しそうな雰囲気があります．

しかしネットワーク構造に依存して例外が存在します (論文図3(b))．

この図のように，ネットワークのトポロジが悪さをした結果，幾何的なconvex hullに含まれない迂回頂点が発生する例を作ることができます．これを対処するには，最短経路を用いたグラフ上の最短経路に基づく凸包 (簡単に言えば，任意の頂点間の最短経路を構成する頂点がその包に含まれるような集合です) を計算すれば良いです．

提案手法では通常の凸包を構築した後に，最短経路を補い，それを用いて探索範囲の凸包を構築します．ちなみにこの処理の最適性はどうなんでしょうか！？知らないです（は？）．

この関数で計算される凸包を$V$の探索範囲とすることで ($Q$はすべて探索します)，所望の頂点を求めることができました．具体的に適当にサンプリングした点と，真面目に最短経路凸包を計算した結果を図にしてみました．

convex hull	最短経路を追加していった図

2. $k$-OMP based on Preferred Paths

これは人々が職場から自宅に帰ろうとしているときに，「今日一杯飲んでいく？」といって全員があるお店に集合する場合に都合の良い場所をk個ぐらいリストアップする問題です(ここはコロナが存在しない世界ですので，飲み会のために寄り道しても問題ありません)．

定義

1.で書いた問題と同様にグラフ$G=(V, E)$を考えます．問題設定はほとんど似ていますが，少しだけ前提が異なります．1つ目はPOIが存在すること，2つ目は選好パスを持っていることです．

1つ目についてです．今，頂点$V$上にPOI (Point of Interestsの略で，要するにお店などがあるチェックイン地点のようなものです)が集合 $C$として与えられるとします．

これは例えば飲み会を開催する候補の集合のようなものです．

2つ目についてです．今，各$n$ユーザは，出発地(o)と目的地(d)を持っていて，最短経路などのユーザが希望する経路で移動しようとしています．

たとえばユーザ$n$がいつも通勤につかっているような経路がデフォルトで設定されています．

またグラフや経路上には分岐点 (branching point) を想定しています．これは移動する際に経路を変更しうる点として設定されています．ただし基本的にはグラフ$G$がうまく用意されていて，移動がいい感じにできる (途中で寄り道できるような頂点が十分用意されている)，ぐらいのイメージで良いと思います．

距離の定義

あるPOI $o_j$ からパス $p_i$ への迂回距離として， $p_i$ に含まれる分岐点のうち最小な位置へのネットワーク距離として定義します: $\mathit{dd}(o_j, p_i) := \min_{b_i^k\in p_j} d_n(o_j, b_i^k)$ です．ここには行き帰りの分のコストが表現されていると想定しておきます (すべて2倍なので)．

$n$ユーザの選好パス集合 $p_\mathit{set}$ が与えられたとき，あるPOI $o_j$ から集合 $p_\mathit{set}$ への 集団迂回距離 (GDD) として，$p_\mathit{set}$ に含まれる経路への迂回距離の話として定義します: $\mathit{Gdd}(o_j, p_\mathit{set}) := \sum_{i=1}^n \mathit{dd}(o_j, p_i)$ です (ただし$\forall p_i\in p_\mathit{set}$です)．

問題の定義

今考える問題 ($k$-OMP$^3$) は次のような形式です．

Input: $n$ユーザの選好パス集合 $p_\mathit{set}$, POI集合 $C$
Output: $A\subseteq C, |A| = k$ であり $\forall o_i\in A, o'\in C\setminus A$ について $\mathit{Gdd}(o_i) < \mathit{Gdd}(o')$ を満たすもの (上で定義した集団迂回距離が小さいPOI $k$個)

アルゴリズム

問題を解く方法を見ていきます．

naive

一番naiveな手法としては，$A\subseteq C, |A|=k$をすべて試すことでしょうか．例えばPythonを使えば，networkxとitertools.combinationsを使えば最低限の機能を実装できそうです．

改良

1.の手法と同じく，うまく計算を効率化していきたいです．論文の提案手法は，次のようなものになっています．楕円とGNNqueryを用いて探索範囲をうまくpruningするという基本的なアイデアは似たものになっていますね．

1. Group nearest neighbor query (GNNquery) を用いて，出発地点の幾何中心 $c_s$ (centroidの意味です)と目的地の幾何中心 $c_d$ から都合の良い地点を$k$個初期解として選ぶ
2. 選ばれた初期解を用いて目的関数値 $\mathit{Gdd}$ のtop-$k$個 ($\mathit{Gdd}^k$ と書く) を計算して格納する
3. $c_s$ と $c_d$ を焦点とする楕円を描き，楕円に含まれるPOIに対して目的関数値を計算し，$\mathit{Gdd}^k$を更新する
4. 最終的にtop-$k$なPOI地点を解として返す

ここでは初出のGroup nearest neighbor queryについて型を説明します．GNNqueryは以下の処理を実現するものです．

Input: $N$個の点$\{p_1,\dots,p_N\}$と，$n$個のクエリ点$\{q_1,\dots,q_n\}$
Output: 距離$\mathit{dist}(q, Q)$を最小とするような$k$個のクエリ点: ただし $\mathit{dist}(q, Q) := \sum_{i=1}^n |pq_i|$ ($|pq_i|はユークリッド距離)$

なぜネットワーク距離を用いた$\mathit{Gdd}$を計算する問題にユークリッド距離のquery (とそれを実現するデータ構造) が使われているのかというと，ネットワーク距離の上限を計算するときに，平面上のユークリッド距離の三角不等式を用いているためです．詳細な証明は省きますが

(ユークリッド距離の三角不等式) => (迂回距離 $\mathit{dd}$)に関する不等式 => (集合迂回距離 $\mathit{Gdd}$)に関する不等式

と展開し，集合迂回距離に関する不等式を用いて，$\mathit{Gdd}^k$の改善に寄与しない範囲のPOIを楕円の外においやることで，楕円内部だけを探索することで効率的な処理を実現しました．テクニカルですね．

まとめ

本記事ではグラフ上の経路探索に関して，ライドシェアやロジスティクスなどの応用において重要とされる合流に関する問題とデータ構造・アルゴリズムについて雑多に書きました．

参考文献

• Da Yan, Zhou Zhao and Wilfred Ng: Efficient Algorithms for Finding Optimal Meeting Point on Road Networks, VLDB2011
• Elham Ahmadi, Mario A. Nascimento: $k$-Optimal Meeting Points Based on Preferred Paths, SIG-SPATIAL2016
• Jin Soung Yoo, Shashi Shekhar: In-Route Nearest Neighbor Queries, GeoInformatica 9:2, pp.117-137, 2005
• Dimitris Papadias, Qiongmao Shen, Yufei Tao, Kyriakos Mouratidis: Group Nearest Neighbor Queries, ICDE2004