DEIM Forum 2016 A8-4

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

吉田 悠一†† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2-1-2
E-mail: †{takiba,yyoshida}@nii.ac.jp
あらまし

2 点間を移動する経路を計算することは，交通ネットワークにおける最も重要な処理の 1 つであり，地図アプリケーションやカーナビゲーションシステムなどの重要な応用を持つ．本論文では，距離，所要時間，金額などからなる多次元のコストがついたグラフとして交通ネットワークを定式化し，様々な好みを持つ多数のユーザを満足させるような代表的な経路を計算することを目標とする．この問題を最大後悔割合の考え方に基づき定式化し，高速に代表的な経路を計算するアルゴリズムを提案する．
キーワード

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

1. は じ め に
交通グラフ上で 2 点間を移動する経路を計算することは，交通ネットワークにおける最も重要な処理の 1 つであり，地図アプリケーション，カーナビゲーションシステム，配送計画，交通シミュレーションなど様々な応用を持つ．これまでの多くの研究では，交通グラフは単一基準の重みつきグラフとみなされ，単一基準のグラフにおける最短経路の計算の高速化が取り組ま(a) Top-k 最短経路 (b) 経路スカイライン(228 個)れてきた [1]．
本論文では，交通ネットワークのより現実的なモデルとして，(c) 最大後悔割合最小化(本研究)

図 1 異なるアプローチによる代表的経路集合の比較 (k = 4).

距離，所要時間，金額などからなる多次元のコストがついた多基準グラフを採用する．このモデルでは，各ユーザが異なる選ルゴリズムを用いても，計算に非常に時間がかかる．

好ベクトルを持ち，ユーザにとっての経路のコストは，選好ベ

そこで，本論文では，代表的な経路集合の計算を，最大後悔クトルとコストベクトルの内積として定義される（詳しい定義

割合の最小化問題として定式化する．最大後悔割合は，多次元は 2. 章を参照）．本論文の目標は，このモデルの下で，多基準の大規模点集合データから代表的な点集合を選択するために提グラフと始点・終点が与えられた時，ユーザを出来るだけ満足案された考え方である [4]．本論文では，最大後悔割合は，経させるような代表的な経路集合を提示することである．

路の集合に対し定義され，任意の選好ベクトルを持つ人を仮定

一つのアプローチは，ユーザの選好ベクトルを入手し，それした時に，コストの意味でどの程度損をするか，という割合のに基づき問題を単一基準グラフへ帰着することである．しかし，最大値に相当する（詳しい定義は 2. 章を参照）．これが小さい

ユーザの選好ベクトルを入力させることは大きな手間となる上，ほど多くの人を満足させることのできる良い代表的経路集合で実際にはユーザ自身も自分の選好ベクトルを正確に表現するこあると考える．とが困難である場合も多い．また，ユーザの選好ベクトルを自本論文では，始点と終点，及び整数 k が与えられた時，最大動的に推定することも考えられるが，そのためにはそのユーザ後悔割合が小さいような k 本の経路の集合を計算するアルゴリに関する十分量のデータの蓄積が必要になる．さらに，単一基ズムを提案する．このアプローチで計算された経路集合の例は準グラフで複数の経路を提示するための標準的なアプローチで

図 1c である．このアプローチでは，事前にユーザの選好ベクある top-k 最短経路は，実グラフでは，図 1a のように，ごくトルを入手する必要がない．一方，出力は k 本の経路であり，一部のみが異なり，残りのほとんどの部分が重なってしまうよ

スカイラインのように出力される経路が多すぎることもない．

うな出力となることが多い．

また，top-k 最短経路のように経路が似すぎることも無い．そ別のアプローチとして，パレート最適なコストを持つ経路である経路スカイラインを全て求める研究も行われてきている [3, 6]．このアプローチであれば，ユーザの選好ベクトルを事前に入手する必要は無い．しかし，経路スカイラインの数は，して，提案するアルゴリズムは経路スカイラインを列挙するアルゴリズムよりも遥かに高速であり，実用的である．

2. 事 前 準 備

グラフのサイズに対し指数的に増加し，莫大な数となってしま

非負の実数及び整数を R+ , Z+ と表す．整数 n >= 0 に対し，う．例えば図 1b でも，これだけ近い頂点対に対して 228 本の[n] は集合 {1, 2, . . . , n} を表す. ベクトルは x や y のように経路スカイラインが出力されてしまっている．また，最新のア太字で表記する．2 つのベクトル x, y ∈ Rd に対し，⟨x, y⟩ は内積を表す．単一基準（重みつき）グラフは，V を頂点集合，E を辺集合，c : E → R+ を重み関数として，G = (V, E, c) と3. 提 案 手 法

して定義される．G 内の経路 P について，ℓG (P ) を P の経∑路長として e∈P c(e) と定義する．2 頂点 s, t ∈ V について，集合を求めるための，より高速なアルゴリズムを設計する．まPG (s, t) を s から t への全ての経路の集合とする．s, t 間の Gず，陽なスカイライン列挙を行わずに貪欲アルゴリズムを実現

内での距離 dG (s, t) は minP ∈PG (s,t) ℓG (P ) として定義される．

する方法を説明する（3. 1 章）．次に，最短経路探索の工夫な多基準グラフは Vを頂点集合，E を辺集合，c : E → Rd+ を多基準グラフ上の 2 点に対し最大後悔割合を最小化する経路

どによりさらなる高速化を実現する（3. 2 章）．

重み関数として，G = (V, E, c) として定義される．d をグラフ

3. 1 オラクルモデルにおける最大後悔割合最小化の次元と呼ぶ．d 次元の多基準グラフ G = (V, E, c) と選好ベ

2. 2 章で扱った素朴なアルゴリズムの致命的な点は，経路ス

クトル 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) と∑dP (i) =e∈P c(e)(i) として定義されるベクトル P ∈ R+集合 P ⊂ Rd+ は隠されており，問合せによるアクセスを提供をしばしば同一視する．選好ベクトル w ∈ Rd+ に対するするオラクル OP : Rd+ → P のみが与えられる．オラクル OP

経路 P のコストは ⟨P , w⟩ として定義される．後悔値，後は，与えられたベクトル w ∈ Rd+ に対し，⟨w, p⟩ を最小化す

悔割合，最大後悔割合は以下のように定義する．選好ベクる点 p ∈ P を返すものとする．この状況において，最大後悔割

トル w に対して，経路集合 P の後悔値は rG,s,t (P, w) =<合 mrrP (S) を最小化する集合 S ⊂=P ， S = k を求めることが目的である．

min ⟨P , w⟩ −P ∈PminP ∈PG (s,t)⟨P , w⟩ = min ℓw (P ) − dw (s, t) であP ∈P

オラクルモデルにおける最大後悔割合最小化においては，点る．選好ベクトル w に対して，経路集合 P の後悔割合は

3. 1. 1 最大後悔割合最小化の幾何的解釈

rG,s,t (P,w)
dw (s,t)rrG,s,t (P, w) := min= 1 − minである．ここで，ℓw (P )ℓw (P )

最大後悔割合最小化問題に関する Peng らの幾何的考察 [5]P ∈PP ∈P

minP ∈P ℓw (P ) = 0 の時は rrG,s,t (P, w) = 0 とする．経路集合 P の最大後悔割合は mrrG,s,t (P) := maxw∈Rd rrG,s,t (P, w)

を更に深めることで得られる補題 1 はアルゴリズムの構成に極めて重要である．

+である．論文中，文脈から明らかな箇所では添え字を省略する．

補題 1. S を P の真部分集合とする．下側エンベロープ LE(S)

これらは，集合 PG (s, t) に関して [4] に沿った定義を行っていのある面に直行するベクトルであって S の最大後悔割合を与えることに他ならない（ただし，ここでも，経路の集合を Rd+ 内る選好ベクトルが存在する．のベクトルの集合と同一視している）．

2. 2 素朴なアルゴリズム
本論文で扱う問題は，多基準グラフ G，2 頂点 s, t，正整数k が与えられた時，mrrG,s,t (P) を最小化するような s から tへの経路集合 P であって P <= k となるようなものを求める

3. 1. 2 貪欲アルゴリズム
提案アルゴリズム OracleGreedy は以下のように動作する．Sを空集合として開始し，現在の S に対し最大後悔割合を与える
点 p∗ ∈ P を追加することを繰り返す．面 F に対し，wF はことである．以下のような既存のアルゴリズムの単純な組合せその直行単位ベクトルを表すものとする．補題 1 より，点 p∗

により素朴なアルゴリズムが実現できる．このアルゴリズムをは下側エンベロープ LE(S) の各面 F に対しオラクルによりNaive と呼ぶことにする．

OP (wF ) を問い合わせ，最大の後悔割合を与えたものを選ぶこ

まず，経路集合 PG (s, t) のスカイラインを求める．ここでは，既存の多基準グラフにおける経路スカイラインの計算アルゴリとにより得られる．補題 1 を用いて補題 2 が，面の個数の上界を用いて補題 3 が証明できる．

ズムを用いることができる [3, 6]．次に，得られたスカイライ

補題 2. 任意の k ∈ Z+ に対し，アルゴリズム OracleGreedy はンの経路集合に対して，既存の最大後悔割合最小化のアルゴリ

アルゴリズム Greedy [4] と同一の集合を返す．

ズムを適用する．最大後悔割合最小化は計算困難問題であるため，現実的な時間で最適解を求めるアルゴリズムは知られていない．しかし，Ramer-Douglas-Peucker の枠組みに基づく貪欲アルゴリズムである Greedy [4] やその高速版 GeoGreedy [5]が非常に良い解を与えることが知られている．

補題 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 を返す．オラクルの一度

4. 評 価 実 験
本実験には CPU が Intel Xeon 2.67 GHz，メモリが 96GBの呼び出しは，Dijkstra のアルゴリズムの一度の実行に相当す})({るため，計算量は O min 2d+k , (k + d)⌊d/2⌋ (m + n log n)の Linux サーバを利用した．全てのアルゴリズムは C++ でとなる．

実装され，gcc 4.8.4 を用いて最適化オプション -O3 の設定でスカイラインの陽な列挙が必要なくなったため，この時点でコンパイルされた．2 つの多基準グラフを用いた（表 1）．共既に素朴なアルゴリズムよりは遥かに高速なアルゴリズムが得に，コストは 5 次元であり，所要時間，ユークリッド距離，高られている．しかし，現実の大規模交通グラフを考えた場合，低差，ユニットコスト，ランダム値である．

十分な速度とは言えない．そこで，さらなる高速化を行ったア

表 1 データセット．

ルゴリズム BestFirstSearch を提案する．

|V |

データ元

USATIGER/Line 23,947,347 58,333,344

3. 2. 1 大域的最良優先探索
アルゴリズム OracleGreedy では，下側エンベロープの全てEurope PTV AGの面から得られる選好ベクトルについて Dijkstra のアルゴリズムを実行していた．一方，アルゴリズム BestFirstSearch は，Dijkstra のアルゴリズムを少しずつ実行することにより，全ての選好ベクトルについて最短経路を求めることなく，最大後悔割合を与える最短経路のみを発見する．
ここで重要となるアイディアは，Dijkstra のアルゴリズムの実行途中の状態から，その選好ベクトルが与える後悔割合の上界が求まるということである．現在確定している代表経路集合が S であり，選好ベクトル w に対する距離 dw (s, t) の下界がdw (s, t) >= δ というように分かっている時，後悔割合について，rrG,s,t (S, w) <=1−

δminP ∈S dw (P )|E| tDijkstra

名前

4.42 s

18,010,173 42,188,664

3.15 s4. 1 最大後悔割合
まず，提案手法のアプローチにより最大後悔割合の小さい代表的経路集合が求められることを確認する．以下の 2 つのアプローチと比較する．1 つめの Top-k は，所要時間に関してTop-k 最短経路を計算するものである．2 つめの Random は，ランダムな選好ベクトルを k 本生成し，それらにおける最短経路を計算するものである．提案手法の貪欲法に基づく最大後悔割合最小化のアプローチは Regret-minimizing と表記する．
実験結果は図 2 である．経路の本数 k を増やすことにより，Regret-minimizing は確かに最大後悔割合を減少させることに成功していることが分かる．ということが言える．従って，算出された上界が最も高い選好ベクトルに対する最短経路計算を進める，ということを繰り返

さらに最短経路の計算を省略するため，より精度の高い後悔割合の上界を線形計画法を用いて得ることができる．既に確定している経路の集合 S = {Pi } と，各経路を与えた選好ベクト
ル wi を用いることで，選好ベクトル wF における後悔割合の10010-110-2Regret-minimizing
Top-K
Random02

上界を線形計画問題として以下のように定式化できる．

⟨p, wF ⟩subject to⟨p, wi ⟩ >= ⟨Pi , wi ⟩,i = 1, 2, . . . , S .

4681012

Number of paths (k)14(a) USA

図2minimize

Maximum regret ratio

3. 2. 2 線形計画法による枝刈り

100

Maximum regret ratio

すことで，最大後悔割合を与える最短経路が発見できる．

1610-110-2Regret-minimizing
Top-K
Random024681012

Number of paths (k)1416(b) Europe

異なる代表的経路集合の最大後悔割合の比較．

4. 2 実 行 時 間
次に，貪欲法の枠組みに基づき最大後悔割合最小化を行うア

最適解における変数 p ∈ Rd+ の値を p∗ とした時，以下の補題ルゴリズムの速度の比較を行う．素朴なアルゴリズム Naive，が成立する．

オラクルモデルの導入により導いた OracleGreedy，多基準グラ∗
補題 4. dwF (s, t) >= ⟨p , wF ⟩.

3. 2. 3 多基準グラフにおける ALT 下界と両側 A* 探索

フにおける最大後悔割合最小化のため更なる高速化を導入した

BestFirstSearch を比較する．この 3 つのアルゴリズムは全て完全に同一の解を出力する．

Dijkstra のアルゴリズムを両側 A* 探索にすることにより，実験結果は図 3 である．Naive は指数個になり得る経路スカ更なる高速化が達成できる．多基準グラフにおける両側 A* 探

イラインの列挙を行うため，頂点対が離れるにつれ実行時間が索に関する既存研究は存在しない．両側 A* 探索を行うために劇的に増加してしまう．一方 OracleGreedy と BestFirstSearch

は，2 点間の距離の下界を得る必要がある．単一基準グラフには，頂点対間の距離に対して実行時間の増加が緩やかになっおいて有用な下界である ALT 下界 [2] を多基準グラフに拡張ている．また，BestFirstSearch は OracleGreedy に対し最大ですることで，多基準グラフにおける両側 A* 探索が可能となる．

1000 倍程度高速である．

103102102101

101

Time [s]Time [s]文10310010-1
BestFirst
OracleGreedy
Naive

10-2
10-3

101

100

Distance [km]10010-1
BestFirst
OracleGreedy
Naive

10-2
10-3

102

101

100(a) USA

図3102

Distance [km](b) Europe

異なるアルゴリズムの実行時間の比較．

4. 3 ケーススタディ
実世界の関心地点を用いて代表的経路集合の計算を行ったものが図 4 である．左側では経路が地理的に描画され，右側ではそれらのコストが描画されている．経路とコストは同じ色のものが対応する．コストの意味のみならず，地理的にも多様性を持つ代表的経路集合が得られていることが分かる．
1
2636088.03426799.5

56

78

892.0

202.0

571459.8

24827.2

757.6

185.6

506831.622854.9

623.2

169.2

442203.4

20882.6

488.8

152.8

377575.2

18910.3

354.4

136.4

312947.0

16938.0

220.0

Unit

Time

Distance

120.0

Height(a) ブルックリン美術館からコロンビア大学．
1
2

3
4

5
6

7
8

2145000.0

107861.0

2437.0626.01887994.0

100056.3

2112.2560.0

1630988.0

92251.6

1787.4494.0

1373982.0

84446.8

1462.6428.01116976.0

76642.1

1137.8362.0859970.068837.4813.0

UnitTime

Distance

Height296.0(b) カリフォルニア大学バークレー校からスタンフォード大学．

図4ケーススタディ．

5. お わ り に
本論文では，多基準の交通グラフにおいて代表的な経路集合を求める問題を，最大後悔割合の考え方に基づき定式化し，高速かつ高精度なアルゴリズムを提案した．今後の展望としては，更なるアルゴリズムの高速化に加え，高い一般性を持つオラク
ルモデルの最大後悔割合最小化問題の他の問題領域への適用を探りたい．

謝辞．本研究は JST さきがけの支援を受けたものである．ここに記して謝意を表す．また，4. 3 章の実験に助力を頂いた中村謙弘氏に感謝する．

献[1] H. Bast, D. Delling, A. V. Goldberg, M. MüllerHannemann, 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. InICDE, pp. 261–272, 2010.
[4] D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, and J. Xu.
Regret-minimizing representative databases. PVLDB, 3(12):1114–1124, 2010.
[5] P. Peng and R. C.-W. Wong. Geometry approach for kregret query. In ICDE, pp. 772–783, 2014.
[6] M. Shekelyan, G. Jossé, and M. Schubert.
ParetoPrep: Fast computation of path skylines queries. CoRR,
abs/1410.0205, 2014.