DEIM Forum 2016 D2-6

合流による利益を考慮した単一目的地への集合経路最適化
瀧瀬

和樹†

浅野

泰仁††

吉川 正俊††† 京都大学工学部情報学科 〒 606–8501 京都府京都市左京区吉田本町 36-1†† 京都大学情報学研究科 〒 606–8501 京都府京都市左京区吉田本町 36-1
E-mail: †takise@db.soc.i.kyoto-u.ac.jp, ††{asano,yoshikawa}@i.kyoto-u.ac.jp
あらまし

複数のユーザに対し, 全員の移動距離の和が最小になるような集合地点を求める問題は盛んに議論されている. しかし, 現実的な状況においては, 各々が単独で集合地点へ向かうのではなく, 経路の途中で合流しながら集合した方が利益が大きい場合が多い. そこで, 本研究では合流による利益を考慮した, 集合経路の最適化に関する問題を新たに定式化し, 少人数で高速に厳密解を求めるアルゴリズムと多人数にも対応した近似アルゴリズムを提案する. 実
データを用いた実験によって, 提案手法が実用的な速度と精度で動作することを確認した.
キーワード

グラフ, ロードネットワーク, 合流, 経路探索

1. は じ め に
地図上に与えられた複数の地点からの最短距離の総和が最小になるような地点を探索する問題は, [1] [2] [3] などで既に盛んに議論されている. この問題の主要な応用例としては, 異なる地

(a) ロードネット(b) 待ち合わせ場所(c) 本論文が考えるワークの例

問題の最適解例

問題の最適解例

点にいるユーザの待ち合わせ場所の決定や, スーパーマーケッ
ト等の施設の理想的な建設地の決定などが挙げられ, それぞれ

図 1 合流による利益が問題になる待ち合わせの例

待ち合わせ場所問題や施設配置問題と呼ばれる.
しかし, 特に待ち合わせ場所の決定等の応用例を考える場合,

る利益を考慮した単一の目的地への経路の最適化のための新た各ユーザの初期位置からの最短距離の総和の最小化を目指したな問題を定式化する. この定式化では, 新たに利益関数というだけでは不十分な場合がある. 現実的な状況においては, 各々概念を導入し, 合流や集団という概念を扱っている. この関数のユーザは目的地へ独立して移動するだけでなく, 時には合流の値をあらかじめ調節することにより, ユーザ同士の合流に対しながら目的地を目指すことによりより大きな利益を獲得する.

する利益を自由に設定し, 様々な応用例に対して忠実に本問題

例えば, 親密な友人同士が異なる地点から同一の目的地を目を適用することが可能となっている.

指す場合には, 二人もしくはそれ以上の人数でまとまって目的

具体的には, 親密なユーザ同士をできるだけ長い経路で一緒地へ向かう方が有意義だと考えるかもしれない. また, タクシーに移動させたり, 逆に合流させたくないユーザ同士は別々に目のような交通手段を用いて移動する場合, 経路の途中で合流す的地へと移動させることも可能である. また, 少人数でのみ一ることによりタクシーの利用台数を削減し, 移動にかかる費用

緒に移動可能なタクシー等の応用例を想定し, 集団の人数の範の総和を小さくできるかもしれない. しかしこのような応用例

囲を制限することも可能である.

を想定した研究は十分に行われていない.

我々の知る限り, これらの細かな設定まで想定した既存の関図 1(a) から図 1(c) は, 以上のような問題が発生しうるロー

連研究は存在しない. したがって, 本論文は, ユーザ同士の合流

ドネットワークの例である. 図 1(a) のようなロードネットワー

による利益を考慮した単一の目的地への経路の最適化に対して,

クを考える. 各円はロードネットワークの頂点を表し, u1 から本格的な定式化を初めて提案する論文と位置付けることができ

u4 とラベリングされた頂点にユーザがそれぞれ存在するとする.

る. このとき, 一般的な待ち合わせ場所問題において解となる

2 つ目の貢献として, 以上の問題を実用的な速度で解くため頂点は G とラベリングされた頂点であり, 図 1(b) における青の手法を複数提案する. より具体的には, 動的計画法に基づき少色の経路がそれぞれのユーザの最短路となる.

人数で高速に厳密解を求めるアルゴリズムと, ヒューリスティッ

しかし, 頂点 G にユーザが集合するとき, 図 1(c) における赤クを導入し多人数にも対応した近似アルゴリズムを提案する.

色の経路を各ユーザが通ることにより, u1 と u2 , u3 と u4 がそそして最後の貢献として, 実際のロードネットワークを用いれぞれの経路の途中で合流して移動することができる. この場た実験により, これらの提案手法が実用可能な速度と精度で動合, 図 1(b) に比べユーザの移動距離はそれぞれ大きくなってい作することを確認した.

る. しかし, 現実的な状況においては上記の例のように, これらの経路を採用した方が利益が大きくなる状況が多く発生する.
本論文では, まず一つめの貢献として, ユーザ同士の合流によ•

2. 関 連 研 究

それぞれの経路が合流することにより利益が獲得できる.

ただし, Buy at Bulk では経路にフローを流し続けるのに対

2. 1 待ち合わせ場所問題, 施設配置問題

し, 本問題は経路上を実際に人や物が移動するという点が本質

地図上に与えられた複数の地点からの最短距離の総和を最的に異なる.

小化する問題は, [1] [2] [3] などで既に研究が行われている. 特

Buy at Bulk 問題の既存の研究は, 理論的な保証を与える近に [3] は, Waber Problem として比較的長い歴史を持ち, ユーク

似アルゴリズムに関するものが一般的である. 実用的な速度やリッド平面上でこの問題を扱う. Waber Problem は, [4] [5] [6]精度で動作することが確認された手法は, 我々の知る範囲ではなどでさらに詳しい研究がなされている. ロードネットワーク

まだ提案されていない. これらの研究に対し, 本論文ではロー上におけるこの問題は, [1] [2] などで研究が行われている.

ドネットワーク上での待ち合わせという応用例に焦点を当てる.

これらの問題と本論文が扱う問題では, 問題に対する入力とそしてこの応用例に適した定式化を行うことで, 実用的に十分出力が異なることに注意されたい. これらの問題では待ち合わ

な一般性と性能を兼ね備える手法を初めて提案することを, 本

せ場所, もしくは施設の配置場所としての最適な頂点を解とし論文の主要な貢献として挙げたい.

て出力するのに対し, 本論文では, ユーザの初期位置と最終的に集合する頂点が与えられたときに, その経路を決定する問題を

3. 問 題 設 定
3. 1 表記と制約扱う.
本論文のように移動中での合流を考慮したナビゲーションシ

本論文は, 合流による利益を考慮した単一目的地への経路探

ステムの開発に関する研究も [11] 等で既に行われている. しか索に関する問題を扱う. まず, この問題を定義するために必要し既存の研究における定式化や手法は, 最小シュタイナー木問となる基本的な概念や用語を定義し, それらの表記を定める.

題と同様のものをそのまま用いているため, 柔軟性に乏しいといえる. 本論文では, これらの研究よりも一般性の高い形での定式化を行っているため, より幅広い応用例に忠実に適用可能である.

定義 3.1 (グラフ) 本論文では, 無向グラフ G = (V, E) として表されるロードネットワークを扱う. V は頂点集合, E は辺集合を表す. それぞれの辺 e ∈ E は, 正の実数の重み we を持ち,
これは辺 e の両端点間の距離を表す. 2 頂点 s, t ∈ V に対し,

2. 2 最小シュタイナー木問題d(s, t) は頂点 s, t 間の最短距離を表す. 任意の二点間 s, t に対ある無向グラフにおいて, その頂点の部分集合が与えられた際にそれら全てを連結する木の中で辺の重みの総和が最小のもする最短距離に対応するパスのうちのある一つを path(s, t) と表す.

のを求める問題が, 最小シュタイナー木問題であり, 様々なアルゴリズムが既に開発されている. 詳しくは, [7] [9] 等を参照されプログラムの実行中, 任意の二点間 s, t に対する最短距離d(s, t) は, 二次元配列に保存され O(1) 時間で計算できるもの

たい.
本論文が扱う問題は, 最小シュタイナー木問題を一般化したとする. path(s, t) は, O(|V |) 時間で取得できるものとする. 本

位置づけとなっている. 本問題を最小シュタイナー木問題に適

論文における最短距離と最短経路に関する詳細は, 5. 1. 4 節を用する手法は 3. 3 で扱う. [8] より, 最小シュタイナー木が NP

参照されたい.

困難であるため, 本論文が扱う問題も NP 困難となる.

定義 3.2 (クエリ) 本問題の各クエリはユーザの集合 U と, 各

本論文が扱う問題は, 最小シュタイナー木と類似した性質を多く持つ. 本論文において厳密解を求める提案手法は, 最小シュタ
イナー木問題を求める Dreyf us, W agner のアルゴリズム [10]を一般化した位置付けとなっている. ただし, アルゴリズムの中で用いられる変数や計算式の意味が, Dreyf us, W agnerの ア ル ゴ リ ズ ム と 提 案 手 法 で は 大 き く 異 な る.

そ の た め,Dreyf us, W agner のアルゴリズムと提案手法を関連付けて考えるのは容易ではない.

2. 3 Buy at Bulk 問題

ユーザ u の初期位置を表す頂点 su ∈ V , および目的地 vT ∈ Vからなる.
定義 3.3 (経路) 各ユーザ u の初期位置 su からのある頂点へのある経路を R(u) と表し, R = {R(u) | u ∈ U } とする. R(u)の i 番目の辺を e(R(u), i) と表す. また, R(u) の i 番目の頂点
を v(R(u), i) とする. ただし, v(R(u), 0) = su と定める. R(u)に含まれる辺の数を l(R(u)) と表す.
ここで, それぞれのユーザの経路に同一の辺や頂点が複数回入頂点から出頂点へのネットワークの配線を行う際に, 経路

あらわれることがありうることに注意されたい. この状況は既を合流させ配線をまとめて購入し, 要求されるネットワーク容存の関連研究の定式化では発生せず, 本問題に一般性を与え, 難量を満足させつつ配線費用を最小化する問題が, Buy at Bulk

解なものにする一因となっている.

問題である. 詳しくは [12] 等を参照されたい.
この問題には様々な形式の定式化があるが, 特に, [14] [15] 等
で研究されている Single Source Buy at Bulk と呼ばれる問題
は, 本論文が扱う問題と以下のような点で非常に類似している.

•

クエリとして, 複数の始点と単一の終点が与えられる.

•それぞれの始点から終点への経路を探索する.

以下では, 本問題で最も特徴的な概念である合流について定義する.
定義 3.4 (合流) あるユーザの組 u1 , u2 が合流するとは, それぞれの経路中で共通したある頂点 v から目的地まで一緒に移動することを開始することをいう. この頂点 v を u1 , u2 の合なお, 本問題では, 一度合流したユーザは目的地に到達するま𝒔 𝒖𝟏

𝒗𝟏
𝒖𝟏 と 𝒖𝟐 は𝒗𝟑 で合流

𝒔 𝒖𝟐

𝒔 𝒖𝟑

𝒗𝟐

𝒗𝟓

𝒗𝟑
𝒗𝟒

で経路中で再び分離することはないものとする. このような仮定をおく理由としては以下の 2 点がある. まず, ユーザが途中で分離するコストは, 各応用例によって様々な原因が存在する

𝒗𝟔

ためにその見積もりは簡単ではなく, むしろ本論文が考える問題のように目的地が単一の場合は, 分離が全く起こることがな

𝒖𝟏 と 𝒖𝟐 は𝒗𝟒 , 𝒖𝟑 は𝒗𝟔 まで経路が定まっている

い応用例が多い. また, この仮定と目的地が単一であるということより, 本研究では単純な定式化と高速な手法の提案が可能

図に対応する𝑅と𝑀
𝑅 𝒖𝟏 = 𝒗𝟏 → 𝒗𝟑 → 𝒗𝟒
𝑅 = 𝑅 𝒖𝟐 = 𝒗𝟐 → 𝒗𝟑 → 𝒗𝟒
𝑅 𝒖𝟑 = 𝒗𝟓 → 𝒗𝟔となっている .
次に, 上で定義した合流の定義を用いて, 目的地まで一緒に移𝑀 = 𝑀 𝒖𝟏 , 𝒖𝟐 = (𝒖𝟏 , 𝒖𝟐 , 1, 1 )動するユーザの集合を表す合流集団という概念を定義する.
定義 3.5 (合流集団) あるユーザ u1 , u2 について合流点が存在

図 2 3 人のユーザに対する R, M の例

するとき, その合流点とそれ以降の共通するパスにおいて, u1と u2 は同一の合流集団に属すると呼ぶ. ある経路の集合 R と流点と呼び, それぞれの経路の何番目の頂点であるかを表す

合流点の集合 M が与えられたとき, それぞれのユーザ u とそ

整数の組 (i, j) によって定まる. 合流点が存在する全てのユーの経路 R(u) の i 番目の辺 e(R(u), i) に対し合流集団が一意にザの組 (u1 , u2 ) とその合流点に対応する整数の組 (i, j) から定まる. これを Group(R, M, u, i) と表記する.

なる四つ組 (u1 , u2 , i, j) の集合を M とする. またこのとき,

M (u1 , u2 ) = (i, j) と表記する.

3. 2 問 題 設 定
本論文で考える問題は, 複数のユーザの初期位置と単一の目た だ し, ユ ー ザ の 組 u1 , u2 に 対 し 合 流 点 が 存 在 し て的地が与えられた際に, 各ユーザの初期位置から目的地への移M (u1 , u2 ) = (i, j) のとき, u1 , u2 の経路のそれぞれ i 番目,

動距離の総和を小さく保ちつつ, ユーザ同士の合流によりでき

j 番目の頂点とそれ以降のパスが一致しなければならないため,るだけ大きな利益を獲得できるような経路を発見することであ以下の制約を導入する.

る. そのためにまず, ユーザ同士の合流による利益を目的関数に組み込むための関数を定義する.

l(R(u1 )) − i = l(R(u2 )) − j >=0(1)

利益を意味する正の実数を返す関数 α(U ′ ) を導入し, これを利

0<k<
= l(R(u)) − i の k に対し,e(R(u1 ), i + k) = e(R(u2 ), j + k)

定義 3.6 (利益関数) 合流集団 U ′ ⊂ U を引数として受け取り,(2)

益関数と呼ぶ.
本論文では, 以下で定める目的関数を最小化するような経路以上で定義した R, M についての 3 人のユーザに対する例を
図 2 に示す.
ここで, あるユーザの組 u1 , u2 が, それぞれの経路の途中から目的地までのパスを共有する場合でも, 合流せずに別々に移動することも可能であることに注意されたい. これは, 以下のの集合を探索する問題を考える. その中で利益関数は, 各ユー
ザに対してその経路中の各辺の長さに対する重みとなる. したがって, この利益関数は値が小さいほど合流する利益が大きいことを意味する. この関数に関しては, 3. 3 節においてさらに詳しい説明を行う.

ような現実的状況を反映している.
まず, u1 , u2 が異なる時間帯に辺 e を通過する場合, u1 , u2 が問題 (単一終点合流問題)

一緒に移動したと考えることは不適切である. また, タクシー

以上の定義により, 本論文で考える問題は以下のように定式化の利用料金の総和を最小化するという応用例を考えた際, 同じされる.

タクシーに乗るユーザのみが一緒に移動していると考えるのが入力 各ユーザの初期位置 su ∈ V , 目的地 vT ∈ V

自然である. このとき, u1 , u2 が同じ時間帯に辺 e を通過する

出力 各ユーザの初期位置から目的地までの経路の集合 R, 合流

場合でも, u1 , u2 が異なるタクシーに乗車している場合は, 別々点の集合 Mに移動したとみなすべきであろう.

目的関数 (最小化)

我々の知る限り, 経路を合流させるという概念に対し, この制約を導入した既存研究は存在しない. この制約は, グラフ上
を人やデータが実際に移動する応用例を考えた場合によく発生∑ l(R(u))∑
u∈Uα(Group(R, M, u, i)) ∗ we(R(u),i)

(3)

i=1

するが, 定式化を難解なものにするためこれまで扱われてこな

つまり, 与えられる全てのユーザに対し, その経路の移動距離かった. 第 2 節で述べた最小シュタイナー木問題, Buy at Bulkから合流による利益を割り引いた値の総和を目的関数として定問題についてもこれは同様である. 一方で本論文ではこれらの義し, これを最小化する経路を探索する.

制約により, これらの既存研究よりも, 集合経路最適化に関する3. 3 利益関数が持つ意味応用例でさらに実用的に適用可能となっている.

ここで, 利益関数 α の関数の性質が持つ具体的な意味について説明する. まず, 本問題と最小シュタイナー木問題の関連にる手法の速度と精度を検証する. このとき, アルゴリズムを実ついて以下の定理が成り立つ.

行するにあたり利益関数の値をあらかじめ決定する必要がある.

定理 3.1 最小シュタイナー木問題は, 本問題における利益関数な状況を反映するため, U’ を合流集団としたとき以下の範囲にの値を以下のように設定した問題である.

α(U ′ ) =利益関数は任意の正の実数の値をとることができるが, 現実的値を限定する. そして, この範囲内でランダムな値を採用し実1|U ′ |(4)

たとえば, ある二人のユーザ u1 , u2 がある辺 e で同じ合流集

験を行う.

1 <
α(U ′ ) < 1|U ′ | =(6)

団に属する場合を考える. 利益関数が (4) 式に従う場合, 二人の要素を持つ合流集団に対する利益関数の値は 1/2 となる. したがって, 上記の目的関数において, u1 , u2 が e を通過することに起因するコストは以下のようになる.

1
1∗ we + ∗ we = we22

4. 提 案 手 法
4. 1 厳密解のアルゴリズム
4. 1. 1 ナイーブな手法(5)

3 人以上の場合も同様に, ある辺 e と集団集合 U ′ に対して合

この手法では, 各ユーザのあらゆる経路と, 可能な全ての合流点を探索することにより, 目的関数を最小にする経路の集合

RT と合流点の集合 MT を見つける.

計 we のコストがかかることになる. これは, 最小シュタイナー

まずここで, ある経路の集合 R と合流点の集合 M に対し,

木問題において, ある辺を採用する場合のコストが, その辺が接各ユーザ u がその経路 R(u) の終点 v(R(u), l(R(u))) で属す合続する頂点数等に関わらず常にその辺の重み we となることに流集団を考える. このとき, 全ユーザ U はこれらの合流集団に対応している. つまり, (4) 式のように利益関数を設定し, 最小

よって分割される. この分割を P と表す. 合流集団の定義より,シュタイナー木問題のクエリとなる頂点をユーザの初期位置や分割 P によるそれぞれの合流集団 Ui に属する全てのユーザの目的地とみなすことにより, 本問題を最小シュタイナー木問題

経路の終点は同一の頂点となる. これを v(R, M, P, Ui ) と表記に適用することが可能であることがわかる. なお, 10 人以下のする. 本手法では, これら (R, M, P ) の三つ組を探索における合流集団に対する (4) 式の値は図 3 に示されている.

一つの状態としてとらえ, 初期状態 (R0 , M0 , P0 ) から遷移可能

また本問題では, 利益関数の値を任意の正の実数とすることなあらゆる状態へと遷移させることにより探索を行う. 以下, 特ができるため, 様々な現実的制約を, 自然な形で利益関数に反映に断りのない限り, R, M, P はそれぞれ, 探索の過程で到達可能させることが可能である.

なある経路の集合, 合流点の集合, ユーザの分割を表す.

例えば, 一緒に移動させたくないユーザの組がいくつかわかっ

初期状態の R0 として, 各ユーザ u の経路 R0 (u) はそのユーているとする. この場合には, これらのユーザの組を含む合流

ザ u の初期位置 su のみをもつ. つまり, 各ユーザ u に対し集団に対する利益関数の値を十分大きくすることにより, これv(R0 (u), 0) = su , l(R0 (u)) = 0 とする. また, 初期状態におけらの組が合流することを避けることができる.

る合流点の集合 M0 は要素を持たないものとする. そして, こまた, それぞれの合流集団を 1 つのタクシーで移動する集団

れらの R0 , M0 に対して P0 を定める. 初期状態では合流点が存とみなし, その利用料金の総和を最小化する応用例に本問題を在しないため, P0 の要素は, 各ユーザを単一の要素とする合流

適用するとする. タクシーに乗車できる人数は 4 人から 5 人程集団となる.

度が限界であるため, それ以上の人数で合流することがないよ

ある状態 (R, M, P ) に対し, 1 回の状態遷移は以下の三つのうにすることが望ましい. この場合, 一定以上の人数を含む合ステップからなる.

流集団に対する利益関数の値を十分大きくすることにより, 合1. 選択 P に含まれるある二つの合流集団の組 U1 , U2 を選択

流集団の要素数を一定以下に抑えるといったことも可能となる.

する.

この場合の利益関数の例は図 4 に示されている.

2. 移動 あ る 頂 点 v ′ を 選 択 す る. U1 ま た は U2 に 属 す 全
ユーザ u の経路 R(u) に対し, path(v(R, M, P, U1 ), v ′ ) または path(v(R, M, P, U2 ), v ′ ) を追加する.

3. 合流 U1 の要素 u1 と, U2 の要素 u2 の全ての組合せについて, m(u1 , u2 ) = (l(R(u1 )), l(R(u2 ))) を M に追加する.
ただし, ある状態 (R, M, P ) に対し, P に含まれる合流集団が一つ, つまり P = U のとき, 1. 選択のステップにおける二つの合流集団の組 U1 , U2 の選択ができないため, その状態から新た
図 3 最小シュタイナー木問題に対応する利益関数

図4

タクシー相乗りに対応する利益関数の例な状態への遷移は起こらない.
上記の状態遷移では, ある状態 (R, M, P ) に対し, 選択のス
テップで合流集団の組, また移動のステップで移動先の頂点に利益関数の範囲

5 節では, 実際のロードネットワークを用いて, 4 節で提案す関する異なる遷移が存在する. ナイーブな手法では, 初期状態

(R0 , M0 , P0 ) から探索を始め, 遷移可能な全ての状態を生成す初期状態

4. 1. 2 動的計画法による手法

𝑅 = 𝑅# = {𝑅# 0 , 𝑅# 1 , … , 𝑅# |𝑈| }𝑀 = 𝑀# = ∅𝑃 = 𝑃# = {{𝑢0 }, {𝑢1 }, … , {𝑢|2| }, }本手法では, 動的計画法によってナイーブな手法で無駄な計算をしている部分を省くことで高速な計算を実現する. 具体的

ユーザ𝒖𝒊と𝒖𝒌が頂点𝒗𝒌で合流には, 目的関数が各合流集団で独立して計算可能なコストに分
𝑅 = {… }𝑀 = {… }𝑃 = {… }𝑅 = {… }𝑀 = {… }𝑃 = {… }𝑅 = {𝑅# 0 , … , 𝑹 𝒖𝒊 = 𝒑𝒂𝒕𝒉 𝒔𝒖𝒊 , 𝒗𝒌 ,𝑅 = {… }𝑀 = {… }𝑃 = {… }𝑹 𝒖𝒋 = 𝒑𝒂𝒕𝒉 𝒔𝒖𝒋 , 𝒗𝒌 , 𝑅# |𝑈| }𝑀 = {𝑴 𝒖𝒊 , 𝒖𝒋 }𝑃 = { 𝑢0 , 𝑢1 , … , 𝒖𝒊 , 𝒖𝒋 , … , {𝑢 |2| }, }𝑅 = {… }𝑀 = {… }𝑃 = {… }解可能なことを用いて, 各合流集団を表すユーザの集合 U ′ とその存在位置を表すあらゆる v ′ の組 (U ′ , v ′ ) に対し, 最小のコストを記憶する. ただし, 各組 (U ′ , v ′ ) の値を愚直に計算した場
合には十分な高速化がのぞめない. 本手法では, (U ′ , v ′ ) の値を

・
・
・

・
・
・

・
・
・

優先度付きキュー等のデータ構造を用いながら適切な順序で処理することで, 少人数のクエリに対し十分な応答性能を実現す
る. 特別なデータ構造の使用と計算順序の変更によるこの高速

𝑅 = {… }𝑀 = {… }𝑷 = {𝑼}𝑅 = {… }𝑀 = {… }𝑷 = {𝑼}𝑅 = {𝑅 0 , 𝑅 1 , … , 𝑅 |𝑈| }𝑀 = {𝑀 𝑢@ , 𝑢A , 𝑀 𝑢B , 𝑢C , … }𝑷 = {𝑼}𝑅 = {… }𝑀 = {… }𝑷 = {𝑼}𝑅 = {… }𝑀 = {… }𝑷 = {𝑼}

化は, 本問題の定式化から簡単に導き出されるものではなく, このアルゴリズムを本論文における主要な貢献の一つとしている.
動的計画法の適用

図5

以下ではまず, 目的関数を各合流集団ごとに独立したコスト

探索のイメージに分解する.
ることにより最適解を求める. 図 5 は, 以上で説明した探索のR(U ′ ) = {Ru | u ∈ U ′ }イメージである. 図中の各長方形は探索の過程で生成される各M (U ′ ) = {M (u1 , u2 ) | u1 , u2 ∈ U ′ }状態 (R, M, P ) を表し, 矢印は状態の遷移を表す.

Algorithm1 に, 以上で説明したナイーブな手法の詳細なアGroup(R(U ′ ), M (U ′ ), u, i) = Group(R, M, u, i)と表記すると, U ′ に起因する目的関数のコストは以下のようにルゴリズムを示す.

書ける.

∑ l(R(u))∑

Algorithm 1 ナイーブなアルゴリズム
1: CostT ← ∞, RT , MT , PTu∈U ′2: N aive(R0 , M0 , P0 , 0) を実行とがわかるため, 以下ではこれを v(R(U ′ ), M (U ′ ), U ′ ) と表記

4: procedure Naive(R, M, P, Cost)
5:

if P の要素数 = 1 then

6:

U ′ ← P の要素

7:

Cost + = d(v(R, M, P, U ′ ), vT ) ∗ ( 全ユーザの人数 )8:

for all u ∈ U ′ do

10:
11:
12:
13:
14:

▷ 全員が同一の合流集団に属す

Ru ← path(v(R, M, P, U ′ ), vT ) を追加(CostT , RT , MT , PT ) ← (Cost, R, M, P ) に更新
for all U1 , U2 ∈ P s.t. U1 ! = U2 do▷ 選択のステップ

for all v ′ ∈ V dofor all u1 ∈ U1 do▷ 移動のステップ17:′ ← path(v(R, M, P, U ), v ′ ) を追加
Ru
1
1

18:

Cost′ ← d(v(R, M, P, U1 ), v ′ )α(U1 ) を加算
for all u2 ∈ U2 do

20:′ ← path(v(R, M, P, U ), v ′ ) を追加
Ru
2
2

21:

Cost′ ← d(v(R, M, P, U2 ), v ′ )α(U2 ) を加算
for all u1 ∈ U1 do

25:
26:
27:
28:

▷ 合流のステップ

for all u2 ∈ U2 do
M ′ ← (u1 , u2 , l(R(u1 )), l(R(u2 ))) を追加

24:

P ′ から U1 , U2 を削除
P ′ に U1 ∪ U2 を挿入
N aive(R′ , M ′ , P ′ , Cost + Cost′ )returnそれに属すユーザの経路の終点を意味する頂点 v ′ のあらゆる組(U ′ , v ′ ) を考え, 最小の (7) 式の値を与える R(U ′ ), M (U ′ ) を記
を複数の部分問題に分割し、部分問題の計算結果を記録しながなお, 本節で紹介するアルゴリズムは, 手法を説明する上での簡潔さを重視し, 最適解となる R や M に対する目的関数の値

Cost′ ← 0, R′ ← R, M ′ ← M, P ′ ← P

23:

本手法では, 合流集団をあらわすユーザの各部分集合 U ′ と,ら解く手法は動的計画法と呼ばれる.

return

16:

22:

する.

憶することにより計算を進める. このように, 対象となる問題

if CostT > Cost then

15:

19:

i=0

また, v(R, M, P, U ′ ) も U ′ , R(U ′ ), M (U ′ ) のみに依存するこ

3: RT , MT を出力

9:α(Group(R(U ′ ), M (U ′ ), u, i)) ∗ we(R(u),i) (7)を求める. 具体的な R や M は, アルゴリズムの各ステップにおいて R や M に関する具体的な情報を記憶することにより,復元することが可能である.
具体的な計算ステップ
以下では, 合流集団を意味するユーザの集合 U ′ と頂点 v ′ の組 (U ′ , v ′ ) に対して, v(R(U ′ ), M (U ′ ), U ′ ) = v ′ となるあらゆる R(U ′ ), M (U ′ ) に関する (7) 式の最小値を dp(U ′ , v ′ ) とする.
この値は, U ′ ごとにあらゆる v ′ に関して, |U ′ | の値が小さい順に計算が可能であり, 最適解に対する目的関数の値は dp(U, vt )に対応する. 以下の説明では, アルゴリズムの直観的な意味に基づいた説明を行う. 本手法の厳密な計算ステップは Algorithm2に示されている.
まず, dp(U ′ , v ′ ) に対し, U ′ はある合流集団, v ′ は合流集団 U ′が存在する頂点を表すものと解釈されたい. このとき, dp(U ′ , v ′ )は, ある合流集団 U ′ が頂点 v ′ に存在するためにかかるコスト

Algorithm 2 動的計画法によるアルゴリズムの最小値とみなすことができる. ここで, 合流集団 U ′ が頂点 v ′1: for all U ′ ⊂ U doに存在するという状態をより詳細にみると, さらに以下の 2 種

2:類の状態に分類される.

3:(1) さらに小さい合流集団 U1 , U2 が v ′ で合流して U ′ となった′′′

(2) 他の頂点 w に U が存在していて, w から v へ U が移動してきた
以下では, 各合流集団 U ′ と各頂点 v ′ に対し, 状態 (1) のみに対応するコストを dp′ (U ′ , v ′ ) とする. dp(U ′ , v ′ ) には状態 (1)と状態 (2) の両方の状態に対するコストの最小値が記憶される.
′′本手法では, U ごとに, |U | の値が小さい順に, あらゆる頂点

dp(U ′ , v) ← ∞, dp′ (U ′ , v) ← ∞4: for all u ⊂ U do
5:dp(u, su ) ← 0

6: for all U ′ ⊂ U do
7:8:

▷ U ′ を |U | の小さい順にループ

for all v ∈ V do

▷ (1) の計算

for all U1 , U2 ⊂ U s.t. U1 , U2 は U ′ の分割 do

9:dp′ (U ′ , v) ← min(dp′ (U ′ , v), dp(U1 , v) + dp(U2 , v))

10:Q ← dp′ (U ′ , v) + ( 移動のコスト ) と v の組を持つ優先度付
きキューに関して dp′ (U ′ , v ′ ) を計算しその後 dp(U ′ , v ′ ) を計算する. U ′11:に関して dp, dp′ の計算をしているとき, U ′ よりも要素数の小12:′▷ 二次元配列 dp を初期化

for all v ∈ V do

▷ (2) の計算

for all v ∈ V do
Q ← (dp′ (U ′ , v), v) を追加

さい合流集団に対する dp, dp は既に求まっていて計算に利用

13:

出来る.

14:

(val, v) ← Q から取り出した組 (ただし val は Q で最小)

まず, ある合流集団 U に対し, あらゆる頂点 v について15:

if val < dp(U ′ , v) thendp′ (U ′ , v ′ ) を計算するステップについて説明する. dp′ (U ′ , v ′ )16:dp(U ′ , v) ← val

は, さらに小さい合流集団が頂点 v ′ で合流し合流集団 U ′ とな17:

for all w ∈ V s.t. w は v に隣接する頂点 do

18:

Q ← (val+ 辺 (v, w) の重み , w) を挿入′′

り, まだ移動していない状態に対するコストの最小値を表してwhile Q の要素数 > 0 do

いる. ここで以下の式を計算する.

U1 , U2 が別々にゴールに向かうコストを Cost2 とする. ただし,dp′ (U ′ , v ′ ) = min(dp(U1 , v ′ ) + dp(U2 , v ′ )′| U1 ∪ U2 = U , U1 ∩ U2 = ∅)これら Cost1 , Cost2 を計算するとき, U1 , U2 以外の合流集団と(8)

次に, この合流集団 U ′ を, あらゆる頂点から頂点へ移動させたコストを dp(U ′ , v ′ ) に記憶する. ここでは, 以下の式を計算
する.

dp(U ′ , v ′ ) = min(dp′ (U ′ , w) + d(w, v ′ )|w ∈ V )の合流は考えない. このとき, Cost2 − Cost1 の値を, U1 , U2 に対する優先度と定める.

R, M, P という状態に対し, 優先度を計算する合流集団の組を U1 , U2 ∈ P とする. また, v1 = v(R, M, P, U1 ), v2 =v(R, M, P, U2 ) とおく. このとき, Cost1 , Cost2 値はそれぞれ(9)

ただしここでは, Dijkstra 法のように, dp′ (U ′ , v ′ ) の値が小さい頂点からの移動を順に考えることにより, 効率的な計算を実現する.
以上の方法により, あらゆる U ′ , v ′ に関して dp(U ′ , v ′ ) が求まる.
本手法の計算量は, O(2|U | (|E| + |V |)log(|V |) + 3|U | |V |) となる.

4. 2 近似アルゴリズム
本手法では, ナイーブな手法と同様に, 初期状態の三つ組(R0 , M0 , P0 ) の状態を遷移させて解を求める. ただし, ナイー
ブな手法のように全ての経路や合流点を探索することはしな
い. ここでは代わりに, 以下の優先度という概念を定義し,(R0 , M0 , P0 ) から優先度の値に応じて貪欲に合流集団の組と合流点を選択することにより計算を行う. 優先度はある二つの合流集団によって定まり, それらが合流することで発生する利益の大きさを表す.

以下のようになる.

Cost1 = min(d(v1 , w)|U1 |α(U1 ) + d(v2 , w)|U2 |α(U2 )+ d(w, vT )|U1 ∪ U2 |α(U1 ∪ U2 ) | ∀w ∈ V ) (10)Cost2 = d(v1 , vT )|U1 |α(U1 ) + d(v2 , vT )|U2 |α(U2 )(11)

この手法では, (R, M, P ) という状態に対して, P 内の合流集
団のあらゆる組の優先度を計算し, その値が最大となる組を選択し合流させる. このときの合流点は, その組の優先度の計算で最小の Cost1 の値を与えた頂点とする.
本手法では, P 内の任意の合流集団の組の優先度を管理する
平衡二分木のデータ構造 Q を用いる. 組 U1 , U2 に関する優先度の場合, (U1 と U2 の優先度 , U1 , U2 ) の三つ組として Q に挿入する. Q から値を取り出すときは, 優先度の値が最も大きい
三つ組を取り出す. Q から取り出した優先度の情報に応じて P
内の二つの要素を合流させる.
このとき, 合流が起こるたびに P 内の合流集団のあらゆる組の優先度を計算することは効率的ではない. 本手法では, Q 内の情報を動的に管理することにより高速な計算を実現する. 具

優先度 P riority:

体的には, (U1 と U2 の優先度 , U1 , U2 ) という情報を Q から取R, M, P という状態に対し, P のある異なる二つの要素からり出して U1 と U2 を合流させるとき, Q から U1 もしくは U2なる組 U1 , U2 が与えられる. U1 , U2 をいずれかの頂点で合流に関する三つ組を削除し, U1 ∪ U2 と P 内の他の合流集団に関させてゴールへ到達させたときコストを Cost1 とする. ここで,する優先度の三つ組を追加する.

合流点としては最もコストの小さくなる頂点を選択する. また,本手法の計算量は, O(|U |2 |V |log(|U |)) となる.

表 1 データセット

Algorithm 3 近似アルゴリズム

都市名 頂点数

辺数

取得年/月

P riority ← U1 と U2 の優先度

東京12108 38823

2015/10Q ← (P riority, U1 , U2 ) を挿入

京都6617 16658

2015/12

1: for all U1 , U2 ∈ P s.t. U1 =| U2 do2:
3:

4: Cost ← 0, R ← R0 , M ← M0 , P ← P0
5: while P の要素数 > 1 do

5. 1. 3 パラメータ調整

6:(val, U1 , U2 ) ← Q から取り出した三つ組

7:

P から U1 , U2 を削除

8:

v1 ← v(R, M, P, U1 ), v2 ← v(R, M, P, U2 )9:v ′ ← U1 と U2 の合流点

10:

Cost + = d(v1 , v ′ )|U1 |α(U1 ) + d(v2 , v ′ )|U2 |α(U2 )11:

for all (val′ , U1′ , U2′ ) ∈ Q s.t. U1′ または U2′ が U1 か U2 do

12:
13:

Q から (val, U1′ , U2′ ) を削除
for all U ′ ∈ P do

それぞれのクエリに対応する利益関数の値は, 3. 3 節で議論
した通り, それぞれの合流集団に対し, (6) 式の範囲内でランダ
ムな値を採用する.

5. 1. 4 メモリ使用量
ナイーブな手法と近似手法では, 任意の 2 点間の最短距離と, その最短距離を与えるパスに関する情報を必要とする.
本実験では, Dijkstra 法によりあらかじめ求めた任意の 2 点

14:

P riority ← U1 ∪ U2と U ′ の優先度

間の最短距離を 2 次元配列に格納し, 各クエリを実行して

15:Q ← (P riority, U1 ∪ U2 , U ′ ) を挿入

いる. またあらゆる頂点の組 (s, t) に対し, 頂点 s に隣接し,16:

P に U1 ∪ U2 を挿入

d(s, t) = d(s, w) + d(w, t) となるような頂点 w も 2 次元配列

17:

for all u1 ∈ U1 doとして保存しておく. この情報を格納しておくことで, 任意の

18:
19:
20:
21:
22:
23:

for all u2 ∈ U2 do
M ← (u1 , u2 , l(R(u1 )), l(R(u2 ))) を追加
for all u1 ∈ U1 do
R(u1 ) ← path(v1 , v ′ ) を追加
for all u2 ∈ U2 do
R(u2 ) ← path(v2 , v ′ ) を追加

頂点組 (s, t) の最短距離を与えるパス path(s, t) を O(|V |) 時間
で取得できる. この配列のサイズは表 1 のデータセットに対し
数 GB 程度であり, 今回実験に使用したマシンのメモリに十分収まる. さらに大きな都市に対して本手法を適用する場合には,SmPG のアルゴリズム [16] 等を利用することにより, 十分な実

24: U ′ ← P の要素

行速度を保ちながら使用メモリ量を削減することが可能である

25: Cost + = d(v(R, M, P, U ′ ) ∗ ( 全ユーザの人数 )と考えられる.

26: for all U ′ ∈ P の要素 do
27:
28:

for all u ∈ U ′ doRu ← path(v(R, M, P, U ′ , vT ) を追加

29: R, M を出力

動的計画法によるアルゴリズムに関しては, 実用的な速度で実行可能な最大人数である 10 人程度のクエリに対し, 数 MBから数十 MB 程度のメモリを必要とするのみである.

5. 1. 5 実 験 方 法
本実験では, ユーザの人数ごとにクエリを 100 個ずつ生成し,前節の各手法を適用した場合の実行時間と精度を調べた. ユー

5. 評 価 実 験

ザの初期位置, 目的地はクエリごとにランダムに生成されていこの章では, 実際のロードネットワークを用いた実験により,る. 利益関数に関しても, クエリごとに上記の範囲内でランダ

提案した手法の応答性能と精度を検証する.

5. 1 実 験 方 法

ムに生成されている.

5. 2 実 行 時 間

5. 1. 1 実 行 環 境
本実験には, CPU が Intel Core i5, メモリが 16GB の Mac のマシンを利用した. アルゴリズムは C++で実装され, gcc 5.2.0を用いて最適化オプション-O2 の設定でコンパイルされた.

5. 1. 2 データセット
本論文はロードネットワーク上の経路探索手法の提案を行っている. したがって公的に入手可能な実際のロードネットワー

東京の道路網にクとして, Open Street Map Japan（注 1） より入手可能なデータ適用した場合の実行時間

を用いて実験を行った. また本問題においては, 任意のユーザ

図6

京都の道路網に適用した場合の実行時間

実行時間 (少人数)の初期位置と目的地が連結でない限り解が存在しない. そのため, Open Street Map Japan より取得したデータに対し, 非連

図 6 より, 動的計画法による手法, 近似手法ともに, ナイーブ

結な頂点を省く等の簡単な前処理を行っている. 前処理を行っな手法よりも大きく実行性能が改善されている. 特に動的計画

た後の各グラフのサイズ等は, 表 1 にまとめられている.

法による手法では, 8 人程度以下の人数に対し, 数秒以内に解が計算できることがわかる.
待ち合わせの応用例を想定した場合, 8 人以上の人数で相互（注 1）：https://openstreetmap.jp/に合流しながら待ち合わせ場所に向かうことは稀であると考えられるため, 動的計画法による手法は, 十分な実行性能を有しているといえる.
次に, 近似手法を多人数のクエリに適用した結果を以下に謝

辞本研究は JSPS 科研費 15K00423, 栢森情報科学振興財団, および独立行政法人科学技術振興機構 (JST) の研究成果展開事示す.

業「センター・オブ・イノベーション (COI) プログラム」の助成を受けたものです. ここで心より感謝申し上げます.
文

東京の道路網に京都の道路網に適用した場合の実行時間

適用した場合の実行時間

図7

実行時間 (多人数)

図 7 より, 100 人程度以下であれば, 近似手法は数秒以内に実行可能であることがわかる. これより, 少人数のグループの待ち合わせよりもさらに大規模な応用例にも, 本手法が適用可能であるといえる.

5. 3 精度

東京の道路網に京都の道路網に適用した場合の誤差

適用した場合の誤差

図 8 提案する近似手法の誤差

厳密解を求めるアルゴリズムは, 10 人程度のユーザに対するクエリの応答が限界であるため, 今回は 10 人以下の人数における近似手法の相対誤差の挙動を検証した.
図 8 より, 厳密解が実行可能な 10 人以下のクエリについて,提案する近似手法は 1 人あたり 8%以下の誤差となっている. また, クエリの人数の増加に対し, 誤差の増加が非常に緩やかであり, 多人数のクエリに対しても本近似手法が一定以上のスケー
ラビリティを持つことが予測される.

6. お わ り に
本論文では, 合流による利益を考慮した単一目的地への集合
経路最適化のための問題を定式化し, その手法を複数提案した.
また, 実データを用いた実験により, 厳密解, 近似解両方に関するアルゴリズムが実用的な速度と精度で動作することを確認した.
今後の課題としては, 提案した近似手法の精度の理論的保証に関する考察や, 合流にかかるコストやユーザの出発および到着時間に関する制限などを考慮した定式化への拡張などが挙げられる.

献[1] Da Yan, Zhou Zhao, Wilfred Ng, “Eﬃcient Algorithms for
Finding Optimal Meeting Point on Road Networks,” Proceedings of the VLDB Endowment, Volume 4, pp. 968–979,
2011.
[2] Da Yan, Zhou Zhao, Wilfred Ng, “Eﬃcient processing of
optimal meeting point queries in Euclidean space and road
networks,” Knowledge and Information Systems, Volume
42, pp. 319–351, 2015.
[3] L. Cooper, “An Extension of the Generalized Weber Problem,” Journal of Regional Science, vol. 8, issue 2, pp. 181–
197, 1970.
[4] R. Chen, “ocation Problems with Costs Being Sums of Powers of Euclidean Distances,” Computers & Mathematicswith
Applications, vol. 10, issue 1, pp. 87–94, 1997.
[5] R. Chen, “Solution of Location Problems with Radial
CostFunctions,” Computers & Mathematics with Applications,vol. 10, issue 1, pp. 87–94, 1997.
[6] L. Cooper, “The Mulitfacility Location Problem:Applications
and Descent Theorems,” Journal of RegionalScience, vol.
17, issue 3, pp. 409–419, 1977.
[7] Winter P, “Steiner problem in networks,” a survey. Networks 17(2), pp. 129–167, 1987.
[8] Richard. M. Karp, “Reducibility Among Combinatorial
Problems,” Complexity of Computer Computations, Partof the series The IBM Research Symposia Series, pp. 85103, 1972.
[9] Prmel, Hans Jrgen, Steger, Angelika, “The Steiner tree
problem: a tour through graphs, algorithms, andcomplexity,” Advanced Lectures in Mathematics, Basics 3: Complexity, pp. 41-62, 2002.
[10] S. E. Dreyfus, R. A. Wagner, “The Steiner problem ingraphs,” Networks, 1, pp. 195–207, 1972.
[11] Bjoern Z, Alexander M, “Calculating Meeting Points forMulti User Pedestrian Navigation Systems,” Proceedings ofAdvances in Artificial Intelligence, Volume 7006 of the series
Lecture Notes in Computer Science, pp. 347–356, 2011.
[12] Baruch Awerbuch, Yossi Azar, “Buy-at-Bulk Network Design,” Proceedings of IEEE FOCS, pp. 542–547, 1997.
[13] C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, M. R.
Salavatipour, “Approximation Algorithms for Nonuniform
Buy-at-Bulk Network Design,” Foundations of Computer
Science 2006, FOCS ’06, pp. 1772–1798, 2010.
[14] Ashish G, Ian P, “An Oblivious O(1)-Approximation forSingle Source Buy-at-Bulk,” Foundations of Computer Science 2009, FOCS ’09, pp. 442–450, 2009.
[15] Srinivasagopalan S, Busch C, Iyengar, “An Oblivious Spanning Tree for Single-Sink Buy-at-Bulk in Low DoublingDimension Graphs,” IEEE Transactions on Computers, Volume: 61, Issue: 5, pp. 700–712, 2012.
[16] D. Delling, A. Goldberg, T. Pajor, and R. Werneck, “Robust distance queries on massive networks,” Proceedings of
22nd ESA, pp. 321–333, 2014.