経路検索ソフトウェア

Summarize Timeline Fact Check

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Summarize Fact Check

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

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

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

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

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

高度な道路経路検索は、道路ネットワークのリアルタイム状況を考慮する。これには、DATEX IIや都市交通計画制御 (イギリス)（英語版）といったインターフェースを通じて道路データサービスから取得する二種類の主要フィードが用いられる。

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

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

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

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

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

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

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