情報処理学会 インタラクション 2022
IPSJ Interaction 2022

2D112022/2/21

経由地に着目した経路検索システムの提案
渡邉 公輔1,a)

北 直樹1

斎藤 隆文1

概要：既存の経路検索では寄り道をするような経路を検索するとき，寄り道候補ごとに検索をやり直さなければならない．このようにある目的地への経路を複数個考えたいとき，最適経路を推奨するだけでは使用者の選択肢を狭めているのではないかと考えた．そこで本稿では経由地に着目した経路検索システムを提案する．複数の経由地の滞在時間の考慮した OR 経路検索や最短鉄道経路のような特殊経路検索により，使用者の選択肢を広げることを期待する．特殊な経路を検索する本稿のシステムでは使用者は好みの経路を選ぶことになるため，選択肢は広い方が好みに合った経路を提案できる可能性が高い．また従来の経路検索は最適経路を求めたため総料金などの結果だけあれば比較可能だったが，本稿の提案手法は OR 検索や特殊経路検索のように目的地への経路の過程を重視しているため，経路を地理的に比較できることが重要である．そのため複数の経路の経路比較を地図上でも行えるように構築した．さらに構築したシステムを用いて定性的な評価を行った．

1. はじめに他の地点でも可能な場合がある．それは特定の場所に用があるのではなく，特定用途の施設に用がある等の場合であ

現代はインターネットが広く普及し便利なシステムがイる．そのようなとき，経由地を変え複数回検索・比較を繰ンターネット越しに数多く公開されている．経路案内もそり返す必要がある．何度も検索をしなければならない現状のシステムの一つである．公共交通機関を用いて移動をすを解決するために，経由地の OR 検索を製作した．これはる場合，乗換案内などの経路検索を使うのが一般的であ使用者の経路選択の意図を汲み取る方法の一つとして有効

る．出発地と目的地を入力すると瞬時に最適な経路が生成だと期待する．

され，最適な移動手段を知ることができる．最適な移動手

次に一般的でない経路検索を実装し，使用者に多くの選段を知ることは非常に有用だが，最適以外の選択肢を選ぶ択肢を与えられるようにした．一般的でない経路検索とは可能性を除外している可能性がある．そこで本稿では経由電車経路における最短経路のような特殊経路のことである．

地に着目した経路検索システムを提案する．

従来の経路検索では最適な経路は見つけることができる

まず経由駅での滞在を含む所要時間算出など，経由駅でが，それ以外の経路を提案されることはない．それでは寄の自由度を増やすことで従来のサービスでは検索困難な経り道をしたいときなど，使用者が最適経路以外を知りたい路の検索を行えるようにした．従来の経路検索では経由地時に調べることが困難である．そこで特殊経路検索によっにかかる重要度が小さく，設定項目自体少ない．それではて多様な経路を提案することができるようにした．

寄り道をしたいときに寄り道地点に着いてからの行動を再さらに本稿では複数の経路の経路比較を地図上でも行え度調べる必要がある．このような現状を解決するために，るように構築した．従来の経路検索は最適経路を求めたた

経由地に関する設定項目を増やすことのできる経路検索をめ総料金などの結果だけあれば比較可能だったが，本稿の製作した．

提案手法は OR 検索や特殊経路検索のように目的地への経また経由地の OR 検索によって使用者の求める経路をよ路の過程を重視しているからである．そのため経路中の経り多様に表示できるようにした．OR 検索とは経由地のい由地に関する重要度が増し，経路を地理的に比較できるこずれか一つを通るような経路を生成する検索である．経路とが重要である．それらにより使用者は多様な経路の中か選択をするうえで経由地を指定することがしばしばある．

ら欲しい情報を見つけることができると期待する．

経由地を指定する場合，経由地点で何らかの用事を済ます

以上のような提案手法を実現したシステムを製作し，定ことが目的である．しかしその用事を済ますだけであれば性的な評価のためにシステムのデモや使用を通じ意見を集1a)めた．特殊経路検索・地図連動・OR 検索については面白
東京農工大学s176748r@st.go.tuat.ac.jp© 2022 Information Processing Society of Japan

いとの意見が多かった．一方で検索可能範囲・データ量・300

情報処理学会 インタラクション 2022
IPSJ Interaction 2022

2D112022/2/21

設定項目数などが不足だという意見があり，今後改善した

殊経路検索・経由駅 OR 検索ができる．また経由駅での滞いと考えている．

在を考慮した設定項目の有無も違いである．

2. 関連研究3. ユースケース
本節では提案するシステムのユースケースとしていくつ

本節では既に Web 上のシステムとして提供されていおり，多くの人に利用されているものをいくつか紹介する．

かの典型的な検索例を紹介する．

2.1 NAVITIME

3.1 寄り道駅の選択
使用者は「渋谷駅からお台場海浜公園駅まで行きたいが

NAVITIME[1] は様々な用途の経路案内が用意されている．ここでは本稿と特に関連強い 3 つを取り上げる．

2 時間程度，品川駅周辺のカフェか新宿駅の駅ナカカフェ

2.1.1 電車乗換案内で時間をつぶしたい」と考えていると仮定する．そのよう

NAVITIME 電車経路検索 [2] は出発駅と到着駅を指定すな場合，使用者は「渋谷駅からお台場海浜公園駅への経路ることで「時間が早いルート」「運賃が安いルート」「乗換で，120 分間品川駅改札外で下車または 120 分間新宿駅改が少ないルート」の 3 種類の検索が行われる．時間や運賃札内で待機する経路」という条件で検索することもできるが近しいルートがそれぞれ 4 経路ほど示され，最大 16 経路(図 1)．の中から自動でおすすめを抜粋し表示されている．この案
内では経由地を複数個指定できることがメリットである．
これのシステムと比べ，本稿のシステムは特殊経路検索・経由駅 OR 検索・地図連動での経路比較ができる．また経由駅での滞在を考慮した設定項目の有無も違いである．

2.1.2 複数目的地ルート比較
NAVITIME 複数目的地ルート比較 [3] は 1 つの出発地に
図 1 寄り道する場合の検索例

対し複数の目的地を設定でき，それを地図上で比較することができる．一つの目的地につき最適と思われる経路が一つ表示される．この案内では複数の目的地について地理的に比較することができることがメリットである．これのシ

3.2 環状線の回り方

ステムと比べ，本稿のシステムは OR 検索を目的地でなく環状線を回るような経路を通らざるを得ないとき，どち経由駅で行うことが違いである．また経路の候補も特殊経らの方がより良いのかを見つけることができる．使用者は路含め多数表示できる点や経由駅での滞在を考慮した設定「池袋駅か品川駅を通り，新宿駅から東京駅に行きたい」とがある点も違いである．

仮定する．そのような場合，使用者は「新宿駅から東京駅

2.1.3 トラベルプランニングへの経路で，池袋駅か品川駅を通る経路」という条件で検NAVITIME のトラベルプランニング [4] は旅行プラン索することもできる (図 2)．

を作成するためのツールで，目的と滞在時間をタイムテーブルにセットすると間の移動時間を自動で検索することができる．複数の経由地を経由し，滞在時間を指定できることがメリットである．また，そのタイムテーブルから旅のしおりなどを自移動生成できることも強みである．これのシステムと比べ，本稿のシステムは特殊経路検索・経由駅OR 検索を行うことができ，さらに経路候補を特殊経路含

図 2 環状線の回り方を変える検索例

め多数表示できる．

2.2 Google マップ

4. ユーザインタフェース

Google マップ [5] の電車経路案内は Google マップと連制作したシステムは東京都内を通る電車等*1 を使用した

動して検索結果の経路が可視化される．また条件の近しい乗換検索を行うものである．本稿で提案する手法で実装さ経路が複数表示され，公共交通機関の複合的な経路案内をれたシステムは必ずしも最適にならない経路を複数提示できる点がメリットである．しかし経由地設定はできず，し，経路選択の自由度を与えることができる．またそれら移動する度に調べることが想定されているのではないかとの経路を地図上で可視化し経路選択を補助する．さらに複考えている．これのシステムと比べ，本稿のシステムは特*1© 2022 Information Processing Society of Japan

電車以外に新交通・モノレール・路面電車などを含む．

301

情報処理学会 インタラクション 2022
IPSJ Interaction 2022

2D112022/2/21

数経由駅 OR 検索を用い，使用者の主体的な経路選択がで経路の横についているグラフはその経路の形を描画したもきる．のになっており，地図上と同形になる．さらに地図上の円形のポイントは乗換駅を示しており，図 4 では渋谷を選択

4.1 検索した．

4.3 結果詳細
経路の詳細は経路名を選択することで HTML の折り畳み領域が展開され見れるようになる．図 5 では図 3 の検索
条件で「新宿駅内に 120 分待機」という設定をしたため，新宿で 120 分間の待ちが発生している．品川経由の場合も同様に 120 分間下車している時間が組み込まれている．

図 3

3.1 節の検索フォーム

実装したシステムは既存システムとほぼ同様の使い方で検索することができる．インタフェースは Web で構築し，図 3 のような検索フォームで検索する．最低限，出発駅と到着駅を埋め日時で出発時刻を入力すれば検索ができるようになる．3.1 節では「経由駅追加」を 2 回実行して品川と新宿の 2 つの経由駅設定を行った．どちらの経由地も 120 分間の滞在で，下車するかどうかをトグルボタンで
図 5決定する．またどちらかの経由駅を通ればよいので OR 検

3.1 節の「最短距離 - 新宿 検索」の経路詳細索に「経由条件」のトグルボタンを設定する．経由条件は
図 3 では OR 検索だが，他にも上から順に全て経由する経路を生成する AND 検索を選ぶこともできる．

5. 提案手法
4 節で示したように地図連動型経路検索を Web 上にシ

4.2 検索結果

ステムを構築した．システムは大きく WebAPI とユーザインタフェース (UI) に分けることができる．WebAPI は受け取った GET パラメータを解読しそれに沿うような経路を検索し結果を JSON 形式で返却する．UI はユーザからの入力を分解し GET パラメータを作成し WebAPI に送る．返却された結果はユーザにわかりやすいように表示している．

5.1 一般的な経路検索
一般的な経路検索の方法として「最安料金検索」「最短時間検索」「最小乗換検索」等が考えられる．本稿では「最安料金検索」を実装することにした．なぜなら他の「最短図 4

3.1 節の検索結果の一部時間検索」「最小乗換検索」のもととなる検索が「最安料金検索」だからである．電車において最安料金とはすなわ

図 3 の検索結果の一部を図 4 に示す．本稿では経路検索アルゴリズム簡単のために特例運賃などは考慮せず愚直

ち「乗換が少なく営業キロ*2 が短いもの」という条件の経路のことを指す．
電車の運賃は原則として*3 営業キロに比例して段階的にに改札を出入りした場合の金額が出力されている．検索結果の経路を選択するとハイライトされ，地図が連動して経路を表示する．図 4 は「最短距離 - 新宿 検索」と「最小料金 - 新宿 検索」の 2 つを選択し比較している．それぞれの© 2022 Information Processing Society of Japan*2*3

各鉄道会社が制定した駅間の線路の長さのことである．鉄道・路線バス等で運賃計算などに用いる．
定額乗車やその他様々な特例等があるため”原則”とした．特例等に関しては本稿では考慮しない．

302

情報処理学会 インタラクション 2022IPSJ Interaction 2022

2D112022/2/21

変化する．まず，各駅間の営業キロと運賃が分かれば，営の k を 0 から n まで AND 検索を行う．すべての AND 検

業キロを重みとしたグラフを用いて探索することで最小距索の結果が OR 検索の結果になり，このときの検索結果の離を求めることができる．本稿では探索アルゴリズムを単経路数は n 個となる．

純かつ高速で安定した探索が可能なダイクストラ法で探索した．次に，他社乗換の際生じる初乗り料金は各鉄道ごと5.4 地図連動型 UIに距離換算しこれも探索の重みとして付与した．営業キロと距離換算した初乗り料金はどちらも同じ単位で [km] であるから合算し重みとした．この方法では正確な最安料金が必ず出る保証はないが，本稿では厳密な最安料金である必要はない．実際に調べてみたところ大きく外れるようなことはなかったためこの方法で本システムの最安料金検索とする．
厳密には [7] のような手法を用いて最安料金検索が算出される．
図 6 国土地理院白地図

5.2 特殊経路検索
特殊経路検索の方法として候補を 5 個考えた．まず 5.1

地図を連動させるために leaﬂetjs[9] を利用した．地図は節の最安料金検索に最も近い手法の「最短経路」を実装

GoogleMAP[5] と国土地理院の白地図 [10] を利用した．そした．

れぞれ図 4 で Google マップ，図 6 で国土地理院の白地図•の表示例を示す．線路の形状を補完することは難しいため

最短経路
営業キロを最小にする検索•

最安最長経路料金は最安料金のまま営業キロを最長にする検索•

最小乗り換え乗換回数を最小にする検索•

停車駅数最小経路
列車が停車する駅数を最小にする検索

•

寄り道案内
時刻や乗車時間によって自動で寄り道する検索

通過する駅の座標間を直線でつなぎ，路線図を近似したレイヤを作成した．作成したレイヤを UI のイベントに合わせて表示・非表示を切り替えることで地図を連動させている．また，乗換駅をポイントとして描画し，該当経路で使用している駅名・路線名をポップアップ表示できるよう設定した．

6. 評価
本稿のシステムのどのような部分に興味を持てたかな

最短経路は営業キロを最小にする検索だから 5.1 節の乗どの意見を聴き，定性的な評価を行う．手順は以下の通り

換の重みを無視すればよい．他は 5.1 節と同様に，営業キで，旅行好きや電車好きなどを含む 20 代の男女 5 人 (女性ロを重みとしたグラフを用いて探索することで最小距離を3 人，男性 2 人) へ個別に意見を聴くことができた．

求めることができる．一般的な経路検索と比べ最短を通る( 1 ) 本研究の概要を説明する．

ために乗り換え回数が多くなっているのが特徴である．

( 2 ) 使い方の例としてデモを行う．
( 3 ) 被験者にシステムを使用してもらう．

5.3 経由駅の OR 検索
複数の駅を経由する AND 検索を実装し，それを利用しOR 検索を行う．

( 4 ) 被験者の意見を聴く．
被験者のほぼ全員が最初はどのように使うべきなのかわからず，戸惑っていた．概要である程度説明しているが，複数の駅を経由する AND 検索は営業キロを重みとしたOR 検索や地図を使った電車経路の比較は馴染みがなく直グラフのダイクストラ法による探索を複数回行うことで実感的ではなかったことが原因だと考えている．しばらく現する．n 個 (n ≥ 0) の経由駅列 {Vn } に対し出発駅 s と様々なケースを試すうちに使い方や見方が分かり，最終到着駅 t を加え，全経由駅列 {Tn+2 } = {s, V1 , V2 , ..., Vn , t}的に「面白い提案だ」という意見が多かった．特に OR 検を定義する．この駅列について k を 0 から k + 1 まで順

索はほとんど見る機会がなく，私が調査してた限りでは番に Tk と Tk+1 で経路検索を行った経路が複数経由駅のNAVITIME の複数目的地比較 [2] がもっとも近かった．まAND 検索になる．

た「経由先で待機時間を指定できる点も使い勝手が良い」

経由駅の OR 検索は複数経由駅の AND 検索を用いる．という意見が多かった．これらのことより複数経由地での同様に n 個 (n > 0) の経由駅列 {Vn } と出発駅 s と到着駅 t

OR 検索は需要があるのではないかと考えている．それだを定義する．全経由駅列を {T3,k } = {s, Vk , t} として Ta,k

けでなく「待機時間設定や下車・待機設定などもあると使© 2022 Information Processing Society of Japan303

情報処理学会 インタラクション 2022
IPSJ Interaction 2022

い易い」という意見が多かった．

2D11
2022/2/21て行っていきたい．

地図連動型検索も同様に最初こそ抵抗を感じる被験者も今後は一回の検索でダイクストラ法で探索する回数が増いたが，様々なケースを検索していくうちに「普段意識しえることが予想されるため，探索を軽量にする必要がある．

ないことが知れて楽しい」という意見が出た．被験者の多そこでダイクストラ法の高速化の手法 [8] を参考に軽量化

くは，普段の使う経路案内は地図がないもので，路線図はや，グラフ自体も LOP[6] の軽量化方法を参考に軽量化し，見やすいように実際の距離や方角などを歪めた簡易なもの

検索の高速化を図りたい．また本稿では使用者に意見を聞で覚えていた．そのような背景があるために，地理的な要くとを評価としたが，しっかりしたユーザスタディの実施

素から電車経路を見ると楽しいという意見が出ることに繋により提案手法を評価したい．既存手法とは着目する点ががったのだと考えている．

違うため，その点が使用者にどのような影響を与えるのか

国土地理院の白地図に対する意見は被験者による違いがを評価したい．

最も現れた項目だった．遠出や鉄道の歴史などが趣味の場
合，駅名称や経路と地名の対応を取れたほうが有用だとい

参考文献

う意見があった．Google マップより白地図の方が地名や[1]県境などが見やすいためだと推測している．一方で特に意見はないという被験者もいた．
今回実装した特殊経路検索が 1 種類のみだったことと，

[2]
[3]

重みが似ていたため検索方法による差異が生じにくかった．そのため，このような比較をするのであれば「もっと[4]奇抜な検索方法が複数ほしい」という意見が多かった．また経由地に関して，下車駅と乗車駅を変えるような設定も[5]追加出来たらより便利になるという意見もでた．加えて，このシステムはある程度土地勘がある人が使うとより効率[6]的に使えるのではないかという意見もでた．

7. 展望

[7]

本稿の目的は使用者の経路選択に自由度を与えることであり，特殊経路検索・地図連動型 UI・複数経由駅 OR 検索[8]により使用者が思いがけない経路や経由地を見出すことを期待した．本稿のシステムを通じ，最適な経路を行くだけでは知ることのできないような 寄り道 や 遠回り の面白さを使用者に伝えたいと考えている．最適で目的地へ

[9]
[10]

NAVITIME，https://www.navitime.co.jp/(2021.12.19).
乗換案内 - NAVITIME，https://www.navitime.co.jp/transfer/?fromlink=pcnavi.header (2021.12.19).
複数目的地比較 - NAVITIME，https://www.navitime.
co.jp/route/comparison/point/?fromlink=pcnavi.
header (2021.12.19).
旅 行 計 画・プ ラ ン ニ ン グ・旅 の し お り 作 成—
NAVITIME Travel，https://travel.navitime.com/
ja/plan/ (2021.12.19).
Google マ ッ プ ，https://www.google.co.jp/maps(2021.12.19).
宮代 隆平, 葛西 隆也: 最長片道切符, 日本オペレーショ
ンズ・リサーチ学会和文論文誌, Vol.49, No.1, pp.15-20(2004).
池上 敦子, 森田 隼史, 山口 拓真, 菊地 丞, 中山 利宏, 大倉 元宏: 鉄道運賃計算のための最安運賃経路探索 : 複数の鉄道会社を含む場合日本オペレーションズ・リサーチ
学会和文論文誌, Vol.51, pp.1-24 (2008).
安井 雄一郎, 藤澤 克樹, 笹島 啓史, 後藤 和茂: 大規模最短路問題に対するダイクストラ法の高速化日本オペレーショ
ンズ・リサーチ学会和文論文誌, Vol.54, pp.58-83 (2011).
Leaﬂet: https://leafletjs.com/, (2021.12.19).
国土地理院 — 地理院タイル一覧: https://maps.gsi.
go.jp/development/ichiran.html, (2021.12.19).

たどり着くだけでなく，それに至る過程を注意深く見ることで新しい発見があるのではないだろうか．実際に東京都内において鉄道等の公共交通機関で地図連動型経路検索を行うシステムを制作し，5 人の 20 代男女に意見をもらうことで定性評価を行った．結果は特殊経路検索・地図連動・OR 検索については面白いとの意見が多かった一方で検索可能範囲・データ量・設定項目数などが不足だという意見を聴くことができた．
本稿のシステムでは比較できる環境を作ったがそれをうまく使えるような検索を実装できなかったことが改善点として評価された．そのため，今後は特殊経路検索を早急に実装する必要があり，より奇抜な経路検索を提案したい．
また，今回集めた被験者は東京都の路線にあまり精通していない人も多く，東京都しか対応できない本稿のシステムとは相性が悪かった可能性がある．次回評価を行う際には被験者の生活圏などを事前によく確認したい．さらにデー
タ不足で検索できない路線もあるのでデータ集めも並行し© 2022 Information Processing Society of Japan304