経路検索ソフトウェア

**経路検索ソフトウェア**（けいろけんさくソフトウェア、英：journey planner）、または**ルート検索ソフトウェア**（ルートけんさくソフトウェア）、**乗り換え案内ソフトウェア**（のりかえあんないソフトウェア）とは、二地点以上の間の移動における最適な手段を検索するための特化型検索エンジン。カーナビゲーションは代表的な経路検索ソフトウェアである。場合によっては複数のを組み合わせることもできる。

検索は、最速、最短、乗換回数最少、最安など、さまざまな基準で最適化できる。また、出発・到着時刻の指定、特定の経由地の回避などの制約条件を課すことができる。単一の移動に複数の交通手段の連鎖が含まれうるため、システムは公共交通機関以外も含めた知識を有することがある。

経路検索ソフトウェアは1970年代以来、旅行業界で旅行代理店により広く用いられてきた。インターネットの普及、地理空間情報の増大、情報技術の発展により、利用者が自ら操作できるウェブブラウザベースのオンライン経路検索ソフトウェアが急速に発展した。

経路検索ソフトウェアは発券・予約システムと連動して用いられることがある。例として、イギリスでは鉄道予約システムとして「リアルタイム旅行計画」（RTJP）と呼ばれる二地点間または複数地点間のデータを処理するソフトウェアが存在し、ナショナル・レールの公式ウェブサイトで閲覧できる。

## 歴史
### 第一世代
1980年代後半から1990年代初頭にかけて、いくつかの国有鉄道事業者や大都市圏の交通当局は窓口業務支援のため、経路検索ソフトウェアを開発した。これらは典型的にはメインフレーム上で稼働し、職員が業務端末から利用して顧客からの問い合わせに対応した。

これらは時刻表データベースを利用し、簡単な経路検索機能が含まれていた。ドイツ企業ヘイコン（現在はシーメンスAGの一部）が1989年に開発したハファス時刻表情報システムはその一例であり、同年にスイス連邦鉄道およびドイツ鉄道に採用された。ロンドン交通局がオンライン経路検索ソフトウェアの開発以前に使用していた「Routes」システムも、ロンドンの全公共交通サービスを網羅したメインフレーム型のオンライントランザクション処理経路検索ソフトウェアの例であり、ロンドンの観光名所や主要目的地の大規模データベースを備えていた。

### 第二世代
1990年代、経路検索を実行可能なメモリと処理能力を備えたパーソナルコンピュータ（PC）の登場により、ミニコンピュータやPCにインストールして稼働できる経路検索ソフトウェアが開発された。

PC向けの最初の経路検索ソフトウェアは、アムステルダム大学の情報学専攻の学生エドゥアルト・トゥルプによってアタリPC上で開発された。彼はオランダ鉄道に雇用され、1990年には、オランダ鉄道向けの最初のオフライン経路検索ソフトウェアがフロッピーディスクで販売された。そのソフトウェアの原理は1991年に論文で公表され、まもなくオランダ国内のすべての公共交通を対象に拡張された。

もう一人の先駆者として、スイスのハンス＝ヤコブ・トブラーが挙げられる。彼の製品フィナジュールはIBM PC DOSおよびMS-DOS上で動作し、最初の公開版は1989・1990年の時刻表期間向けに販売された。その後、他の欧州諸国でも独自の経路検索ソフトウェアが相次いで登場した。

この潮流のさらなる展開として、携帯端末などより小型デバイスへの展開が進み、1998年にはハファスのMicrosoft Windows Embedded CE版が登場した。これはアプリケーション本体とドイツ鉄道の全時刻表を6メガバイトに圧縮し、オフラインで動作した。

### 初期のオンライン経路検索ソフトウェア
インターネットの発展により、一般利用者向けのHTMLベースのユーザーインターフェースが登場した。ハファスの試験的ウェブインターフェースは、1995年にドイツ鉄道の公式鉄道経路検索サイトとして公開され、やがてドイツ鉄道の公式ウェブサイトへと発展した。

2001年にはロンドン交通局が、ロンドンの全公共交通機関に加えてロンドンへ向かう鉄道路線をも網羅する、世界初の大都市向け大規模経路検索ソフトウェアを公開した。これは、1990年代後半にロンドン交通局自身のメインフレーム内経路検索ソフトウェアにウェブインターフェースを追加しようとした試みが拡張性の面で失敗したことを受け、ミュンヘンのメンツの経路検索エンジンを採用したものである。

国営鉄道や大都市などの大規模交通ネットワーク向けのオンライン経路検索ソフトウェアは非常に大きなアクセス数に耐える必要があり、そのためトラフィックを維持できるよう最適化されたソフトウェアアーキテクチャが求められる。

大都市圏向けとして世界初のモバイル端末向け経路検索ソフトウェア（メンツエンジンを用いたWAPベース・インターフェース）は、ロンドンのスタートアップ企業キズーム・リミテッド社により2001年に公開された。同社は2000年にイギリス初のモバイル向け鉄道経路検索ソフトウェアを提供し、その後SMSサービスを追加した。2000年からはトラベルライン社が、イギリス全域を対象にバス、長距離バス、鉄道についての地域別経路検索ソフトウェアを提供した。2003年には、イギリスのナショナル・レールが鉄道経路検索サイトを公開した。

初期の公共交通経路検索ソフトウェアは、出発点や終着点として停留所または駅の指定を必要とするのが一般的であったが、観光地の最寄り駅情報によって観光名所などから経路検索できるものが出現した。のちに住所や座標を追加できるよう拡張され、より便利な経路検索が可能となった。

#### 公共交通機関情報の標準化
1990年代後半から2000年代初頭にかけての大規模経路検索ソフトウェアの発展に決定的であったのは、駅・時刻表データ標準の策定と、それらのデータを定期的に集約・配信するワークフローの整備である。特にバスや長距離バスでは小規模事業者が多数存在するため、少数の大手事業者によって標準フォーマットやプロセスが整備されていることが多い鉄道に比べて標準化に向けた課題は大きい。ヨーロッパでは欧州標準化委員会の公共交通機関情報標準である「」が策定されている。

### 分散型経路検索ソフトウェア
2000年代には、特定地域をそれぞれカバーする個別経路検索ソフトウェアを連携させ、広域を対象とするための分散型アーキテクチャを開発するプロジェクトがいくつか生まれた。

2004年に公開された英国運輸省によるは、ジャーニー・ウェブ・プロトコルを用いて、イングランド・スコットランド・ウェールズの140の地方交通当局のデータを対象として8つの地域にまたがって道路と公共交通の双方の経路検索を統合し、所要時間やカーボンフットプリントの比較を可能にした。

ドイツのデルファイプロジェクトは、ドイツの各地域にまたがる分散型経路検索アーキテクチャを開発し、2004年にプロトタイプを公開した。このインターフェースはドイツの トライアスプロジェクトによりさらに発展し、2017年に公表された分散型経路計画のためのオープン API（CEN/TS 17118:2017）というの策定へとつながった。これは、ジャーニーウェブやEUスピリット（欧州各地域間を結ぶ経路検索ソフトウェア）の機能を取り込み、SIRIプロトコル・フレームワークおよびTransmodel参照モデルを活用する。

### 第二世代オンライン経路検索ソフトウェア
公共交通経路検索サイトは非常に高い人気を博し、2005年の時点でドイツ鉄道は既に1日あたり280万件のリクエストに対応していた。経路検索サイトは、各国において最も高トラフィックなウェブサイトの一角を占める。検索された行程に対して旅行券を購入できる機能は、サイトの実用性と人気をさらに高めた。初期の実装例としては、イギリスのトレインラインが郵送によるチケット配送を提供していたが、その後は欧州の多くの国でセルフサービス印刷やモバイル端末による発券方式が普及した。今日、オンライン経路検索は、多くの鉄道および航空事業者にとって主要な販売チャネルとなっている。

Googleは2005年、ポートランド地域を対象としてグーグルトランジットに経路検索機能を導入した。これにより、経路検索で用いる交通データを収集するためのフォーマットであるGeneral Transit Feed Specification（GTFS）が開発され、多数の国にわたる公共交通データフィードの生態系形成に大きな影響を与えた。多くの国の大手事業者がGTFSを出力形式として採用したことにより、Googleは経路検索の対象地域を世界各地へ拡大することが可能となった。グーグルトランジットの経路検索機能は2012年にGoogle マップへ統合された。

経路検索エンジンのさらなる進化として、経路にリアルタイムの遅延・交通障害を反映できるよう、が統合されるようになった。イギリスのナショナル・レールは 2007年に鉄道経路検索にリアルタイム遅延・障害情報を導入した。

また、運行障害情報、混雑度、CO2コストなど、他種のデータを経路情報に統合する動きも重要である。ロンドン交通局のような大都市圏の経路検索ソフトウェアの中には、大規模障害の際に個別駅や路線全体を停止扱いとして、利用不能な区間を除外した経路を提示できるものもある。さらに、アクセシビリティ・データの追加や、車椅子利用など特定の障害に関する要件を考慮して経路検索を最適化するアルゴリズムの導入も進んだ。

2012年ロンドンオリンピックでは、候補経路の提示を操作して混雑の少ない経路へ交通を誘導できるようにした強化版経路案内ソフトウェアが作成された。もう一つの革新として、各競技会場について、公共交通機関の駅・停留所から個々のアリーナ入口に至るまでの全アクセス経路を詳細にモデル化し、セキュリティチェック等による遅延を織り込むために予測および実測の待ち時間を予想移動時間へ反映した。

オープンソースの経路検索ソフトウェアを開発する取り組みである「オープントリッププランナー」は、2009年にオレゴン州ポートランドの公共交通機関の主導で開始され、米欧の機関・事業者の参加を得て開発が進められた。2016年9月に完全版1.0Ver.がリリースされ、中小規模の交通機関や事業者にもライセンス料無しで経路検索を提供することが可能となっている。

## 交通手段
### 公共交通
公共交通経路検索では、利用者は出発地と目的地を入力し、両地点間の公共交通による適切な経路を提供する。移動時間は出発時刻または到着時刻を基準として検索でき、その他の経路選好も指定可能である。

複数交通手段経路検索では、自転車、都市高速鉄道（地下鉄等）、バス、フェリーなど複数の交通手段を組み合わせ手経路を検索できる。多くの経路検索ソフトウェアはドア・ツー・ドア（出発地点から目的地入口まで）検索に対応する一方、駅・空港・バス停など交通ネットワーク上の駅・停留所間のみを対象とするものもある。

公共交通の経路探索は出発・到着時刻、最速、乗換回数最少、アクセシビリティ重視など、異なる最適化基準が存在する。価格による最適化は、通常は別個のアルゴリズムまたはエンジンが担うが、検索結果に運賃を返せる経路検索ソフトウェアは価格による並べ替え・絞り込みを提供する場合がある。価格が重要となる長距離鉄道・航空の計画では、出発日時に柔軟な利用者に対して、最も安価な旅行日を提案することがある。

### 自動車
道路区間の計画は、経路検索ソフトウェア内部の別サブシステムで扱われることがあり、単一モードの走行計算のみならず、パークアンドライドやキスアンドライド等の複数交通手段も考慮されうる。典型的な最適化基準には、最短距離、最短時間、最低コスト、特定経由地の制約などがある。電気自動車の普及は経路検索に新たな課題（充電インフラ、航続距離制約、長い充電時間等）をもたらし、これらを考慮した最適化が求められている。高度な経路検索ソフトウェアの中には、道路区間の平均所要時間、さらにはリアルタイムに予測される平均所要時間を考慮できるものもある。

### 歩行
歩行経路検索は、停留所・駅・各地点への歩行アクセスについて詳細な経路指示を提供する。ここには「段差なし」「車椅子対応」「エレベーターを使わない」等、利用者のアクセシビリティ要件を考慮するオプションが含まれる。

### 自転車
一部の経路検索ソフトウェアは自転車ルートの検索に対応し、自転車で通行可能なすべての経路を統合するとともに、地形（標高・勾配）、交通量、路上の自転車インフラ等の追加情報を取り込むことが多い。静穏・安全な道路の優先、標高変化の最小化、自転車レーンの優先等を指定できるものもありうる。

## データ
経路検索は多種多様なデータに依存し、その品質と網羅性が機能の限界を規定する。多数の情報源から多様なデータを統合するものもあれば、単一モードのみ（例：空港間のフライト行程）、あるいは住所と街路ネットワークのみ（自動車の経路案内）で動作するものもある。

### コンテクストデータ
#### 地点データ
旅客は特定の駅や停留所へ行くために移動するのではなく、アリーナ、観光名所、ショッピングセンター、公園、裁判所等の目的地へ行くために移動する。多くの経路検索ソフトウェアは、こうした「関心地点（POI）」を名称またはカテゴリ（博物館、スタジアム、刑務所等）で検索可能とする。体系的に命名・ジオコーディング・分類された目的地のデータセットは、イギリスのPointXのように商用で入手できるほか、オープンストリートマップなどのオープンデータから派生させることもできる。ロンドン交通局やナショナル・レールのような大手事業者は、最寄り停留所との連絡情報とともに、コールセンターで利用するためのこうしたデータを歴史的に整備してきた。公園、カントリーハウス、スタジアム等の広大なPOIでは、入口の精密なジオコーディングが重要である。

#### 地名集データ
地名集データを統合することで、経路検索のユーザーインターフェースが洗練され、特に停留所検索の補助（曖昧性解消等）に有用である。例えばアメリカには「Newport」という地名が33、イギリスには14存在するが、地名集により同名地名を識別できるほか、乗換結節点と利用者が目指す都市・都心部との関係を示すことも可能となる（例：ロンドンには5前後の空港があるが、実際にロンドン市内に所在するのは一つに限られる）。この種のデータは、Esri、、 等が提供するデータセットを用いることが多い。

### 道路データ
#### 道路ネットワークデータ
道路経路検索は、街路および歩行者道のネットワークデータを用いて、ネットワークの接続性に基づいて経路を計算する）。この種のデータは、アメリカ合衆国国勢調査局が公開しているTIGER（英語版）、Esri、オープンストリートマップなどの公共・商用・クラウドソースデータセットから取得される。これらの基本表現は、ノードとエッジ（すなわち点とリンク）から成るグラフである。さらに、各交通手段の経路計画を支援するため、次のような注釈が付されることがある。

*道路データ：道路種別（高速道路、幹線道路、補助道路、未舗装路等）、右左折規制、速度規制などに加え、平日・週末・祝日等の日種別や時間帯ごとの平均所要時間を備えることで、精度の高い所要時間予測を提供できる。
*自転車用道路データ：自転車ルート番号、交通量、路面種別、照明の有無等、自転車に影響する属性を注記する。
*歩行者道データ：段差、エレベーター、車椅子対応、スロープ等のアクセシビリティ属性に加え、照明、防犯カメラ、非常通報装置などの安全指標を注記し、アクセシビリティ制約付きの経路計画を可能にする。

#### 道路のリアルタイム・データ
高度な道路経路検索は、道路ネットワークのリアルタイム状況を考慮する。これには、DATEX IIやといったインターフェースを通じて道路データサービスから取得する二種類の主要フィードが用いられる。

*状況データ：事故、イベント、計画工事等をネットワークに結び付けられる構造化形式で記述したもの。現在のボトルネックや事象位置を地図や経路案内に反映するために用いられる。
*リンク交通流データ：監視対象ネットワークの各リンクにおける現在の交通流を定量化したもの。予測所要時間を計算する際に、実勢の交通状況を織り込むために用いられる。

### 公共交通データ
公共交通の経路検索が機能するためには、時刻表データを常に最新に保つ必要がある。異なる経路検索ソフトウェア間でのデータ交換と相互運用を容易にするため、いくつかの標準形式が整備されてきた。

2006年に策定されたGeneral Transit Feed Specification（GTFS）は、現在では世界中の何百もの公共交通事業者で使用されている。欧州連合においては、すべての公共旅客輸送事業者が、欧州連合の鉄道時刻表データ交換形式に基づく情報提供の義務を負う。他地域でも同様の交換標準が存在する。

#### 停留所データ
バス・トラム・長距離バスの停留所、駅、空港、フェリー発着場・港湾などの公共交通アクセスポイントの位置と識別情報は、経路検索の基盤であり、停留所データセットは交通データ基盤にとって不可欠である。空間検索や道路ルーティングエンジンと統合するため、停留所はジオコーディングされる。時刻表や路線と統合するため、ネットワーク内で一意の識別子が付与される。旅客が判別しやすいよう、公式名称に加えて、インターフェースで用いる公開短縮コード（例：空港のIATA三文字コード）が与えられることがある。歴史的には、同一停留所に対して事業者ごとに異なる識別子が用いられ、停留所番号が国内や地域内で一意でないことも多かった。国際鉄道連合の駅所在地コードや、英国のシステムのような停留所データ管理システムは、番号の一意性と停留所記述の完全性を確保し、データ統合を大きく促進する。GTFS、、のような時刻表交換形式は停留所データをそのスキーマに含み、オープンストリートマップのような空間データセットは停留所識別子のジオコーディングを可能にする。

#### 公共交通ネットワークのトポロジー・データ
都市地下鉄や都心バスのように運行頻度が非常に高いネットワークでは、特定の出発時刻ではなく平均運行間隔を仮定してトポロジー自体を経路計画に用いることができる。列車やバスの経路データは、検索結果の可視化（例：地図上への列車経路の描画）にも有用である。イギリスのオードナンスサーベイに代表される国の地図作成機関は、データセットに交通レイヤを含めるのが一般的であり、欧州のインスパイア・フレームワークは戦略的デジタルデータに公共交通インフラのリンク情報を含めている。欧州標準化委員会のNeTEx形式は、交通インフラの物理層と論理層を一対一で扱うことを可能にする。

### 公共交通の時刻表
公共交通の運行時刻データは、特定時刻における利用可能な行程を決定するために経路検索で用いられる。歴史的に、鉄道データは各国固有の形式で広く整備されており、バスその他の交通手段についても、VDV 452（ドイツ）、TransXChange（英国）、Neptune（フランス）など、各国標準が存在する。近年では、GTFSやNeTExといった国際標準形式での提供も増加している。地図上に経路を投影するため、GTFSは単純なシェイププロットの指定を可能にする一方、欧州標準化委員会のNeTExやTransXChangeのようなTransmodelに基づく標準は、構成リンクを識別して複数の異なる意味層を区別できるより詳細な表現も許容する。

### 公共交通のリアルタイム予測情報
経路検索は、リアルタイム情報をデータベースに取り込み、至近の移動に対する最適経路選択で考慮できる場合がある。はGPSを用いて車両位置を監視し、リアルタイム情報および予測情報を経路検索システムへ提供しうる。経路検索ソフトウェアは、この種のデータを取得するため、欧州標準化委員会のリアルタイム情報サービス・インターフェース（SIRI）等のリアルタイム・インターフェースを利用しうる。

## 技術
経路検索ソフトウェアは通常、ネットワークと時刻表を効率的にインメモリ表現し、多数の経路候補を迅速に探索できるようにする。計算に必要なノード数が少ない場合や、行程に付随する補助情報へアクセスする場合には、データベース照会も併用される。単一のエンジンがネットワーク全体と時刻表を格納することもあれば、ジャーニーウェブやデルファイプロトコルといった分散型経路計算プロトコルを用いることもある。経路計算エンジンは、経路照会専用のソフトウェア・プロトコルまたはAPIを介して様々な種類の端末上のユーザーインターフェースから利用される。

停留所・路線・時刻表を表現するデータ標準（TransXChange、NaPTAN、Transmodel、GTFS 等）の整備は、相互の適合性を確保しつつ、経路計算エンジンの発展と並行して進められてきた。経路計画アルゴリズムは、計算複雑性理論における典型的課題の一例である。実運用では、精度、解の完全性、計算時間の間で計算資源をどのように配分するかというトレードオフが避けられない。

経路検索の下位問題は、一般に扱うデータ量と制約が少ないため、比較的容易である。もっとも、道路リンクに対し時刻帯ごとに異なる所要時間を関連付ける「道路時刻表」の発展により、道路経路検索においても出発時刻の要素が重要性を増している。

### アルゴリズム
経路検索は、交通ネットワークを表すグラフ上でルーティングアルゴリズムを用いる。時間に依存しない最も単純な場合、（有向）エッジで街路・経路区間を、ノードで交差点を表現する。この種のグラフ上でのルーティングは、ダイクストラ法、A*、ワーシャル–フロイド法、ジョンソン法など、さまざまなアルゴリズムにより効率的に実行できる。各エッジには距離、コスト、アクセシビリティといった重み付けを、場合によってはノードにも重み付けを設定する。

公共交通のような時間依存の要素を取り込む場合、ネットワークのグラフ表現には複数の方式が提案されており、RAPTOR など異なるアルゴリズムが用いられる。

### 自動経路検索
自動経路検索は、利用者が提供した情報に基づいて行程表を自動生成する。一つの方法は、目的地、旅行日程、関心事項を提出すると、短時間で行程が作成されるというものである。別の方法として、航空会社・ホテル・レンタカー会社からの予約確認メールを転送して必要情報を提供する手法がある。

### カスタム経路検索
カスタム経路検索では、利用者がデータベースから適切なアクティビティを選択して、個別の行程表を作成する。Triphobo.comのように関心地点（POI）の事前構築データベースを提供するものもあれば、ユーザー生成コンテンツに依存するものもある。CoMapsのようなコミュニティ開発のモバイル端末向け経路検索ソフトウェアの中には、オープンストリートマップからダウンロードした地図を用いてオフラインで経路計画を行うものがある。

2017年、GoogleはGoogle Tripsと呼ばれるモバイルアプリを公開した。2018年には、データサイエンス、人工知能、音声技術の進展を背景に、カスタム旅行計画系スタートアップへの投資関心が再燃し、AIベースの旅行計画スタートアップであるロラ・ドットコムやホッパー・ドットコムは、経路検索アプリ開発のために多額の資金調達に成功している。

モバイル端末向け経路検索アプリに予約・決済機能が加わると、結果としてMobility as a Service（MaaS）と見なされる。

### 商用ソフトウェア
多くの流通・物流企業は、システムの一部として経路検索ソフトウェアを用い、運用効率の向上を図っている。これらのシステムは GPS追跡やテレマティクス機能を統合することが多く、運用者が車両をリアルタイムで監視し、報告ツールを通じてパフォーマンスを分析し、必要に応じて経路を調整できるようにする。典型的な目標は、総走行距離とアイドリングの削減、燃料消費の抑制、配送信頼性の向上である。

## 関連項目
*グラフ理論
*カーナビゲーション
*高度道路交通システム
*持続可能な交通
*運輸連合
*
*

## 脚注