一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

1. はじめに

道路網距離での旅行計画の為のインクリメンタル検索方式
インクリメンタル検索方式

車や人などの移動体が現在地から最終目的地に達する
途中で，あらかじめ指定されたいくつかの種類のPOIを訪れる際の最適経路を求める検索は，旅行計画と呼ばれている．例えば，現在地から最終目的地に至る途中で，ガソリンスタンド，レストラン，ショッピングセンター（これらをPOI種と呼ぶ)を訪れる際の最適経路を求める検索である．この際に，POI種の訪問順序が一意に指定されている場合と，訪問順序にはこだわらず全てのPOIを訪れればよい場合とで計算の困難さが異なる．
前者はShrarifzadehら[1]により提案され，OSR (optimal sequenced route)検索と名付けられている．また，
後 者 は Li ら [2]に よ り 提 案 さ れ ， TPQ(trip planningquery)と名付けられている．更に，両者の中間の検索，
即ち，部分的な訪問順序の規則が与えられる検索はChen
ら [3]によ り提 案され MRPSR (multi-rule partial sequenced route)検索と名付けられている．MSPRSとは，例
えば，上記の例でレストランは最後に訪れられなければならないというような，訪問順序の部分的な規則が与えられる検索である．本稿では，これらの全ての検索を旅行計画問題という名で総称する．
上述のように，これらの旅行計画の計算困難さは，途中に訪れるPOI種の順序の指定の厳しさに依存する．いま，
C1からCmまでのm種類のPOI種を，添え字の順序で訪れる検索を考える．また，各POI種にはそれぞれNi (1 ≤ i ≤ m)

An Incremental Query Algorithm for
Trip Planning Queries in Road Network
Distance

大沢 裕♥
曽根原 登♠トウ トウ♦
坂内 正夫♠

Yutaka OHSAWA Htoo HTOO
Noboru SONEHARA Masao SAKAUCHI

現在地から最終目的地に至る途中でいくつかの種類のPOI を１つずつ訪れる際のコスト最小の経路を求める検索は，旅行計画と呼ばれている．この旅行計画は訪れる POI の種類が増えると，また訪れる順番の自由度が増えると最適解を得る計算は困難になるため，従来近似解法が提案されてきた．また，従来の研究はユークリッド距離での巡回路長が最小の解を求めることにとどまっていた．本稿では，道路網上を移動する際の最適解を得る為に，まずユークリッド距離での候補を探し，それを道路網距離で検証するアプローチをでの候補を探し，それを道路網距離で検証するアプローチを採用する．この枠組みでは，ユークリッド距離での候補を最適なものから順番に任意個求める必要がある．本稿ではこの際に必要になる，ユークリッド距離でのインクリメンタルな検索アルゴリズムを提案する．

個のPOIが含まれるものとする．現在地をsとし，最終目
的地をdとするとき，まずsから最初のC1を訪れる場合の数はN1ある．この中から1つを決定して，そのPOIから次のC2のPOIを訪れる場合の数はN2個ある．即ち，sからdに至る途中でm種類iのPOIを1つずつ訪れる場合の組み合わm

せ数は，∏i1 Ni となる．これがOSRにおける探索空間であThis paper proposes a fast trip planning query
method in road network distance. In advance of thequery, the current position, the final destination, andsome number of POI categories visiting during thetrip are specified. Then the query searches theshortest route from the current position, visiting one
from each specified POI categories before reaching
the final destination. Though, several such kinds oftrip planning methods have been proposed, most ofthem only give suboptimal solutions or the solutions
in Euclidean distance. This paper proposes anincremental algorithm for trip planning query, which
can be apply to incremental Euclidean restriction
approachapproach to obtain optimal trip planning routes inroad network distance.

る．
一方，TPQでは，各POI種の訪問順序が指定されないため，各Ciを任意の順序で訪問することができる．従って，m!の訪 問順 序が 存在 する こと にな り， 場合 の数 が，mm! ∏i1 Ni に増えることから，更に計算困難さが増す．

MRPSRは上記2つの検索の中間的なものであり，部分的に指定されるルールが厳しければOSRのコストに近づき，それが緩ければTPQのコストに近づく．旅行計画はこのよ
うな計算困難さを有するため，従来準最適解を求める方式が多く提案されてきた．しかし，一般のLBSでの応用ではmの値は大きくない(例えば高々10程度)と仮定できる．
本稿では，旅行計画を道路網上に移動が制約されている状況で最適解をIER(incremental Euclidean restriction)[4]の枠組みで求める方式を検討する．これは，ユークリッド距離での検索で候補を探し，それを道路網距離で検証する枠組みである．道路網上での距離による旅行計画路をIERの枠組みで求めるためには，ユークリッド
距離での旅行計画路をインクリメンタルに生成できる必要がある．しかし，そのようなアルゴリズムに対する従来の提案は極わずかであり，またそれらの方式の実行性能も高くない．本稿では実験により，提案方式が従来方式に比して解決できる問題のサイズと実行時間の点で優れることを示す．
以下，２．で提案方式を述べる．３．では性能比較実♥

正会員 埼玉大学大学院理工学研究科
ohsawa@mail.saitama-u.ac.jp♦
非会員 埼玉大学大学院理工学研究科博士後期課程
htoohtoo2@gmail.com♠
非会員 国立情報学研究所{sonehara, sakauchi}@nii.ac.jp

1―1―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012
る．また， d3の場合には， sから発せられた光がMBRのある辺で反射してdに到達する場合の距離，即ち辺上の点Aを通過する距離となる．

験を行った結果を提示する．最後に，４．で本稿をまとめる．

2. ユークリッド距離上でのインクリメンタル探索2.1

IER の枠組みでの旅行計画探索

IERの枠組みでは，ユークリッド距離で候補経路を生成し，その結果を道路網上の距離で検証する．いま，ユー
クリッド距離での検索で距離最短の順序訪問経路(SR:sequenced route)が１つ見つかったものとし，そのSRの道路網上での最短路の長さをLminとする．このとき，更にユークリッド距離でLmin以下のSRを全て求めれば，道路網上での距離で最短のSRは必ずその中に含まれる．なぜなら，2点a,b 間のユークリッド距離をdE (a, b)，また
道路網上の距離をdN (a, b)と表わすとき，常にｄE (a, b) ≤図 1 STP 経路の下限距離
Fig.1 Lower Bound Distance of STP PathdN (a, b)の関係が成り立つためである．逆に言えば，IERの枠組みでの旅行計画では，ある距離の上限値Lminが指定され，それ以下のユークリッド距離のSR を全て求める検索が必要となる．この性質を満たすのが，距離が短い
ものから順に探索を行えるインクリメンタル検索である．
従来旅行計画の為に提案されている多数の方式の内，筆者らの知る限りでは，Sharifzadedら[1]のPNE及びLiら[2]のMDQがインクリメンタル検索可能な方式である．
両方式共，基本的なアルゴリズムは同じであり，旅行開始点sから次第に検索範囲を拡大しつつPOIを探索する．
Sharifzadeh[1]は，PNEの他に，ユークリッド距離でのOSRを求めるアルゴリズムLOADを提案している．また，この効率化方式として，R木を用いるR-LOADを提案している．
しかしこのR-LOADは深さ優先に基づく探索方式であり，
本稿で目的とするインクリメンタルな探索には適していない．そこで本稿では，R木を用いた最適優先探索によりOSR候補をインクリメンタルに生成可能なアルゴリズムを提案する．このアルゴリズムを単純に発展させることにより，MRPSRやTPQにも適用可能である．

距離を求める対象のMBRをMとし，その4頂点をc1～c4とする．このとき，上述の3種類の場合の距離の下限値は，以下のように決定できる．
Case1: s,dを結ぶ線分とMが交わる場合．寄り道路の距
sd

離の下限値はその線分の長さ，即ちLE (M)  dE s, dである．これは図 1のd1の場合に相当する．
Case2: s,dを結ぶ線分がX軸に平行な辺の延長線，及びY軸に平行な辺の延長線に共に交わる場合．寄り道路の距
離の下限値はsからMBRのある頂点ciを経由しdに至るパスの長さの最小値，即ち，
sd

LE M  min dE s, ci   dE ci , d : i  1, ⋯ ,4である．これは図1のd2の場合に対応する
Case3: それ以外の場合． sとdは，図2に示すように，
MBRのある辺(b)に対して，共に同じ側に存在している．
まず，辺bを含む直線に対して dと対称な点d'とsを結ぶ
線分と辺b との交点Aを求める．もしAが辺bの範囲の外側であれば，Case2と同様に最小距離を求める．一方， Aがbの範囲に含まれれば2.2 ユークリッド距離でのユークリッド距離での STP 探索
POI集合はR木[6]で管理されているものとする．旅行計
画における出発地をs，最終目的地をdとするとき，ユー
クリッド距離でのSR はR木中のMBRを参照しつつ，最短の経路長が得られる可能性のあるノードをたどることにより得られる．以下では，まず途中で訪れるPOIのカテゴリ
ー数が１の場合[7](STP: simple trip planning)について述べ，次にそれを複数カテゴリーをたどるOSRに拡張す
る．図1は，s,dの組に対して位置関係が特徴的な3種類の目的地d1～d3，及びR木中のあるMBR(M)の位置関係を示している． d1のように，2点を結ぶ線分がMBR(M)の内部を通過するとき，このM 中に存在するPOIを訪れる経路長の下限値は，この線分長自身となる．以下では，この下限

sd′

LE (M)  dE (s, A)  dE (A, d) ( dE s, d )

とする．

d

d’

A

M

b

sd

値をLE (M)と表わす．実際には，POIがこのMBRのどこにあるかは不明であるが， sとdを結ぶ線分の上にPOIが存在する可能性があり，SRの経路長の下限値は上記の値となる．
d2とd3 は線分がMBRを通過しない場合である．まず， d2の場合には，寄り道路の距離の下限値は， sとd2を結ぶ線分から最も近いMBRの頂点を通過する場合の距離となs
図 2 Case 2 の場合
Fig.2 Case 2
以上で述べた処理により得られる， sからR木のある

2―2―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012
様の処理を繰り返すことによりインクリメンタル検索が行える．ユークリッド距離で距離最短の寄り道路を与える経路をk 個求めるアルゴリズムをAlgorithm 1に示す．
このアルゴリズムではユークリッド距離でのSR経路長が短いものから順に求まる．1行目のnは求まった経路の数を計数する変数である．またRstは，途中に通過するPOIの結果集合である．2行目では， s, d間のユークリッド
距離dE (s, d)とR木の根ノード(root)からなるレコードを

sd

MBR，Mを経由してdに至る経路の距離LE (M)と，R木の葉
ノ ー ド に 置 か れ る POI(p)を 経 由 す る 実 際 の SRの 距 離
sdsd

LE (p)を総称して，以下ではLE (e)と表わすことにする．
即ち，この関数はeがMBRのときにはsからMBR中のPOIを経
由してdに至る経路長の下限値を表わし， eがPOIの場合にはユークリッド距離での実際のSRの距離を表わす．SR
の探索はヒープ(PQ)を用いた最適優先探索で行う．ここで， PQは次の(1)式のレコードを管理するものとする．
sd〈LE (e), e 〉PQに入れている．3行目から12行目までのループを優先順
位付きキューPQが空になるか，または指定された個数(k)のPOIが求まるまで繰り返す．

(1)

sd

4行目では， LE (e)の値が最小のレコードrをPQから取り出している．5行目から8行目では， rがMBRの場合，その全ての子(ノード，又はPOI)についてPQのレコードを作成し，それをPQに投入している．9行目と10行目は， r.eがPOIの場合の処理であり，そのときはr.eを結果集合Rstに加え， nの値をインクリメントしている．
このアルゴリズムでは，対象のPOIを１つ経由するSRの距離が短いものからk個求めているが， PQの内容を保存しておき，3行目以降を繰り返すことによりインクリメ
ンタルな候補の探索が行える．
Algorithm 1 (ESTP)
1 n ← 0, Rst ← ∅2 PQ. enqueue(  (s, d), root )
3 while PQ. size()  0 and n   do
4r ← PQ. deleteMin()5
if r.e instance of MBR then6
for all ch ∈ e. c do
7
PQ. enqueue(〈L (ch), ch〉)8
end for9else
10
Rst ← Rst ∪ r. e, n ← n  1
11
end if
12 end while
13 return Rst

図 3 R 木上での SR 路検索
Fig.3 SR Path Search on R-tree
図3は，sからdに至る途中で1種類のカテゴリー中のPOIを１つ訪れる経路を求める場合を示している．図3(a)は簡単なR 木を示している．また，図3(b)と(c)で点線は，MBRまたはPOIを経由する経路と，その経路の距離（数値）を示している．図3(b)に示すように，R 木の根ノードに置 か れ て い る 3つ の MBR(M1～ M3)と の 経 路 長 の 下 限 値

2.3
2.3 複数カテゴリーへの拡張
前節で述べたESTPを対象POI種を変えながら繰り返し
適用することにより，OSR の探索が行える．ここで， sからdへ移動する途中でm種類のPOI(Ci 1 ≤ i ≤ m)を順

sd(LE (M)，但しMはM1～M3)を求め，それぞれに対してPQのにたどるものとする．図4に示すように，ESTPを適用してまずC1カテゴリーのPOIをたどる経路を探索する．その結果Ci中のPOI， p1が得られたものとする．次に， p1とdを両端点としてC2カテゴリーに属すPOIを検索の対象としてESTPを適用する．一般に， CiカテゴリーのPOI， piが求まったとき， piからCi+1カテゴリーのPOIを対象として処理を繰り返す．そして，最後のカテゴリーCmに属すPOI，
pmのレコードがPQから取り出されたとき，OSR経路が1つ確定したことになる．
探索の全体は，１つのPQで制御される．そのPQはsからdに至る途中で現在見つかっているPOIを経由し，次に探索を行うカテゴリーを管理するR木のMBR を経由する距
離の下限値の和で昇順にレコードを管理する．図4の例でこの距離の値は，レコードを作成し，それらをPQに投入する．この時点でのPQの内容は，次のようになる．
<25,M2>, <42,M3>, <45,M1>
次に，PQからコスト最小の要素を取り出す．その結果，<25,M2>が得られる．そこで，R木のM2の子ノードをたどる．この場合に， M2の子ノードは葉ノードであり，点C,D,Eが置かれている．そこで，図3(c)に示すように，それら3つの点に対してPQのレコードを作成してPQに投入する．その結果，PQ の内容は次の様に変わる．
<32,C>,<38,D>,<41,E>,<42,M3>,<45,M1>
ここで，PQからコスト最小の要素を取り出すと<32,C>が得られる． CはPOIであるため，この時点でSRが１つ得られたことになる．このSRの経路長は最短であることが保証される．また，PQから次のPOIが取り出されるまで同

3―3―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012p1に基づくOSR探索で必要となる，経路長がLmin以下の経路を全て求める検索も，次々に求まる確定経路の長さがLmin以下の内，検索を続けることにより得られる．
ユークリッド距離に基ずくOSR探索のアルゴリズムを
疑似コードで表現したものを，Algorithm 2に示す．
EOSRアルゴリズムは以下の修正を行うことによりTPQに適用できる．1行目では， C1のR木の根ノードに対するレコードのみをPQに投入しているが，TPQでは全てのカテ
ゴリーの根ノードに対するレコードを作成してPQに入れる．また，7行目から11行目の処理では，次のカテゴリーのR木の根ノードに対するレコードを作成してPQに入れているが，TPQではまだ訪れていない全てのカテゴリーのR木の根ノードに対してレコードを作成してPQに投入する．従って，TPQでは特にmの値が大きい場合，OSRに比してPQ中のレコード数が急速に増大する．
MRPSRでは，1行目で最初に訪れることができる全てのカテゴリーのR木の根ノードのレコードを投入すると共に，7行目から11行目では，現在求まったPOIのカテゴリ
ーの次に訪れることが可能なPOIカテゴリーについてレ
コードを作成し，PQに投入する．

ds

M (C2)

図 4 EOSR による OSR 探索
Fig.4 OSR Search Using ESTP
1

1

p d

dE s, p   LE r

(2)となる．PQ中には，探索の対象とするPOIカテゴリーが異なるものが混在することになる．PQが管理するレコードのフォーマットを以下に示す．
<Cost, prev, dfs,i,e,psr>
上式で， prevは直前に発見したPOIであり，初期値はsである． dfsは， sからprevまでのSRの経路長である． iは次に探索するPOIカテゴリーの番号， eはCiを管理する
R木のノード(又は，POI)であり， psrは現在までに求まっている部分SR(PSR)に含まれるPOIの集合である．また，Costは式(2)で得られる距離の下限値である．
PQからは， Costが最小のものが取り出される．そのレ
コードのeがMBRであるとき，そのノードのR木中での全ての子ノードに対して，新たなレコードを作成し，それらをPQに投入する． eがPOIのとき，そのeがi番目にたどる
POI(pi)になる．そこで，探索するPOIカテゴリーを1つ進める．即ち， Ci+1をターゲットとする探索を開始する．
もし， i > mのとき，距離最小の経路が求まったことになる．そこで，現在求まっている経路を返す．

2.4 カテゴリー毎のPOI
カテゴリー毎のPOI密度が大きく異なる場合
POI密度が大きく異なる場合
前節で述べたアルゴリズムにより，POI個数(密度)が均一な場合には良好な結果が得られる．一方，POI密度が低いカテゴリーがシーケンスの最後に置かれる場合，処理時間が急速に増大する傾向がある．EOSRではsとdを焦点とする楕円領域からOSRルートが探索されるが，POI密度が低いカテゴリーが最後に訪れられる場合，その楕円領域が広がる．この楕円領域の拡大により，密度高く分布するPOIの数が増大し，PSRの数も増える為である．
上記の欠点を緩和するためには，OSRで指定された訪問
順序にはこだわらず，密度が低いカテゴリーを先に探索し，順次密度が高いカテゴリーの探索を行えば良い．例
えば最も密度の低いPOIカテゴリーをCiとするとき，そのカテゴリー中のPOI， piが先に決定される．その後，sとpi間，及びpiとd の間で順次密度の高いPOIを対象として探索を行うことにより，探索空間を狭く抑えることができる．

Algorithm 2 (EOSR)
1 PQ. enqueue( d (s,d),s,0,1,T(1).root,{s}>)2 while PQ.size() > 0 do
3r ← PQ. deleteMin()4
if r. i   then5
return r.psr
6
end if7
if r.e instance of POI thenthe8r. psr ← r. psr ∪ r.e
9i ← r. i  1
10d ← r. dfs  d (r. prev, r. e)
11
PQ. enqueue(   d (r. e, d), r. e, d, i,T(i). root, r. psr )
12
else
13
for all ch ∈ e. c do
14
Cost  ch. dfs  L., (ch)15
PQ. enqueue( , ℎ. , ℎ. ,ℎ. , ℎ, ch. psr )
16
end for17
end if18 end while

3. 性能評価
前章までに述べたアルゴリズムをJavaで実装し，性能評価実験を行った．使用した計算機は，Intel Corei7 CPU(3.2GHz)，主記憶容量は9GBである．実験に際して，POI
カテゴリーの数が大きい場合に多量のヒープ領域を使う
ため，ヒープサイズの最大値を１GBに設定した．道路網を用いた実験も行っているが，本稿では紙面の都合でEOSRの性能評価に焦点を当てる．
現在地sと最終目的地dとの距離とPOI密度とは深く関連する． s,d間の距離が長くなれば，POI密度が低くても検索に際して調査対象となるPOI数は増え，一方， s,d間の距離が同じでもPOI 密度が高ければ，同様に調査対象となるPOI数は増加する．そこで，まず図5の矩形領域
内に疑似乱数を用いて1万個のPOIデータセットを多数作成した．データが存在する空間のサイズは縦横100,000とした．sとdは，矩形領域の中心から描いた半径Rの円周上で，互いに対角線となる位置に置いた．対角線の角度は30度毎に変えた12のパターンを用いた．この設定によこのアルゴリズムは，距離最小の経路が求まった後も，PQの内容を保持することにより，OSR経路長が最小のもの
から順に，インクリメンタルに求めることができる．IER

4―4―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012

り，例えばR=2500の場合，円内に平均約20個のPOIが存在することになる．

EOSR(1)
EOSR(50)
EOSR(100)
PNE(1)
PNE(50)
PNE(100)

Visited Node Number

105
4

10

103
2

10

1

10

100

図 5 s とｄの設定
Fig.5 Setting of s and d

3

10

2

10

0.01

Processing Time (s)

0.1

1

10

8

10

0.1

0.01

0

6

10

1

105

4

8

LAH
HAL
DFLAH
DFHAL

10

4

2

6

今までに述べた実験では，各カテゴリー中のPOIの個数
を10,000個で一定とした．次に，カテゴリー毎にPOIの個数が異なる場合の性質を調べるための実験を行った．POI
個数が10,000個のデータセット(H)と1,000個のデータセット(L)を多数生成し，5つのPOIカテゴリーからなるOSRのシーケンス中に１つLの集合が含まれ，他は全てH集合からなるシーケンスでの処理時間を測定した．また，逆に1つのHが他は全てLの中に含まれるシーケンスに対しても処理時間を測定した．この結果を図8に示す．ここで，LAHはH中に1つのL が含まれるパターンを，HALはL中に1つのHが含まれるパターンを表わしている．また横軸は，個数の異なる集合がシーケンス中で表れる位置を示している．この図から，HALでは個数の多いPOIカテゴリーがシーケンス中の後ろに置かれるほど処理時間は短くなる．
逆に，LAHでは個数の少ないカテゴリーがシーケンスの後ろに置かれる程，処理時間は急速に長くなる性質がある．

6

10

0

4

図 7 インクリメンタル検索の性能評価
Fig.7 Performance Comparison on Incremental Search

Visited node number

Processing time (s)EOSR-time
EOSR-node
PNE-time
PNE-node

1

0.001

2

m

図6は途中で訪れるPOIのカテゴリー数(m)を変化させたときの処理時間と展開ノード数をEOSRとPNEについて比較したものである．但しPOIを管理するR木のスロット
数は64(1ノード2KB)とし， R=2500としている．
PNEはmの値が5を超えたとき，ヒープ領域のあふれが生じたため，5以下の値を示している．この図に見られるよ
うに，EOSRは計算可能なmの範囲を2倍に拡大できている．
また，同じm 値で比較したとき，EOSRはPNEに対して計算
時間，参照されたR木のノード数ともに50分の1～100 分の1に効率化している．
本稿では全ての実験でR木の最大スロット数を64に固定しているが，この値を64，32，16，8の間で変化させた
場合， m値が4以上の場合において最大スロット数が16で最短の実行時間が得られた．但し，これらの値の間での差異は高々4倍程度である．
図7は，最短のEOSR，50番目，及び100番目のEOSRをインクリメンタルに求めた場合の処理時間を示している．
m の値が3以上の場合，EOSRをPNEと比較すると10倍から100倍の高速化が実現できている．但し，この図ではR=500とした．理由は，Rの値が大きい時ヒープ領域あふれにより，PNEでは小さなmの値に対してしか計算できない為で
ある．
10

0

10

m

1

2

3
Position

45

図 8 密度の異なる POI の影響
Fig.8 Effect of POI Density

図 6 ユークリッド距離での実験結果
Fig.6 Experimental Result on Euclidean
Distance

一方，2.4節で述べたように，最も密度が低いPOIカテ
ゴリーを先に探索し，順次密度が高いPOIを対象とした経路探索を行うことにより，上で述べた処理時間をPOI密度

5―5―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月

一般論文

DBSJ
Vol.11, No.2.2
Vol.11,.11
No
DBSJ Journal,
Journal,Vol.
11,
No.2
October
October2012
2012に依らず安定させることができる．図8中のDFLAHとDFHAL
は密度が低いPOIカテゴリーから順に探索を行った結果であり，それぞれLAHとHALに対応している．この結果に見られるように，密度が低いカテゴリーから探索をおこなうことにより，安定した処理時間が得られている．
最後に，提案アルゴリズムをTPQに適用した結果を図9に示す．途中に訪れるPOI種の数をmとするとき，TPQはOSRのm!倍探索対象となるルート数が増える．一方，TPQでは
訪問順序を自由に選べるため，OSRに比べて経路長が短くなる．これにより，探索する範囲も減少する．図9には1 カ
テゴリー中のPOI数が1,000個の場合と10,000個の場合を示している．1,000 個の場合ではPOI数が7まで，10,000
個では8の場合まで探索できた．共に，これを超えた場合にはヒープ(上限をIGBに設定)のオーバーフローが発生
している．
10

式はLBSにおける実用的な検索に対応可能であると思わ
れる．

[謝辞]
謝辞]
本 研 究 は 文 部 科 学 省 科 研 費 ， 24500107 及 び
23300337-01 の補助による．

[文献］[1] Sharifzadedh, M., Kalahdouzan, M. and Shahabi,
C.: "The oprimal sequenced route query", Technicalreport, Computer Science Deartment, University ofSouthern California (2005).
[2] Li, F., XCheng, D., Hadjieleftheriou, Kollios, K. andTeng, S. H.: "On trip planning queries in spatial
databases", Proc. SSTD 2005, pp.273-290 (2005).
[3] Chen, H., Ku, W. S., Sun, M. T., and Zimmermann,
R. : "The multi-rule partial sequenced route query",
ACM GIS '08, pp.65-74 (2008).
[4] Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y.:"Query processing in spatial network databases",
Proc. 29th VLDB, pp.790-801, (2003).
[5] Sharifzadeh, M., Kolahdouzan, M. and Shahabi, C.:"The optimal sequenced route query", The VLDB
Journal, 17, pp.765-787 (2008).
[6] Gutttman, A. : "R-tree: A dynamic index structure
for spatial searching", Proc. ACM SIGMOD
Conference on Management of Data, pp.47-57(1984).
[7] トウ, 大沢: "ユークリッド距離での制約をベースとする単純な旅行計画の為の高速アルゴリズム", DEIM
Forum 2012, D-8-1 (2012).

10000
1000

Processing Time (s)

1

0.1

0.01

0.001

2

3

4

5

6

7

8

m

図 9 TPQ 探索時の実行時間
Fig.9 Processing Time of TQP Search

大沢 裕 Yutaka OHSAWA

4. おわりに

埼玉大学大学院理工学研究科教授．1978 信州大学大学
院修士課程修了．工学博士．地理情報システム，時空間
データベースの研究に従事．

本稿では，道路網上の移動を想定した旅行計画をIERの枠組みで実行する方式を提案した．この枠組みでの検索の為には，ユークリッド距離上でのOSRをインクリメン
タルに検索できる必要がある．そのために，R木で管理されているPOIを対象として，OSRを最適優先探索で求める方式を提案した．
OSRをインクリメンタルに求められる唯一の既存アルゴリズムはPNEであるため，それと提案アルゴリズムとの比較実験を行った．PNEは旅行開始点から同心円状に探索
範囲を拡大していく．一方，提案方式は旅行開始点と最終目的地を焦点とする楕円状に探索範囲を拡大する．この探索範囲の大きさの差が実行時間と求められる問題のサイズ(m)に影響する．比較実験では提案アルゴリズムがPNE の約2倍の規模(m値)の問題に対して厳密解が得られることを示した．
更に，OSRシーケンスの先頭から順番に探索を行う場合，
POIカテゴリーの密度の影響を受ける問題が生じることを示した．この対策として，密度が低いPOIカテゴリーから順に探索を行う方式を提案し，それにより，安定した実行時間が得られることを示した．また，提案方式をTPQに適用した場合， m値が7程度以下までの経路を生成できることを示した．LBSで求められる旅行計画では通常m値
はそれほど大きくないと予想できる．従って，本提案方トウ トウ Htoo HTOO

埼玉大学大学院理工学研究科博士後期課程在学中．2004
University of Computer Studies, Yangon, Manmar 修士課程修了．LBS の研究に従事．

曽根原 登 Noboru SONEHARA

国立情報学研究所教授．1978 信州大学大学院修士課程修了．工学博士．情報セキュリティーの研究に従事．電子情報通信学会フェロー．

坂内 正夫 Masao SAKAUCHI

国立情報学研究所所長．1972 東京大学大学院博士課程修了．工学博士．画像データベース，画像処理，マルチ
メディアデータベース，ITS などの研究に従事．電子情報通信学会フェロー．

6―6―

日本データベース学会論文誌 Vol.11
Vol.11,
11, No.2
No.2
日本データベース学会論文誌 2012
Vol.11,
No.2
月2012 年 102012年 10月