「利用者:佐佐木どうよ/sandbox2」の版間の差分
削除された内容 追加された内容
編集の要約なし タグ: 差し戻し済み |
編集の要約なし タグ: 差し戻し済み |
||
4行目:
[[File:OpenTripPlanner screenshot.png|thumb|upright=1.4|[[公共交通機関]]の経路を強調表示した、{{ill|SORTA|en|Southwest Ohio Regional Transit Authority}}の「オープントリッププランナー」経路検索ソフトウェアの[[スクリーンショット]]]]
'''経路検索ソフトウェア'''（けいろけんさく-、英：journey planner）、または'''ルート検索ソフトウェア'''、'''乗り換え案内ソフトウェア'''とは、二地点以上の間の移動における最適な手段を検索するための特化型[[検索エンジン]]。場合によっては複数の{{ill|交通手段|en|Mode of transport}}を組み合わせることもできる<ref name="ichi">Li, Jing-Quan; Zhou, Kun; Zhang, Liping; Zhang, Wei-Bin (2012-04-01). "A Multimodal Trip Planning System With Real-Time Traffic and Transit Information". Journal of Intelligent Transportation Systems. 16 (2): 60–69. doi:10.1080/15472450.2012.671708. ISSN 1547-2450. S2CID 33373852.</ref><ref name="ni">Zografos, Konstantinos; Spitadakis, Vassilis; Androutsopoulos, Konstantinos (2008-12-01). "Integrated Passenger Information System for Multimodal Trip Planning". Transportation Research Record: Journal of the Transportation Research Board. 2072: 20–29. doi:10.3141/2072-03. ISSN 0361-1981. S2CID 109396014.</ref>。
[[検索]]は、最速、最短、乗換回数最少、最安など、さまざまな基準で最適化できる<ref>"Bike Triangle | OpenTripPlanner". GitHub. Retrieved 2017-05-11.</ref>。また、出発・到着時刻の指定、特定の経由地の回避などの制約条件を課すことができる。単一の移動に複数の交通手段の連鎖が含まれうるため、システムは[[公共交通機関]]以外も含めた{{ill|交通ネットワーク分析|en|Transport network analysis}}知識を有することがある。
経路検索ソフトウェアは1970年代以来、旅行業界で[[旅行代理店]]により広く用いられてきた<ref>"TravelTecnik Consultants - Travel & Hospitality Technology: History of Global Distribution Systems (GDS)". Traveltecnik.com. Retrieved 2018-09-25.</ref>。[[インターネット]]の普及、[[地理空間情報]]の増大、[[情報技術]]の発展により、利用者が自ら操作できる[[ウェブブラウザ]]ベースのオンライン経路検索ソフトウェアが急速に発展した。
経路検索ソフトウェアは発券・予約システムと連動して用いられることがある。例として、[[イギリス]]では鉄道予約システムとして「リアルタイム旅行計画」（RTJP）と呼ばれる二地点間または複数地点間のデータを処理するソフトウェアが存在し、[[ナショナル・レール]]の公式[[ウェブサイト]]で閲覧できる<ref>"Plan your journey and buy train tickets for all rail links with our national Journey Planner. Check departure times and prices". nationalrail.co.uk. Retrieved 2025-08-13.</ref>。
==歴史==
16行目:
1980年代後半から1990年代初頭にかけて、いくつかの[[国有鉄道]]事業者や大都市圏の交通当局は窓口業務支援のため、経路検索ソフトウェアを開発した。これらは典型的には[[メインフレーム]]上で稼働し、職員が業務端末から利用して顧客からの問い合わせに対応した。
これらは時刻表データベースを利用し、簡単な経路検索機能が含まれていた。ドイツ企業ヘイコン<ref>"History — HaCon, Fahrplanauskunft HAFAS, Fahrplankonstruktion TPS". Hacon.de. Archived from the original on 2018-09-25. Retrieved 2018-09-25.</ref>（現在は[[シーメンス]]AGの一部）が1989年に開発したハファス時刻表情報システムはその一例であり、同年に[[スイス連邦鉄道]]および[[ドイツ鉄道]]に採用された。[[ロンドン交通局]]がオンライン経路検索ソフトウェアの開発以前に使用していた「Routes」システムも、ロンドンの全公共交通サービスを網羅したメインフレーム型の[[オンライントランザクション処理]]経路検索ソフトウェアの例であり、[[ロンドン]]の観光名所や主要目的地の大規模データベースを備えていた。
===第二世代===
1990年代、経路検索を実行可能な[[メモリ]]と処理能力を備えた[[パーソナルコンピュータ]]（PC）の登場により、[[ミニコンピュータ]]やPCに[[インストール]]して稼働できる経路検索ソフトウェアが開発された。
PC向けの最初の経路検索ソフトウェアは、[[アムステルダム大学]]の情報学専攻の学生エドゥアルト・トゥルプによって[[アタリ (企業)|アタリ]]PC上で開発された<ref>[http://www.trouw.nl/tr/nl/5009/Archief/article/detail/2645851/1998/06/05/Succes-voor-het-eerste-06-nummer-zonder-hijgende-dames.dhtml Trouw, 05/06/1998]</ref>。彼は[[オランダ鉄道]]に雇用され、1990年には、オランダ鉄道向けの最初のオフライン経路検索ソフトウェアが[[フロッピーディスク]]で販売された<ref>"175 years of travel information, chapter:Wel of geen vervoer?" (in Dutch). 9292.nl. 1992-09-02. Retrieved 2018-09-25.</ref>。そのソフトウェアの原理は1991年に論文で公表され<ref>http://kinkrsoftware.nl/contrib/Artikel16b.2a/tulp.pdf, Tulp, Eduard, Searching time-table networks, proefschrift Vrije Universiteit Amsterdam, 1991</ref>、まもなく[[オランダ]]国内のすべての公共交通を対象に拡張された。
もう一人の先駆者として、[[スイス]]のハンス＝ヤコブ・トブラーが挙げられる。彼の製品フィナジュールは[[IBM PC DOS]]および[[MS-DOS]]上で動作し、最初の公開版は1989・1990年の時刻表期間向けに販売された<ref>Tages-Anzeiger, 14 February 2009, p. 14, Hans-Jakob Tobler gestorben. Source: Argus Medienbeobachtung (through archive.org) (PDF file; 70 kB).</ref><ref>Alexandria. Entry Finajour 1.02 Sommer 1989 Archived 2014-12-31 at the Wayback Machine.</ref><ref>Computerwoche: Schweiz: Fahrpläne im Videotex, 22 September 1989 («Schon auf den Fahrplanwechsel in diesem Frühjahr war die PC-Version des schweizerischen Zugfahrplans von der Firma Finajour veröffentlicht worden. Inzwischen wurden gut tausend Exemplare zu einem Stückpreis von hundert Franken verkauft.»)</ref>。その後、他の欧州諸国でも独自の経路検索ソフトウェアが相次いで登場した。
この潮流のさらなる展開として、[[携帯端末]]などより小型デバイスへの展開が進み、1998年にはハファスの[[Microsoft Windows Embedded CE]]版が登場した。これはアプリケーション本体とドイツ鉄道の全時刻表を6メガバイトに圧縮し、オフラインで動作した。
34行目:
[[国営鉄道]]や大都市などの大規模交通ネットワーク向けのオンライン経路検索ソフトウェアは非常に大きなアクセス数に耐える必要があり、そのためトラフィックを維持できるよう最適化された[[ソフトウェアアーキテクチャ]]が求められる。
大都市圏向けとして世界初のモバイル端末向け経路検索ソフトウェア（メンツエンジンを用いた[[Wireless Application Protocol|WAP]]ベース・インターフェース）は、ロンドンのスタートアップ企業キズーム・リミテッド社により2001年に公開された。同社は2000年にイギリス初のモバイル向け鉄道経路検索ソフトウェアを提供し、その後[[ショートメッセージサービス|SMS]]サービスを追加した。2000年からはトラベルライン社が、イギリス全域を対象に
初期の公共交通経路検索ソフトウェアは、出発点や終着点として[[停留所]]または[[駅]]の指定を必要とするのが一般的であったが、観光地の最寄り駅情報によって[[観光名所]]などから経路検索できるものが出現した。のちに住所や座標を追加できるよう拡張され、より便利な経路検索が可能となった。
46行目:
2004年に公開された[[運輸省 (イギリス)|英国運輸省]]による{{ill|トランスポートダイレクトポータル|en|Transport Direct Portal}}は、ジャーニー・ウェブ・プロトコルを用いて、[[イングランド]]・[[スコットランド]]・[[ウェールズ]]の140の地方交通当局のデータを対象として8つの地域にまたがって道路と公共交通の双方の経路検索を統合し、所要時間や[[カーボンフットプリント]]の比較を可能にした。
ドイツのデルファイプロジェクト<ref>"Was ist DELFI? | DELFI" (in German). Delfi.de. Retrieved 2018-09-25.</ref>は、ドイツの各地域にまたがる分散型経路検索アーキテクチャを開発し、2004年にプロトタイプを公開した。このインターフェースはドイツの トライアスプロジェクトによりさらに発展し、2017年に公表された分散型経路計画のためのオープン API（CEN/TS 17118:2017）という{{ill|EN標準|en|European Standard}}の策定へとつながった。これは、ジャーニーウェブやEUスピリット<ref>"EU-Spirit | European travel information network". Eu-spirit.eu. Retrieved 2018-09-25.</ref>（欧州各地域間を結ぶ経路検索ソフトウェア）の機能を取り込み、SIRIプロトコル・フレームワークおよびTransmodel参照モデルを活用する。
===第二世代オンライン経路検索ソフトウェア===
公共交通経路検索サイトは非常に高い人気を博し、2005年の時点でドイツ鉄道は既に1日あたり
[[Google]]は2005年、[[ポートランド (オレゴン州)|ポートランド]]地域を対象としてグーグルトランジットに経路検索機能を導入した<ref>Bibiana McHugh (2005-12-07). "Pioneering Open Data Standards: The GTFS Story". Beyondtransparency.org. Retrieved 2018-09-25.</ref>。これにより、経路検索で用いる交通データを収集するためのフォーマットである[[General Transit Feed Specification]]（GTFS）が開発され、多数の国にわたる公共交通データフィードの生態系形成に大きな影響を与えた。多くの国の大手事業者がGTFSを出力形式として採用したことにより、Googleは経路検索の対象地域を世界各地へ拡大することが可能となった。グーグルトランジットの経路検索機能は2012年に[[Google マップ]]へ統合された。
経路検索エンジンのさらなる進化として、経路にリアルタイムの遅延・交通障害を反映できるよう、{{ill|リアルタイムデータ|en|Real-time data}}が統合されるようになった。イギリスのナショナル・レールは 2007年に鉄道経路検索にリアルタイム遅延・障害情報を導入した。
59行目:
[[2012年ロンドンオリンピック]]では、候補経路の提示を操作して混雑の少ない経路へ交通を誘導できるようにした強化版経路案内ソフトウェアが作成された。もう一つの革新として、各競技会場について、公共交通機関の駅・停留所から個々のアリーナ入口に至るまでの全アクセス経路を詳細にモデル化し、[[セキュリティチェック]]等による遅延を織り込むために予測および実測の待ち時間を予想移動時間へ反映した。
[[オープンソース]]の経路検索ソフトウェアを開発する取り組みである「オープントリッププランナー」<ref>"OpenTripPlanner". Docs.opentripplanner.org. 2016-09-09. Retrieved 2018-09-25.</ref>は、2009年にオレゴン州ポートランドの公共交通機関{{ill|トライメット|en|TriMet}}の主導で開始され、米欧の機関・事業者の参加を得て開発が進められた。2016年9月に完全版1.0Ver.がリリースされ、中小規模の交通機関や事業者にもライセンス料無しで経路検索を提供することが可能となっている。
==交通手段==
70行目:
===自動車===
道路区間の計画は、経路検索ソフトウェア内部の別サブシステムで扱われることがあり、単一モードの走行計算のみならず、[[パークアンドライド]]や[[キスアンドライド]]等の複数交通手段も考慮されうる。典型的な最適化基準には、最短距離、最短時間、最低コスト、特定経由地の制約などがある。[[電気自動車]]の普及は経路検索に新たな課題（充電インフラ、航続距離制約、長い充電時間等）をもたらし、これらを考慮した最適化が求められている<ref>{{cite web|url=https://www.researchgate.net/publication/362609011|title=eDijkstra - Time-Optimal Route Planning for Electric Vehicles|website=ResearchGate|language=en|access-date=2022-10-10}}</ref>。高度な経路検索ソフトウェアの中には、道路区間の平均所要時間、さらにはリアルタイムに予測される平均所要時間を考慮できるものもある。
===歩行===
76行目:
===自転車===
一部の経路検索ソフトウェアは自転車ルートの検索に対応し<ref>Yoon, Ji Won; Pinelli, Fabio; Calabrese, Francesco (2012). "Cityride: A Predictive Bike Sharing Journey Advisor". 2012 IEEE 13th International Conference on Mobile Data Management. pp. 306–311. doi:10.1109/MDM.2012.16. ISBN 978-1-4673-1796-2. S2CID 16827996.</ref>、自転車で通行可能なすべての経路を統合するとともに、[[地形]]（[[標高]]・[[勾配]]）、[[交通量]]、路上の自転車インフラ等の追加情報を取り込むことが多い。静穏・安全な道路の優先、標高変化の最小化、[[自転車レーン]]の優先等を指定できるものもありうる。
==データ==
83行目:
===コンテクストデータ===
====地点データ====
旅客は特定の駅や停留所へ行くために移動するのではなく、[[アリーナ]]、観光名所、[[ショッピングセンター]]、[[公園]]、[[裁判所]]等の目的地へ行くために移動する。多くの経路検索ソフトウェアは、こうした「関心地点（POI）」を名称またはカテゴリ（[[博物館]]、[[スタジアム]]、[[刑務所]]等）で検索可能とする。体系的に命名・[[ジオコーディング]]・分類された目的地のデータセットは、イギリスのPointX<ref>Martin Webb. "Welcome". PointX. Retrieved 2018-09-25.</ref>のように商用で入手できるほか、[[オープンストリートマップ]]などの[[オープンデータ]]から派生させることもできる。ロンドン交通局やナショナル・レールのような大手事業者は、最寄り停留所との連絡情報とともに、[[コールセンター]]で利用するためのこうしたデータを歴史的に整備してきた。公園、カントリーハウス、スタジアム等の広大なPOIでは、入口の精密なジオコーディングが重要である。
====地名集データ====
105行目:
公共交通の経路検索が機能するためには、[[時刻表]]データを常に最新に保つ必要がある。異なる経路検索ソフトウェア間での[[互換性|データ交換と相互運用]]を容易にするため、いくつかの標準形式が整備されてきた。
2006年に策定された[[General Transit Feed Specification]]（GTFS）<ref>"Pioneering Open Data Standards: The GTFS Story". beyondtransparency.org. Retrieved 2017-05-10.</ref>は、現在では世界中の何百もの公共交通事業者で使用されている。[[欧州連合]]においては、すべての公共旅客輸送事業者が、欧州連合の鉄道時刻表データ交換形式に基づく情報提供の義務を負う<ref>"NeTEx". Netex-cen.eu. 2014-03-18. Retrieved 2018-10-03.</ref><ref>Branovic, Irina; Veskovic, Slavko; Mladenovic, Snezana; Milinkovic, Sanjin; Jankovic, Sladjana (October 2011). "SOA architecture for complying with EU railway timetable data exchange format". 2011 10th International Conference on Telecommunication in Modern Satellite Cable and Broadcasting Services (TELSIKS). Vol. 2. IEEE. pp. 630–631. doi:10.1109/TELSKS.2011.6143191. ISBN 978-1-4577-2019-2. S2CID 32189828.</ref><ref>"Transnational exchange of timetable and GIS data as a basis for cross-border ITS services". Gip.gv.at. Archived from the original on 2018-10-03. Retrieved 2018-10-03.</ref>。他地域でも同様の交換標準が存在する<ref>"Transit Schedule Data Exchange Architecture". Google.nl. Retrieved 2018-10-03.</ref>。
====停留所データ====
117行目:
===公共交通のリアルタイム予測情報===
経路検索は、リアルタイム情報をデータベースに取り込み、至近の移動に対する最適経路選択で考慮できる場合がある。{{ill|自動車両位置情報システム|en|Automatic vehicle ___location}}は[[GPS]]を用いて車両位置を監視し、リアルタイム情報および予測情報を経路検索システムへ提供しうる<ref name="ichi"></ref>。経路検索ソフトウェアは、この種のデータを取得するため、欧州標準化委員会のリアルタイム情報サービス・インターフェース（SIRI）等のリアルタイム・インターフェースを利用しうる。
==技術==
経路検索ソフトウェアは通常、ネットワークと時刻表を効率的にインメモリ表現し、多数の経路候補を迅速に探索できるようにする。計算に必要なノード数が少ない場合や、行程に付随する補助情報へアクセスする場合には、データベース照会も併用される。単一のエンジンがネットワーク全体と時刻表を格納することもあれば、ジャーニーウェブやデルファイプロトコルといった分散型経路計算プロトコルを用いることもある。経路計算エンジンは、経路照会専用のソフトウェア・プロトコルまたは[[アプリケーションプログラミングインタフェース|API]]を介して様々な種類の端末上の[[ユーザーインターフェース]]から利用される。
停留所・路線・時刻表を表現するデータ標準（TransXChange、NaPTAN、Transmodel、GTFS 等）の整備は、相互の適合性を確保しつつ、経路計算エンジンの発展と並行して進められてきた。経路計画アルゴリズムは、[[計算複雑性理論]]における典型的課題の一例である。実運用では、精度、解の完全性、計算時間の間で計算資源をどのように配分するかという[[トレードオフ]]が避けられない<ref>Bast, Hannah; Delling, Daniel; Goldberg, Andrew; Müller-Hannemann, Matthias; Pajor, Thomas; Sanders, Peter; Wagner, Dorothea; Werneck, Renato F. (2016-01-01). Kliemann, Lasse; Sanders, Peter (eds.). Algorithm Engineering. Lecture Notes in Computer Science. Springer International Publishing. pp. 19–80. arXiv:1504.05140. doi:10.1007/978-3-319-49487-6_2. ISBN 9783319494869. S2CID 14384915.</ref>。
経路検索の下位問題は、一般に扱うデータ量と制約が少ないため、比較的容易である<ref>Delling, Daniel; Sanders, Peter; Schultes, Dominik; Wagner, Dorothea (2009-01-01). "Engineering Route Planning Algorithms". In Lerner, Jürgen; Wagner, Dorothea; Zweig, Katharina A. (eds.). Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 117–139. CiteSeerX 10.1.1.164.8916. doi:10.1007/978-3-642-02094-0_7. ISBN 9783642020933.</ref>。もっとも、道路リンクに対し時刻帯ごとに異なる所要時間を関連付ける「道路時刻表」の発展により、道路経路検索においても出発時刻の要素が重要性を増している。
===アルゴリズム===
経路検索は、交通ネットワークを表す[[グラフ (データ構造)|グラフ]]上で[[ルーティング]]アルゴリズムを用いる。時間に依存しない最も単純な場合、（有向）エッジで街路・経路区間を、[[頂点 (グラフ理論)|ノード]]で[[交差点]]を表現する。この種のグラフ上でのルーティングは、[[ダイクストラ法]]、[[A*]]、[[ワーシャル–フロイド法]]、[[ジョンソン法 (グラフ理論)|ジョンソン法]]など、さまざまなアルゴリズムにより効率的に実行できる<ref>{{cite web|url=http://docs.pgrouting.org/2.0/en/src/index.html#routing-functions|title=Routing Functions — pgRouting Manual (2.0.0)|website=docs.pgrouting.org|access-date=2017-05-13}}</ref>。各エッジには距離、コスト、アクセシビリティといった重み付けを、場合によってはノードにも重み付けを設定する。
公共交通のような時間依存の要素を取り込む場合、ネットワークのグラフ表現には複数の方式が提案されており、RAPTOR など異なるアルゴリズムが用いられる<ref>{{Cite journal|last1=Delling|first1=Daniel|last2=Pajor|first2=Thomas|last3=Werneck|first3=Renato F.|date=2014-10-30|title=Round-Based Public Transit Routing|journal=Transportation Science|volume=49|issue=3|pages=591–604|doi=10.1287/trsc.2014.0534|issn=0041-1655|citeseerx=10.1.1.652.775}}</ref>。
===自動経路検索===
自動経路検索は、利用者が提供した情報に基づいて行程表を自動生成する。一つの方法は、目的地、[[旅行]]日程、関心事項を提出すると、短時間で行程が作成されるというものである。別の方法として、航空会社・ホテル・レンタカー会社からの予約確認メールを転送して必要情報を提供する手法がある<ref>{{cite web|url=https://www.nbcnews.com/id/wbna22129624 |title=New generation of Web sites for travel planning |publisher=[[NBC News]] |date=2007-12-06 |access-date=2019-03-10}}</ref>。
===カスタム経路検索===
カスタム経路検索では、利用者がデータベースから適切なアクティビティを選択して、個別の行程表を作成する。Triphobo.comのように関心地点（POI）の事前構築データベースを提供するものもあれば、[[ユーザー生成コンテンツ]]に依存するものもある。[[CoMaps]]のようなコミュニティ開発のモバイル端末向け経路検索ソフトウェアの中には、オープンストリートマップからダウンロードした地図を用いてオフラインで経路計画を行うものがある。
2017年、GoogleはGoogle Tripsと呼ばれるモバイルアプリを公開した<ref>{{cite web |title=Google launches a personalized travel planner, Google Trips |date=19 September 2016 |url=https://techcrunch.com/2016/09/19/google-launches-a-personalized-travel-planner-google-trips/}}</ref>。2018年には、[[データサイエンス]]、[[人工知能]]、音声技術の進展を背景に、カスタム旅行計画系スタートアップへの投資関心が再燃し、AIベースの旅行計画スタートアップであるロラ・ドットコムやホッパー・ドットコムは、経路検索アプリ開発のために多額の資金調達に成功している<ref>{{cite web |title=Lola Gets $15 Million to Fund App Update |url=https://skift.com/2017/01/12/lola-gets-15-million-to-fund-app-update-travel-startup-funding-this-week/|date=2017-01-12}}</ref><ref>{{cite news |title=Hopper raises $100M more for its AI-based travel app, now valued at $780M |url=https://techcrunch.com/2018/10/03/hopper-raises-100m-more-for-its-ai-based-travel-app-now-valued-at-780m/}}</ref>。
モバイル端末向け経路検索アプリに予約・決済機能が加わると、結果として[[Mobility as a Service]]（MaaS）と見なされる。
| |||