後悔最小化による交通グラフ上の代表的経路集合の高速計算

DEIM Forum 2016 A8-4

後悔最小化による交通グラフ上の代表的経路集合の高速計算

秋葉 拓哉

†

_{吉田 悠一}

†

†

国立情報学研究所

〒 101–8430 東京都千代田区一ツ橋 2-1-2

E-mail:

†{

takiba,yyoshida

}

@nii.ac.jp

あらまし

2 点間を移動する経路を計算することは，交通ネットワークにおける最も重要な処理の 1 つであり，地図

アプリケーションやカーナビゲーションシステムなどの重要な応用を持つ．本論文では，距離，所要時間，金額など

からなる多次元のコストがついたグラフとして交通ネットワークを定式化し，様々な好みを持つ多数のユーザを満足

させるような代表的な経路を計算することを目標とする．この問題を最大後悔割合の考え方に基づき定式化し，高速

に代表的な経路を計算するアルゴリズムを提案する．

キーワード

グラフ, 交通グラフ, 経路探索, スカイライン問合せ, 多基準意思決定

1.

は じ め に

交通グラフ上で2点間を移動する経路を計算することは，交 通ネットワークにおける最も重要な処理の1つであり，地図ア プリケーション，カーナビゲーションシステム，配送計画，交 通シミュレーションなど様々な応用を持つ．これまでの多くの 研究では，交通グラフは単一基準の重みつきグラフとみなされ， 単一基準のグラフにおける最短経路の計算の高速化が取り組ま れてきた[1]． 本論文では，交通ネットワークのより現実的なモデルとして， 距離，所要時間，金額などからなる多次元のコストがついた多 基準グラフを採用する．このモデルでは，各ユーザが異なる選 好ベクトルを持ち，ユーザにとっての経路のコストは，選好ベ クトルとコストベクトルの内積として定義される（詳しい定義 は2.章を参照）．本論文の目標は，このモデルの下で，多基準 グラフと始点・終点が与えられた時，ユーザを出来るだけ満足 させるような代表的な経路集合を提示することである． 一つのアプローチは，ユーザの選好ベクトルを入手し，それ に基づき問題を単一基準グラフへ帰着することである．しかし， ユーザの選好ベクトルを入力させることは大きな手間となる上， 実際にはユーザ自身も自分の選好ベクトルを正確に表現するこ とが困難である場合も多い．また，ユーザの選好ベクトルを自 動的に推定することも考えられるが，そのためにはそのユーザ に関する十分量のデータの蓄積が必要になる．さらに，単一基 準グラフで複数の経路を提示するための標準的なアプローチで あるtop-k最短経路は，実グラフでは，図1aのように，ごく 一部のみが異なり，残りのほとんどの部分が重なってしまうよ うな出力となることが多い． 別のアプローチとして，パレート最適なコストを持つ経路 である経路スカイラインを全て求める研究も行われてきてい る [3,6]．このアプローチであれば，ユーザの選好ベクトルを 事前に入手する必要は無い．しかし，経路スカイラインの数は， グラフのサイズに対し指数的に増加し，莫大な数となってしま う．例えば図1bでも，これだけ近い頂点対に対して228本の 経路スカイラインが出力されてしまっている．また，最新のア (a) Top-k 最短経路 (b) 経路スカイライン (228 個) (c) 最大後悔割合最小化 (本研究) 図1 異なるアプローチによる代表的経路集合の比較(k = 4). ルゴリズムを用いても，計算に非常に時間がかかる． そこで，本論文では，代表的な経路集合の計算を，最大後悔 割合の最小化問題として定式化する．最大後悔割合は，多次元 の大規模点集合データから代表的な点集合を選択するために提 案された考え方である[4]．本論文では，最大後悔割合は，経 路の集合に対し定義され，任意の選好ベクトルを持つ人を仮定 した時に，コストの意味でどの程度損をするか，という割合の 最大値に相当する（詳しい定義は2.章を参照）．これが小さい ほど多くの人を満足させることのできる良い代表的経路集合で あると考える． 本論文では，始点と終点，及び整数kが与えられた時，最大 後悔割合が小さいようなk本の経路の集合を計算するアルゴリ ズムを提案する．このアプローチで計算された経路集合の例は 図1cである．このアプローチでは，事前にユーザの選好ベク トルを入手する必要がない．一方，出力はk 本の経路であり， スカイラインのように出力される経路が多すぎることもない． また，top-k最短経路のように経路が似すぎることも無い．そ して，提案するアルゴリズムは経路スカイラインを列挙するア ルゴリズムよりも遥かに高速であり，実用的である．

2.

事 前 準 備

非負の実数及び整数を_R+,Z+ と表す．整数n >_{= 0}に対し， [n]は集合_{{1, 2, . . . , n}}を表す. ベクトルはxやyのように 太字で表記する．2つのベクトルx, y∈ Rdに対し，_{⟨x, y⟩}は

内積を表す．単一基準（重みつき）グラフは，V を頂点集合， E を辺集合，c : E→ R+を重み関数として，G = (V, E, c)と して定義される．G内の経路P について，ℓG(P )を P の経 路長として∑_e∈Pc(e)と定義する．2頂点s, t∈ V について， PG(s, t)をsからtへの全ての経路の集合とする．s, t間のG 内での距離dG(s, t)はminP∈PG(s,t)ℓG(P )として定義される． 多基準グラフはV を頂点集合，E を辺集合，c : E→ Rd + を 重み関数として，G = (V, E, c)として定義される．dをグラフ の次元と呼ぶ．d次元の多基準グラフG = (V, E, c)と選好ベ クトルw∈ Rd+に対し，重み関数cw: E→ R+ を各辺e∈ E に対しcw(e) =⟨c(e), w⟩として定義し，単一基準グラフGw を(V, E, cw)として定義する．簡潔さのため，多基準グラフG が明確な場合，ℓGw(·)やdGw(·, ·)をℓw(·)やdw(·, ·)と表記 する． 2. 1 多基準グラフにおける経路集合の最大後悔割合 以下，G = (V, E, c)を多基準グラフ，s, t∈ V を始点・終 点とし固定して考える．本論文では，経路 P ∈ PG(s, t) と P (i) = ∑_e∈Pc(e)(i) として定義されるベクトル P ∈ Rd + をしばしば同一視する．選好ベクトル w ∈ Rd+ に対する 経路 P のコストは ⟨P , w⟩ として定義される．後悔値，後 悔割合，最大後悔割合は以下のように定義する．選好ベク トル w に対して，経路集合 _P の後悔値はrG,s,t(P, w) = min P∈P⟨P , w⟩ −P∈PminG(s,t) ⟨P , w⟩ = min P∈Pℓw(P )− dw(s, t) であ る．選好ベクトル w に対して，経路集合 _P の後悔割合は rrG,s,t(P, w) := r_G,s,t(P,w) min P∈Pℓw(P ) = 1− dw(s,t) min P∈Pℓw(P ) である．ここで， minP∈Pℓw(P ) = 0の時はrrG,s,t(P, w) = 0とする．経路集 合_Pの最大後悔割合はmrrG,s,t(P) := maxw∈Rd +rrG,s,t(P, w) である．論文中，文脈から明らかな箇所では添え字を省略する． これらは，集合_PG(s, t)に関して[4]に沿った定義を行ってい ることに他ならない（ただし，ここでも，経路の集合をRd + 内 のベクトルの集合と同一視している）． 2. 2 素朴なアルゴリズム 本論文で扱う問題は，多基準グラフG，2頂点s, t，正整数 k が与えられた時，mrrG,s,t(P)を最小化するようなsからt への経路集合PであってP <_{= k}となるようなものを求める ことである．以下のような既存のアルゴリズムの単純な組合せ により素朴なアルゴリズムが実現できる．このアルゴリズムを Naiveと呼ぶことにする． まず，経路集合_PG(s, t)のスカイラインを求める．ここでは， 既存の多基準グラフにおける経路スカイラインの計算アルゴリ ズムを用いることができる [3,6]．次に，得られたスカイライ ンの経路集合に対して，既存の最大後悔割合最小化のアルゴリ ズムを適用する．最大後悔割合最小化は計算困難問題であるた め，現実的な時間で最適解を求めるアルゴリズムは知られてい ない．しかし，Ramer-Douglas-Peuckerの枠組みに基づく貪 欲アルゴリズムであるGreedy [4]やその高速版GeoGreedy [5] が非常に良い解を与えることが知られている．

3.

提 案 手 法

多基準グラフ上の2点に対し最大後悔割合を最小化する経路 集合を求めるための，より高速なアルゴリズムを設計する．ま ず，陽なスカイライン列挙を行わずに貪欲アルゴリズムを実現 する方法を説明する（3. 1章）．次に，最短経路探索の工夫な どによりさらなる高速化を実現する（3. 2章）． 3. 1 オラクルモデルにおける最大後悔割合最小化 2. 2章で扱った素朴なアルゴリズムの致命的な点は，経路ス カイラインを一度全て陽に列挙する必要がある点である．経路 スカイラインの数は頂点対が離れるにつれ指数的に増加するた め，この処理を含んだままでは，高速な計算を実現することは 難しい．そこで，まず最も抜本的な改善として，経路スカイラ インの陽な列挙無しで，同様の貪欲アルゴリズムを実現する方 法を提案する．この点に集中した議論を行うため，問題を抽象 化したオラクルモデルを導入し議論を行う． オラクルモデルにおける最大後悔割合最小化においては，点 集合P ⊂ Rd + は隠されており，問合せによるアクセスを提供 するオラクルOP :Rd+→ P のみが与えられる．オラクルOP は，与えられたベクトルw∈ Rd+に対し，⟨w, p⟩を最小化す る点p∈ P を返すものとする．この状況において，最大後悔割 合mrrP(S)を最小化する集合S⊂₌P，S <_{= k}を求めることが 目的である． 3. 1. 1 最大後悔割合最小化の幾何的解釈 最大後悔割合最小化問題に関するPengらの幾何的考察[5] を更に深めることで得られる補題1はアルゴリズムの構成に極 めて重要である． 補題1. S をP の真部分集合とする．下側エンベロープLE(S) のある面に直行するベクトルであってS の最大後悔割合を与え る選好ベクトルが存在する． 3. 1. 2 貪欲アルゴリズム 提案アルゴリズムOracleGreedyは以下のように動作する．S を空集合として開始し，現在のSに対し最大後悔割合を与える 点p∗∈ P を追加することを繰り返す．面 F に対し，wF は その直行単位ベクトルを表すものとする．補題1より，点p∗ は下側エンベロープLE(S) の各面F に対しオラクルにより OP(wF)を問い合わせ，最大の後悔割合を与えたものを選ぶこ とにより得られる．補題1を用いて補題2が，面の個数の上 界を用いて補題3が証明できる． 補題2. 任意のk∈ Z+に対し，アルゴリズムOracleGreedyは アルゴリズムGreedy [4]と同一の集合を返す． 補題3. アルゴリズムOracleGreedyのオラクル_OP への問合 せの回数はO ( min { 2d+k, (k + d)⌊d/2⌋ }) 回である． 3. 2 多基準グラフにおける最大後悔割合最小化 以下，G = (V, E, c)を多基準グラフ，s, t∈ V を始点・終点 とする．多基準グラフにおける最大後悔割合最小化の問題は， 上述のオラクルモデルに帰着することができ，アルゴリズム

OracleGreedyを適用できる．隠されていた点集合はPG(s, t)に 相当する．オラクル_OG,s,tは，選好ベクトルw∈ Rd +を受け取 り，単一基準グラフGwにおけるsからtへの最短経路Pwを Dijkstraのアルゴリズムで計算し，Pwを返す．オラクルの一度 の呼び出しは，Dijkstraのアルゴリズムの一度の実行に相当す るため，計算量はO ( min { 2d+k, (k + d)⌊d/2⌋ } (m + n log n) ) となる． スカイラインの陽な列挙が必要なくなったため，この時点で 既に素朴なアルゴリズムよりは遥かに高速なアルゴリズムが得 られている．しかし，現実の大規模交通グラフを考えた場合， 十分な速度とは言えない．そこで，さらなる高速化を行ったア ルゴリズムBestFirstSearchを提案する． 3. 2. 1 大域的最良優先探索 アルゴリズムOracleGreedyでは，下側エンベロープの全て の面から得られる選好ベクトルについて Dijkstraのアルゴリ ズムを実行していた．一方，アルゴリズムBestFirstSearchは， Dijkstraのアルゴリズムを少しずつ実行することにより，全て の選好ベクトルについて最短経路を求めることなく，最大後悔 割合を与える最短経路のみを発見する． ここで重要となるアイディアは，Dijkstraのアルゴリズムの 実行途中の状態から，その選好ベクトルが与える後悔割合の上 界が求まるということである．現在確定している代表経路集合 がSであり，選好ベクトルwに対する距離dw(s, t)の下界が dw(s, t) >_{= δ}というように分かっている時，後悔割合について， rrG,s,t(S, w) <_{= 1 −} δ minP∈Sdw(P ) ということが言える．従って，算出された上界が最も高い選好 ベクトルに対する最短経路計算を進める，ということを繰り返 すことで，最大後悔割合を与える最短経路が発見できる． 3. 2. 2 線形計画法による枝刈り さらに最短経路の計算を省略するため，より精度の高い後悔 割合の上界を線形計画法を用いて得ることができる．既に確定 している経路の集合S ={Pi}と，各経路を与えた選好ベクト ルwiを用いることで，選好ベクトルwF における後悔割合の 上界を線形計画問題として以下のように定式化できる． minimize ⟨p, wF⟩

subject to ⟨p, wi⟩ >_{= ⟨P}i, wi⟩, i = 1, 2, . . . ,S.

最適解における変数p∈ Rd+の値をp∗とした時，以下の補題 が成立する． 補題 4. dwF(s, t) >= ⟨p ∗_{, wF⟩.} 3. 2. 3 多基準グラフにおけるALT下界と両側A*探索 Dijkstra のアルゴリズムを両側A* 探索にすることにより， 更なる高速化が達成できる．多基準グラフにおける両側A*探 索に関する既存研究は存在しない．両側A*探索を行うために は，2点間の距離の下界を得る必要がある．単一基準グラフに おいて有用な下界であるALT下界[2]を多基準グラフに拡張 することで，多基準グラフにおける両側A*探索が可能となる． また，ここで得られる距離の下界は，大域的最良優先探索で用 いる後悔割合の上界の改善にも繋がる．

4.

評 価 実 験

本実験にはCPUがIntel Xeon 2.67 GHz，メモリが96GB

のLinuxサーバを利用した．全てのアルゴリズムはC++ で 実装され，gcc 4.8.4を用いて最適化オプション-O3の設定で コンパイルされた．2つの多基準グラフを用いた（表1）．共 に，コストは5次元であり，所要時間，ユークリッド距離，高 低差，ユニットコスト，ランダム値である． 表1 データセット． 名前 データ元 _{|V | |E| t}Dijkstra USA TIGER/Line 23,947,347 58,333,344 4.42 s Europe PTV AG 18,010,173 42,188,664 3.15 s 4. 1 最大後悔割合 まず，提案手法のアプローチにより最大後悔割合の小さい代 表的経路集合が求められることを確認する．以下の2つのア プローチと比較する．1つめの Top-k は，所要時間に関して Top-k最短経路を計算するものである．2つめのRandomは， ランダムな選好ベクトルをk本生成し，それらにおける最短経 路を計算するものである．提案手法の貪欲法に基づく最大後悔 割合最小化のアプローチはRegret-minimizing と表記する． 実験結果は図2である．経路の本数k を増やすことにより， Regret-minimizing は確かに最大後悔割合を減少させることに 成功していることが分かる． 0 2 4 6 8 10 12 14 16 Number of paths (k) 10-2 10-1 100

Maximum regret ratio Regret-minimizingTop-K Random (a) USA 0 2 4 6 8 10 12 14 16 Number of paths (k) 10-2 10-1 100

Maximum regret ratio Regret-minimizingTop-K Random (b) Europe 図2 異なる代表的経路集合の最大後悔割合の比較． 4. 2 実 行 時 間 次に，貪欲法の枠組みに基づき最大後悔割合最小化を行うア ルゴリズムの速度の比較を行う．素朴なアルゴリズムNaive， オラクルモデルの導入により導いたOracleGreedy，多基準グラ フにおける最大後悔割合最小化のため更なる高速化を導入した BestFirstSearchを比較する．この3つのアルゴリズムは全て 完全に同一の解を出力する． 実験結果は図3である．Naiveは指数個になり得る経路スカ イラインの列挙を行うため，頂点対が離れるにつれ実行時間が 劇的に増加してしまう．一方OracleGreedyとBestFirstSearch は，頂点対間の距離に対して実行時間の増加が緩やかになっ ている．また，BestFirstSearchはOracleGreedyに対し最大で 1000倍程度高速である．

100 ₁₀1 ₁₀2 Distance [km] 10-3 10-2 10-1 100 101 102 103 Time [s] BestFirst OracleGreedy Naive (a) USA 100 ₁₀1 ₁₀2 Distance [km] 10-3 10-2 10-1 100 101 102 103 Time [s] BestFirst OracleGreedy Naive (b) Europe 図3 異なるアルゴリズムの実行時間の比較． 4. 3 ケーススタディ 実世界の関心地点を用いて代表的経路集合の計算を行ったも のが図4である．左側では経路が地理的に描画され，右側では それらのコストが描画されている．経路とコストは同じ色のも のが対応する．コストの意味のみならず，地理的にも多様性を 持つ代表的経路集合が得られていることが分かる． Time 312947.0 377575.2 442203.4 506831.6 571459.8 636088.0 Distance16938.0 18910.3 20882.6 22854.9 24827.2 26799.5 Height220.0 Unit 354.4 488.8 623.2 757.6 892.0 120.0 136.4 152.8 169.2 185.6 202.0 1 2 3 4 5 6 7 8 (a) ブルックリン美術館からコロンビア大学． Time 859970.0 1116976.0 1373982.0 1630988.0 1887994.0 2145000.0 Distance68837.4 76642.1 84446.8 92251.6 100056.3 107861.0 Height813.0 Unit 1137.8 1462.6 1787.4 2112.2 2437.0 296.0 362.0 428.0 494.0 560.0 626.0 1 2 3 4 5 6 7 8 (b) カリフォルニア大学バークレー校からスタンフォード大学． 図4 ケーススタディ．

5.

お わ り に

本論文では，多基準の交通グラフにおいて代表的な経路集合 を求める問題を，最大後悔割合の考え方に基づき定式化し，高 速かつ高精度なアルゴリズムを提案した．今後の展望としては， 更なるアルゴリズムの高速化に加え，高い一般性を持つオラク ルモデルの最大後悔割合最小化問題の他の問題領域への適用を 探りたい． 謝辞．本研究はJSTさきがけの支援を受けたものである．こ こに記して謝意を表す．また，4. 3章の実験に助力を頂いた中 村謙弘氏に感謝する． 文 献

[1] H. Bast, D. Delling, A. V. Goldberg, M. M¨ uller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. CoRR, abs/1504.05140, 2015.

[2] A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In SODA, pp. 156–165, 2005.

[3] H.-P. Kriegel, M. Renz, and M. Schubert. Route skyline queries: A multi-preference path planning approach. In ICDE, pp. 261–272, 2010.

[4] D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. Xu. Regret-minimizing representative databases. PVLDB, 3(1-2):1114–1124, 2010.

[5] P. Peng and R. C.-W. Wong. Geometry approach for k-regret query. In ICDE, pp. 772–783, 2014.

[6] M. Shekelyan, G. Joss´e, and M. Schubert. Pareto-Prep: Fast computation of path skylines queries. CoRR, abs/1410.0205, 2014.