JP2010012853A - 経路探索システム、経路探索サーバ、経路探索方法および端末装置 - Google Patents

Abstract

【課題】利用者が登録した経路の情報に基づいて、更新された時刻表データを用いて登録経路と大きな差のない新たな代替経路の情報を提供する。
【解決手段】時刻表データベース３６と、端末装置２０の利用者登録情報と登録経路情報とを記憶する利用者管理データベース３７と、登録経路情報から属性情報を抽出する属性情報抽出手段と３７２、属性情報に基づいて交通機関の経路区間の移動手段を抽出する移動手段抽出手段３７３と、更新された時刻表データに応じて移動手段抽出手段３７３が抽出した移動手段に基づいて代替経路を探索する代替経路探索手段３３と、を備え、時刻表データに更新があると、移動手段抽出手段３７３は、更新された時刻表データに基づいて、登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、代替経路探索手段３３は、移動手段抽出手段３７３が抽出した移動手段に基づいて代替経路を探索して端末装置に提供する。
【選択図】図２

Description

本発明は、鉄道などの交通機関を用いた経路区間を含む経路探索サーバと端末装置からなるシステムに関するものであり、特に、予め端末装置の利用者が所望の経路を経路探索サーバに登録し、経路探索サーバは登録された経路の情報から属性情報を抽出して記憶しておき、時刻表の変更（ダイヤ改正など）があった時に、登録された経路の属性情報に基づいて登録された経路に類似した移動手段を抽出し、更新された時刻表データに基づいて代替経路を探索して端末装置の利用者に代替経路の情報を提供するようにした経路探索システムに関するものである。

従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られており、このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、携帯電話をナビゲーション端末として利用して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。

特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムも存在する。また、徒歩経路の経路探索を伴わずに情報配信サーバから交通機関の路線や時刻表、乗車可能な列車などの情報の配信を受けて表示する交通案内システムも存在する。

一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。

情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。

交通機関を利用する経路を探索する経路探索システムは、利用者が指定する出発日時、出発地、目的地、到着時刻等の経路探索条件に基づいて、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、これに基づいて交通ネットワークをデータベース化したデータを備えている。そして、これらのデータベースを参照して、乗り継ぎ（乗換え）を含めて出発地と目的地を結ぶ利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、所要時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。

また、交通機関に関する検索、案内を行うシステムとして、携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる案内システムも提供されている。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報サイト）にアクセスして所望の情報をダウンロードする構成がとられている。

電車、列車あるいはバス等の交通機関の発車時刻等を知るために時刻表が存在するが、この時刻表は交通機関の発車時刻や到着時刻をまとめて製本したのみであり、日ごろから時刻表の製本を利用しないものにとっては大変使いにくいものとなっていた。そこで、近年ではこのような製本された時刻表に代わって、時刻表をデータとして保有し、所望の時刻表データを即座に表示できる電子時刻表が提案され、広く利用されている。その代表的なものとして上記のような検索システムや案内システムが提供されている。この電子時刻表を用いることにより、出発地、目的地及び出発時刻を入力するだけで目的地までの最短経路及びそれに要する運賃等を表示するものがあり、このような技術は特許文献にも多く紹介されている（例えば、特許文献２、３参照）。

下記の特許文献２（特開平９−３０５１０９号公報）に記載の電子時刻表システムは、記憶部に時刻表の各ページをイメージデータとして格納し、少なくとも駅と駅を結ぶ路線を含む地図情報を画面に表示し、表示された地図情報から路線名、乗車駅、降車駅、希望乗車時間又は希望降車時間を指定し、さらに指定された情報に基づき記憶部に格納された時刻表データを検索し、検索された時刻表データの該当ページを表示するものである。また、時刻表データの検索において、記憶部に、時刻表の各ページ毎に存在する複数の駅名と、当該ページにおいて最も早い時刻データとこの時刻データに対応する第１の駅名と、最も遅い時刻データとこの時刻データに対応する第２の駅名、に関する情報を保持しておき、利用者が指定した駅における各ページの推定掲載時刻を求め、求めた推定掲載時刻と利用者が指定した時刻データとに基づき、時刻表の該当ページを検索するようにしている。これにより、時刻表の検索をより迅速に行うことができるものである。

また、下記の特許文献３（特開２００１−１３４６３９号公報）には、出力する時刻表を指定するための指定データを入力すると、指定データに対応する時刻表データを出力すし、さらに時刻表データに更新日時が記憶されている場合においては更新後の時刻表データに変更して出力を行うようにした時刻表発行装置が開示されている。この時刻表発行装置は、通信装置によって他の時刻表発行装置から送信される時刻表の指定データを受信すると、当該指定データに対応する時刻表データを前記記憶媒体から読み出して、指定データの送信元の時刻表発行装置へ送信する。各時刻表発行装置は、受信した時刻表データをＲＡＭの時刻表データメモリに記憶し、出力指示にしたがって出力するように構成され、更新日時記憶手段に記憶されている更新日時を計時すると、出力対象とする時刻表データを、現行の時刻表データから更新後の時刻表データへ更新するようにされたものである。

特開２００１−１６５６８１号公報（図１、図２） 特開平９−３０５１０９号公報（段落［０００４］） 特開２００１−１３４６３９号公報（図２、図３）

しかしながら、上記特許文献２や特許文献３に開示されたシステムにおいては、路線名や駅名に基づいて電子時刻表のデータの検索が可能であるが、検索結果として表示される表示内容が１つに限定できる条件が入力されて初めて検索結果の表示がなされるようになっており、利用者が路線検索を行う際の柔軟性が十分とは言えない。また、利用者の利用する駅それぞれについて時刻表を入手するのは容易ではなく、また予め、時刻表検索システムのウェブサイトや利用駅の掲示などで時刻表の更新があることを知ることができたとしても、ダイヤの変更日や、時刻表に更新があることを忘れてしまい、実際に交通機関を利用した時に更新後のダイヤ電車が運行されていて所望の電車を適切に利用できないことがあった。

また、利用者が日常的によく利用する経路、例えば、通勤経路などは経路探索サーバによって最適経路を探索して得た案内経路の情報を登録しておき、経路確認の際には、登録した案内経路のデータを読み出して利用することができる。この場合、時刻表の更新に伴って、新たに経路探索して最適経路（代替経路）の情報を取得することが必要になる。しかしながら、更新された時刻表のデータを用いて代替経路を探索した場合、それまでの案内経路との相違が大きな経路が探索され、通勤経路の変更や運賃が大幅に異なってしまうという問題が生じることがある。

この原因は、ユーザが日常的に利用している通勤経路の選択においては、単純に最短で辿り着けること以外に、様々な要素により経路を選択しているためである。例えば、列車の混雑度であれば、急行であるか、準急であるか、各駅停車であるか、または行き先（終着点）がどこであるかで、または始発駅や始発駅からの距離によって変わる混雑度を知るための始発駅情報、増結車両があるか否かなどの情報を元に、ユーザはそれぞれの意向に合った路線を比較し選択しているのである。

このため、単に最適経路探索を行ってしまうと、これまで利用していた路線と類似した経路が得られるとは限らない。つまり、ユーザは時刻表の更新があった際には、時刻表を見ながら自らこれまで利用していた通勤経路に類似した代替経路を求めるか、または実際乗車してから調整して良い経路を探す必要があった。

上記特許文献３に開示された技術によれば、出力する時刻表を指定するための指定データを入力すると、指定データに対応する時刻表データを出力するものであり、時刻表データに更新日時が記憶されている場合には更新後の時刻表データに変更して出力する。しかしながら、上記の技術によれば予め時刻表の更新や新しい時刻表を知ることが出来ても、代替経路を知ることはできず、更新後の時刻表を見ながら自ら代替経路を求めることになってしまう。また、更新された時刻表のデータを用いて代替経路を探索した場合、それまでの案内経路との相違が大きな経路が探索され、通勤経路の変更や運賃が大幅に異なってしまうという問題が生じることがある。

本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、予め端末装置の利用者が所望の経路を経路探索サーバに登録し、経路探索サーバは登録された経路の情報から属性情報を抽出し、時刻表の変更（ダイヤ改正など）があった時に、属性情報を用いて更新された時刻表データに基づいて前記登録された経路における移動手段に類似した移動手段を抽出し、その移動手段を用いる代替経路を更新された時刻表のデータに基づいて探索して端末装置の利用者にその情報を提供するようになせば、上記の問題点を解消し得ることに想到して本発明を完成するに至ったものである。

すなわち、本発明は上記の問題点を解消することを課題とし、予め端末装置の利用者が登録した経路の情報に基づいて、端末装置の利用者に、更新された時刻表データに基づいて、登録経路と大きな差のない新たな代替経路の情報を提供するようにした経路探索システムを提供することを目的とするものである。

前記課題を解決するために、本願の請求項１にかかる発明は、
時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供することを特徴とする経路探索システムである。

また、本願の請求項２にかかる発明は、請求項１にかかる経路探索システムにおいて、前記端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含むことを特徴とする。

また、本願の請求項３にかかる発明は、請求項１にかかる経路探索システムにおいて、前記経路探索システムは、代替経路選択手段を備え、代替経路選択手段は、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別し、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択し、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする。

また、本願の請求項４にかかる発明は、請求項３にかかる経路探索システムにおいて、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数あるか否かを判別し、少なくとも１つまたは所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択し、代替経路が少なくとも１つまたは所定数に満たない場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする。

また、本願の請求項５にかかる発明は、請求項３にかかる経路探索システムにおいて、前記利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合、前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択し、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が代替経路を探索することを特徴とする。

本願の請求項６にかかる発明は、
時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供することを特徴とする経路探索サーバである。

また、本願の請求項７にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含むことを特徴とする。

また、本願の請求項８にかかる発明は、請求項６にかかる経路探索サーバにおいて、前記経路探索サーバは、代替経路選択手段を備え、代替経路選択手段は、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別し、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択し、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする。

また、本願の請求項９にかかる発明は、請求項８にかかる経路探索サーバにおいて、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数あるか否かを判別し、少なくとも１つまたは所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択し、代替経路が少なくとも１つまたは所定数に満たない場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする。

また、本願の請求項１０にかかる発明は、請求項８にかかる経路探索サーバにおいて、前記利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合、前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択し、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が前記代替経路を探索することを特徴とする。

本願の請求項１１にかかる発明は、
時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段が、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出するステップと、前記代替経路探索手段が、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索するステップと、前記代替経路を前記端末装置に提供するステップと、を有することを特徴とする経路探索システムにおける経路探索方法である。

また、本願の請求項１２にかかる発明は、請求項１１にかかる経路探索方法において、前記端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含むことを特徴とする。

また、本願の請求項１３にかかる発明は、請求項１１にかかる経路探索方法において、前記経路探索システムは、代替経路選択手段を備え、代替経路選択手段が、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別するステップと、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択するステップと、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とするステップと、を有することを特徴とする。

また、本願の請求項１４にかかる発明は、請求項１３にかかる経路探索方法において、前記代替経路選択手段が、代替経路候補が少なくとも１つまたは所定数あるか否かを判別するステップと、少なくとも１つまたは所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択するステップと、代替経路が少なくとも１つまたは所定数に満たない場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とするステップと、を有することを特徴とする。

また、本願の請求項１５にかかる発明は、請求項１３にかかる経路探索方法において、前記利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段が、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合に前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択するステップと、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が前記代替経路を探索することを特徴とする。

本願の請求項１６にかかる発明は、
時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供する経路探索サーバに接続される端末装置であって、
前記端末装置は、利用者登録情報と所望の出発地から目的地までの登録経路情報とを前記経路探索サーバに登録するための利用者・経路登録手段を含む操作入力手段を備えたことを特徴とする

また、本願の請求項１７にかかる発明は、請求項１６にかかる端末装置において、前記端末装置に提供される代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含み、前記端末装置は、前記代替経路の情報を受信する通信手段を有することを特徴とする。

また、本願の請求項１８にかかる発明は、請求項１６にかかる端末装置において、前記利用者・経路登録手段は、前記属性情報に含まれる情報に優先度を設定し、前記経路探索サーバに登録可能になしたことを特徴とする。

請求項１にかかる発明においては、経路探索システムは、時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供する。

このような構成によれば、時刻表の更新があった際に、端末装置の利用者に、更新された時刻表データと、予め端末装置の利用者が登録した経路の情報に基づいて、登録経路と大きな差のない新たな代替経路の情報を提供することができるようになる。これにより、利用者は自分が利用登録していた経路について、類似した条件の代替経路を知ることができ、わざわざ１つ１つ属性情報を照らし合わせて、自分で経路を確認したり算出したりする必要がなくなる。

また、請求項２にかかる発明においては、請求項１にかかる経路探索システムにおいて、端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含む。

このような構成によれば、利用者は自分が利用登録していた経路について、類似した条件の代替経路を知ることができ、わざわざ１つ１つ属性情報を照らし合わせて、自分で経路を確認したり算出したりする必要がなくなる。また、代替経路について、時刻表更新前との時刻差が把握できるため、乗り遅れや乗り間違いを防ぐことが可能になる。

また、請求項３にかかる発明においては、請求項１にかかる経路探索システムにおいて、経路探索システムは、代替経路選択手段を備え、代替経路選択手段は、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別し、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択し、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とする。

このような構成によれば、予め登録した経路の到着時刻や出発時刻に対して所定の時間幅の範囲内に入る代替経路を知ることができるようになり、登録経路の時刻条件に合致する代替経路の情報を得ることができるようになる。

また、請求項４にかかる発明においては、請求項３にかかる経路探索システムにおいて、代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数あるか否かを判別し、少なくとも１つまたは所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択し、代替経路が少なくとも１つまたは所定数に満たない場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とする。

このような構成によれば、利用者は自分が利用登録していた経路について、類似した条件の代替経路を知ることができ、また、類似した代替経路が探索できなかった場合には、登録経路の出発地から目的地までの最適経路探索の結果が代替経路として端末装置に提供されるようになる。

また、請求項５にかかる発明においては、請求項３にかかる経路探索システムにおいて、利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合、前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択し、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が前記代替経路を探索する。

このような構成によれば、時刻表の更新があった際に、端末装置の利用者に、更新された時刻表データと、予め端末装置の利用者が登録した経路の情報に基づいて、登録経路と大きな差のない新たな代替経路の情報を提供することができるようになり、更に、経路の属性情報に優先度を設定することで、登録経路との差異が小さい代替経路が得られない場合でも、条件を緩和して代替経路を探索させることができるようになる。

また、請求項６ないし請求項１０にかかる発明においては、それぞれ請求項１ないし請求項５にかかる経路探索システムを構成する経路探索サーバを提供することができるようになり、請求項１１ないし請求項１５にかかる発明においては、それぞれ請求項１ないし請求項５にかかる経路探索システムにおける経路探索方法を提供することができるようになる。また、請求項１６ないし請求項１８にかかる発明においては、それぞれ請求項１、請求項２、請求項５にかかる経路探索システムを構成する端末装置を提供することができるようになる。

以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するための経路探索システムを例示するものであって、本発明をこの経路探索システムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態の経路探索システムにも等しく適用し得るものである。なお、本発明は、ナビゲーション機能を有する経路探索システムに限らず、時刻表検索システムや路線検索システムであってもよい。本明細書においてはこれらを総称して経路探索システムといい、端末装置に情報を提供するサーバを経路探索サーバという。

図１は、本発明の実施例にかかる経路探索システムの構成を示すシステム構成図である。本発明の実施例にかかる経路探索システム１０は、図１に示すように、携帯電話やＰＤＡ、ミュージックプレーヤーなどの携帯型端末を用いた端末装置２０と経路探索サーバ３０とがインターネットなどのネットワーク１２を介して接続される構成になっている。経路探索サーバ３０は、経路探索のための道路ネットワークのデータおよび時刻表データに基づく交通ネットワークのデータを含む探索ネットワークデータを蓄積したデータベース（ＤＢ１）、利用者が登録する各種登録データを蓄積したデータベース（ＤＢ２）、交通機関の各電車等の運行ダイヤに基づく時刻表や運賃を蓄積した時刻表データベース（ＤＢ３）、表示用の地図データなどを蓄積したデータベース（ＤＢ４）を備えている。時刻表や運賃のデータは、ネットワーク１２を介して情報配信サーバ５０から取得することができる。

本発明にかかる経路探索システム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、ＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器を用いることもできる。また、端末装置２０は携帯機器に限られるものではなく、パーソナルコンピュータなどの端末機器であってもよい。

図２は、図１に示す経路探索システム１０の詳細な構成を示すブロック図である。本発明の実施例１にかかる経路探索システム１０は、図２のブロック図に示すようにインターネットなどのネットワーク１２を介して通信する端末装置２０と、経路探索サーバ３０とから構成されている。

端末装置２０は、経路探索サーバ３０に出発地と目的地などの経路探索条件を設定して経路探索要求を送信し、経路探索サーバ３０は、経路探索条件に従って、探索ネットワークデータ（ＤＢ）に蓄積された道路ネットワークデータ、交通ネットワークデータを参照して最適経路を探索し、その最適経路を案内経路データに編集して端末装置２０に配信する。

端末装置２０は、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、処理要求手段２３、経路探索サーバ３０から受信した案内経路のデータを記憶する配信データ記憶手段２４、表示手段２５、操作入力手段２６、表示制御手段２７などを備えて構成されている。

制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。ＧＰＳ受信手段２２はＧＰＳ衛星信号を受信して現在位置および現在時刻を算出する。

処理要求手段２３は、操作入力手段２６により設定された経路探索条件に基づいて、経路探索サーバ３０に処理要求を送信し、経路探索サーバ３０がこの処理要求に基づいて処理した結果、端末装置２０に送信される各種のデータは、配信データ記憶手段２４に記憶され、表示制御手段２７の制御下で表示手段２５に表示される。

端末装置２０の利用者は、経路探索サーバ３０に利用者登録をした上で、所望の経路、例えば、日常よく利用する特定の目的地までの経路や通勤経路など、経路探索サーバ３０から配信された経路情報を登録しておき、登録した経路における交通機関を用いる経路区間について時刻表に更新があった際に、登録した経路と大きく差が生じない代替経路の情報の配信を受けることができる。

利用者登録や経路情報の登録のため、操作入力手段２６は利用者・経路登録手段２６１を含んで構成される。利用者登録・条件設定手段２６１は、具体的には文字入力キー、表示手段２５に表示されたメニュー画面の設定項目などを選択するカーソルキーなどで構成される。

端末装置のＩＤや利用者のＩＤ、パスワード、経路探索サーバ３０からの通知先のメールアドレス等の情報は経路探索サーバ３０に送信され、利用者管理情報を蓄積するデータ利用者管理データベース３７に記憶される。経路探索サーバ３０に所望の経路情報、例えば、通勤経路の情報を登録する場合、端末装置２０の利用者は、利用者・経路登録手段２６１を用いて、端末装置２０に保存してある経路情報から該当する経路の情報を選択して経路探索サーバ３０に登録する。経路登録の具体例については後述する。

経路探索サーバ３０は、端末装置２０から利用者登録の情報や登録経路の情報を受信すると、利用者管理データベース（ＤＢ）３７に蓄積される。利用者登録情報は、利用者ＩＤ、端末装置ＩＤやパスワード等である。また、登録経路の情報は、出発地、出発駅、出発時刻、目的地、目的駅、到着時刻、乗車すべき電車、列車などの移動手段の時刻、利用路線、利用区間、乗換有無、徒歩の所要時間などの情報である。これらの情報は、過去に経路探索サーバ３０に経路探索要求をして受信した案内経路の情報である。

一方、経路探索サーバ３０は、制御手段３０１、通信手段３１、配信データ編集手段３２、代替経路探索手段３３、地図データベース（ＤＢ）３４、探索ネットワークデータベース（ＤＢ）３５、時刻表データベース（ＤＢ）３６、利用者管理データベース（ＤＢ）３７、処理要求記憶手段３８、経路探索手段３９などを備えて構成されている。

経路探索サーバ３０は、端末装置２０から経路探索やＰＯＩ（興味対象場所：Ｐｏｉｎｔ ｏｆ Ｉｎｔｅｒｅｓｔ）検索あるいは地図配信の要求があると、処理要求記憶手段３８にその要求を一次記憶する。要求が経路探索要求である場合、経路探索手段３９は探索ネットワークデータベース３５を参照して最適経路あるいは推奨経路（案内経路）を探索する。探索された案内経路のデータは配信データ編集手段３２により端末装置２０に対する配信データに編集され、端末装置２０に配信される。また、地図データベース３４から案内経路を含む地図データが読み出され、端末装置２０に配信される。

時刻表データベース３６には、駅時刻表や運行時刻表などのデータが記憶されている。これらの時刻表は、各交通機関の路線ごとの各駅における移動手段（個々の電車や列車）の進行方向ごとの到着時刻または出発時刻の一方または両方を含む時刻、行き先、移動手段の種別（特急、普通の別など）からなる。ダイヤ改正などにより時刻表データに更新があると、時刻表データベースに記憶された時刻表データも更新される。

利用者管理データベース３７には、端末装置２０から送信された利用者登録情報、登録経路の情報が利用者管理情報として登録利用者ごとに記憶される。経路探索サーバ３０は、端末装置２０から経路の登録があると、その属性情報を抽出した登録経路の情報に対応させて利用者管理データベース３７に記憶する。登録経路の属性情報とは、行き先、始発駅情報、増結・切り離しがあるか否か、車両数、特急・準急・各駅停車など、案内経路において利用者に対して案内された乗車すべき個々の移動手段（電車）の情報である。

経路探索サーバ３０は、時刻表の変更（ダイヤ改正など）があった時に、利用者管理データベース３７を参照して、登録された経路情報ごとに更新の有無を判別し、時刻表の更新がある場合、更新された時刻表に基づいて、登録経路の情報およびその属性情報から、登録経路における移動手段（乗車すべき電車等）を抽出する。抽出する移動手段の範囲は、登録経路における移動手段に対して所定の条件範囲内にある類似度の高い移動手段である。

例えば、登録経路が通勤経路である場合、出発駅における出発時刻や急行、普通の種別、乗換え有無、行き先、始発駅、増結の有無など、登録経路において案内された電車と条件の近い、大きな差のない電車（更新された時刻表における電車）を抽出し、その電車を用いた代替経路を探索する。そのような代替経路が探索され、目的地到着時刻が所定の時刻の範囲内であれば、端末装置２０に代替経路を案内する。

このような処理を行うため、経路探索サーバ３０は、登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段３７１と、登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段３７２と、前記属性情報に基づいて前記登録経路における交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段３７３と、前記移動手段抽出手段が抽出した移動手段と更新された時刻表データに基づいて、前記登録経路に対する代替経路を探索する代替経路探索手段３３と、代替経路の時刻条件が登録経路の時刻条件を満足するかを判別する代替経路選択手段３７４と、を備えている。

代替経路選択手段３７４は登録経路の時刻条件を満足する代替経路を端末装置２０に送信する。代替経路の情報は利用者が登録した通知先の情報、例えば、電子メールアドレスに送信される。端末装置２０の利用者は、所望の経路情報を経路探索サーバ３０に登録しておくだけで、登録経路に関する時刻表データに更新があった場合に登録経路と大きな差のない代替経路の情報を経路探索サーバ３０から取得することができるようになる。

以下、図３、図４を用いて登録経路に対する代替経路の探索の概念を説明する。図３は、登録経路の一例を示す図であり、図４は、図３の登録経路に対する時刻表更新に基づく代替経路の概念を示す模式図である。ある利用者が経路探索サーバ３０に登録した経路情報は、図３に示すように出発地Ｓから目的地Ｇまでの徒歩経路区間と交通機関を利用した経路区間からなるものである。

この登録経路は、出発地Ｓから８分間徒歩経路を移動し、出発地Ｓの最寄りのＡ駅ＳＴ１で、路線ＸＸ線の９時発の各駅停車の電車に乗車してＢ駅ＳＴ２で降車し、さらにＢ駅ＳＴ２で乗り換えを行い、路線ＹＹ線の９時１５分発の快速電車に乗車してＣ駅ＳＴ３（目的地Ｇの最寄り駅）に着くと、更にＣ駅ＳＴ３から１０分間、徒歩で目的地Ｇへ徒歩経路を移動し、９時５５分に目的地Ｇに到着するような経路である。

属性情報抽出手段３７２はこのような登録情報から、時刻表データベース３６を参照して経路の属性情報、すなわち、移動手段である乗車すべき電車の情報、例えば、車両編成や始発駅、増結の有無、増結／切り離しが行われる駅、行き先などの属性情報を抽出して登録経路に対応付けて利用者管理データベース３７に記憶する。

この経路が影響を受ける時刻表の更新があると、移動手段抽出手段３７３は、更新された時刻表データに基づいて、代替経路探索のベースになる登録経路に属性情報に類似した移動手段（電車）を抽出する。類似した移動手段とは、登録経路における移動手段（電車）の時刻等とその属性情報（車両編成）などが所定の条件範囲内にある移動手段（電車）である。

そして代替経路探索手段３３は、更新された時刻表データに基づいて、移動手段抽出手段３７３が抽出した移動手段（電車）を用いた出発地Ｓから目的地Ｇまでの代替経路を探索する。図４は、このような代替経路の探索の様子を示している。すなわち、図４に示すように、登録経路において、Ａ駅ＳＴ１を９：００に出発する各駅停車に近い発車時刻の電車は、更新された時刻表においては８：５５、９：０１、９：０７の３本であることが分かるので、これらの電車を移動手段抽出手段３７３が抽出する。この抽出の範囲は、例えば、所定の時間範囲内である電車情報としても良いし、登録経路における出発時刻９：００に近いものから前後何本というように設定しておいてもよい。

さらに、路線の乗換えなど、次の乗車区間が有る場合には、Ｂ駅ＳＴ２で乗り換えてＹＹ線Ｂ駅〜Ｃ駅区間での乗車についても同様に移動手段である電車の抽出を行う。図４に示すように、登録経路における９：１５発の快速電車に近い発車時刻の電車は更新された時刻表においては、８：５４、９：１３、９：３２の３本であることが分かる。移動手段抽出手段は、前述と同様にこれらの電車を抽出する。

移動手段（電車）が抽出されると、代替経路探索手段３３は、Ｂ駅ＳＴ２での乗換え所要時間などを考慮して代替経路候補を探索し、その所要時間を算出する。代替経路候補から予測される目的地到着予想時刻は、それぞれ９：３４、９：５３、１０：０２であることが分かるため、ここから更新前の時刻表における経路の目的地到着時刻との時刻差は、それぞれ−２１分、−２分、＋７分である。このような代替経路の候補を端末装置２０に通知すれば、利用者は登録経路に類似した更新された時刻表による代替経路を知ることができ、目的地に所望の時刻に到着できる代替経路を選択することができるようになる。

なお、利用者が登録した登録経路探索時の時刻条件、例えば、経路探索の際の目的地到着時刻と代替経路の到着予想時刻とを代替経路選択手段３７４で比較し、目的地到着時刻までに到着できる代替経路の候補を識別して端末装置２０に通知するようにしてもよいし、時刻差が所定の範囲内であるという条件を設定してもよい。このような設定をすると、図４に示す例では、目的地Ｇに１０：００以前に到着する経路としては、到着予想時刻が９：３４、９：５３である経路が代替経路の候補として選択され、時刻表更新前の到着時刻と比較してその差が１０分以内であるものという設定をすると、到着予想時刻が９：５３、１０：０２である経路が代替経路の候補として選択されることになる。

また、代替経路選択手段３７４は、出発時刻の推奨時刻を所定の時刻と比較して代替経路を選択するようにしても良い。この場合、代替経路選択手段３７４は予め登録しておいた出発時刻または出発希望時刻と、代替経路の出発時刻を比較し、出発時刻の早すぎるもの、遅すぎるもの、出発時刻の時刻差の有りすぎるものを代替経路の候補として選ばないようにすればよい。

さらに、代替経路探索手段３３は、代替経路選択手段３７４が代替経路の候補経路として選択した経路数が、少なくとも１つ、或いは所定の数であるか否か判定し、設定した条件を満足する代替経路の候補が得られない場合には、出発地及び目的地、または利用駅と時刻条件に従って更新された時刻表データに基づく最適経路探索を行って代替経路候補として端末装置２０に提供してもよい。

上記のような最適経路探索を行う前に、代替経路選択手段３７４は属性情報のうち優先度の低いものを削除したり、優先度の高いものだけを選択するなどして、代替経路探索手段３３に代替経路候補の再探索を行わせるようにしてもよい。属性情報は、先に説明したように、行き先、始発駅情報、増結・切り離しがあるか否か、車両数、特急・準急・各駅停車など、複数の情報を含む。利用者はこれらの属性情報に優先度を設定して経路探索サーバ３０に登録することができる。例えば、各駅停車を優先するように設定して経路探索サーバ３０に登録すれば、代替経路の探索において、各駅停車の属性情報を持つ経路が探索され、有料の特急電車は代替経路探索の対象から除外される。

経路探索サーバ３０は、以上のようにして求めた代替経路の情報を端末装置２０に送信する。例えば利用者が登録した通知方法が電子メールであった場合には、利用者管理データベース３７に記憶された通知先メールアドレスに、これらの情報を配信する。

この時、代替経路情報としては、代替経路のほかに、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と到着予想時刻との時刻差などの情報を含むようにしても良い。

以上のように、時刻表の更新が実施された際に、端末装置２０の利用者は自分が利用登録していた経路について、類似した条件の代替経路を知ることが可能になる。これによって、わざわざ１つ１つ属性情報を照らし合わせて、自分で経路を確認したり算出したりする必要がなくなる。また、代替経路について、時刻表更新前との時刻差が把握できるため、乗り遅れや乗り間違いを防ぐことが可能になる。

図５は、端末装置２０において経路探索サーバ３０に図３に示すような所望の経路情報を登録するための登録画面の一例を示す図である。図５の登録画面は、操作入力手段２６において時刻表更新の通知設定を選択すると表示手段２５に表示されるメニュー画面であり、図示しない利用者登録メニュー画面などとともに利用者・経路登録手段を構成する。

端末装置２０の利用者は、所望の経路を経路探索サーバ３０に登録する際は、図５に示す登録画面を表示画面３００に表示し、登録したい経路の交通機関を利用した経路区間の路線・駅名または乗車区間を選択して経路探索サーバ３０に送信して登録する。経路の登録方法はこれに限らず、種々の方法で行うことができる。

例えば、個々の路線・乗車区間・属性情報等を指定して登録してもよいし、出発地から目的地までの最適経路探索を行い、時刻表データベース３６を参照して最適経路に含まれる路線情報を登録するようにしてもよい。また、過去の経路探索結果から登録できるようにしてもよい。更に、属性情報に含まれる複数の情報に優先度を設定して、登録経路に類似した代替経路を得られるようにしてもよい。

図６は、経路探索サーバ３０から端末装置２０に通知（送信）された時刻表更新および代替経路の通知メールの表示画面３１０の一例を示す図である。図６に示すように、電子メールにて時刻表更新による代替経路情報を配信する場合、時刻表の更新のあった旨、代替路線情報、到着予想時刻、時刻表更新前の到着時刻との差などを含んだ情報を配信し、表示させるようにする。

また、利用経路の乗換え情報を表示するほか、代替経路の候補経路を複数表示しても良いし、該当する代替経路の候補経路がない場合には、最適経路の探索結果を代替経路として表示しても良い。さらに、詳細な乗換え情報を示すページや、時刻表表示ページなどウェブブラウザを介して表示するためのリンク情報を付加しても良い。

次に、経路探索サーバ３０における経路探索の処理について説明する。経路探索のための探索ネットワークデータ３５には、徒歩や自動車による移動経路を探索するための道路ネットワークデータと公共交通機関を利用した移動経路を探索するための交通ネットワークデータが蓄積されている。経路探索手段３９は、この経路探索用ネットワークデータを参照して、徒歩や自動車による経路あるいは徒歩と交通機関を併用した経路を探索する。

道路ネットワークデータは、以下のように構成されている。例えば、道路が、図７に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。

すなわち、図７において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図７では図示を簡略化するため矢印の向きのリンクのみを図示している。

このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図７において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。

図７ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。

これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。例えば、図８に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図１３において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図１３では図示を簡略化するため矢印の向きのリンクのみを図示している。

しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図８に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。

図８に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。

このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。

例えば、図８において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。

このようなネットワークデータを利用して経路探索サーバ３０は経路探索条件に従って、出発地から目的地までの複数の候補経路を探索し、その結果を案内経路データとして端末装置２０に送信する。経路探索条件に出発地の出発時刻が指定されている場合には目的地への到着時刻が、また、目的地への到着時刻が指定されている場合には、目的地に指定時刻に到着するための出発地の出発時刻が案内経路データに含まれ、端末装置２０はこれらを表示手段２５に経路の詳細とともに表示することができる。案内経路に乗換え駅が含まれる場合には、当該乗換え駅で乗換えるべき電車やその出発時刻も同様にして表示することができる。

移動の手段として徒歩と交通機関を用いる場合の経路探索においては、道路ネットワークデータと交通ネットワークデータとを結合して総合的なネットワークデータを編集し経路探索を行う。徒歩経路区間は道路ネットワークデータが参照され、交通機関を用いる経路区間は交通ネットワークデータが参照される。最適経路の探索においては、トータルで経路コストが最小となる経路が探索される。この場合、徒歩経路区間が最小にならない経路が探索されることもある。

徒歩経路区間が最も小さい経路を要求する場合には、徒歩経路区間を最短とする条件を設定する。また、乗換え回数が最小になる経路探索を要求する場合は、乗換え回数を最小とする条件を設定する。更に、交通機関を利用した経路区間の運賃が最小になる条件を設定することもできる。これらの条件設定は、交通機関を用いた経路探索においては一般的なものである。

次に、本発明の実施例にかかる経路探索システム１０の動作手順について詳細に説明する。図９は、経路探索サーバ３０における経路登録の処理手順を示すフローチャートである。先ず経路探索サーバ３０はステップＳ１０１の処理で端末装置２０から登録経路の情報を取得する。この情報は、利用者管理データベース３７の登録利用者のデータに対応付けて記憶される。登録利用者のデータとは先に述べたように、利用者ＩＤ、端末ＩＤ、パスワード、通知先のメールアドレスなどの通知先情報である。また、登録経路の情報とは、出発地、駅、時刻、目的地、駅、時刻、移動手段／の時刻、利用路線、利用区間、乗換有無、徒歩の所要時間などである。

次に、経路探索サーバ３０はステップＳ１０２の処理で、登録された経路の情報から該当する交通機関の路線や利用区間に基づいて、時刻表データベース３６から該当する時刻表のデータを取得する。そして、ステップＳ１０３の処理で属性情報抽出手段３７２は、登録された経路の情報から移動手段（電車）の属性情報を抽出する。属性情報とは、先に述べたように登録経路における移動手段である電車の情報、例えば、行き先、始発駅情報、増結・切り離しがあるか否か、車両数、特急・準急・各駅停車などである。

ステップＳ１０３の処理で抽出された属性情報は、ステップＳ１０４の処理において利用者管理データ３７の登録利用者のデータ、登録経路の情報に対応付けて記憶される。なお、属性情報の抽出と記憶は、経路登録時に行うことが好ましいが、時刻表の更新に伴う代替経路の探索にあたり、更新前の時刻表データを用いて属性情報を抽出する処理を行うこともできる。

図１０は、経路探索サーバ３０における代替経路の探索、時刻表更新の通知処理の手順を示すフローチャートである。時刻表の更新があると、先ず、経路探索サーバ３０は、ステップＳ２０１の処理で利用者管理データベース３７を参照して更新された時刻表に関連する登録経路の情報を取得し、次いで、ステップＳ２０２の処理で、登録経路に対応する属性情報を取得する。

次に経路探索サーバ３０は、ステップＳ２０３の処理で、時刻表データベース３６を参照して、更新された時刻表のデータを取得する。ステップＳ２０４の処理では、移動手段抽出手段３７３は、更新された時刻表データに基づいて、代替経路探索のベースになる登録経路の属性情報に類似した移動手段（電車）、例えば、登録経路における出発時刻に対して所定の時刻の範囲内に出発する移動手段（電車）があるか、否かを判別する。

該当する移動手段がない場合はステップＳ２１４の処理で代替経路探索手段３３は登録経路の出発地や目的地、時刻条件などの経路探索条件で経路探索手段３９に更新された時刻表に基づく最適経路を探索させ、代替経路とする。この場合の代替経路は、登録経路と類似した移動手段がないのであるから、登録経路とは差異の大きい代替経路になる可能性がある。

一方、該当する移動手段（電車）がある場合は、移動手段抽出手段３７３は、ステップＳ２０５の処理で、更新された時刻表に基づく所定の出発時刻範囲の移動手段（電車）の情報を抽出する。次いで、ステップＳ２０６に進み、抽出された移動手段が登録経路における属性情報、例えば、行き先、始発駅情報、増結・切り離しがあるか否か、車両数、特急・準急・各駅停車などと類似した属性情報であるか判別する。これらの属性情報の判別は、利用者が設定した優先度に基づき、特定の属性情報の類似度を判別するようにできる。例えば、登録経路が通勤経路である場合、有料の特急電車を選択しないようにするなどの判別である。

類似の属性情報でない場合はステップＳ２１４の処理に進み最適経路の探索を行う。類似の属性情報の移動手段（電車）である場合は、ステップＳ２０７の処理で経路に路線の乗換えがあり、乗換えが可能な電車があるかを判別する。乗換えが可能である電車がある場合は、ステップＳ２０４の処理に戻り、乗換え先の路線について前述と同様の処理を行う。

乗換え路線がなくなれば、ステップＳ２０８の処理に進み、代替経路探索手段３３は、移動手段抽出手段３７３が抽出した移動手段（電車）をベースに代替経路を特定（探索）し、代替経路の所要時間を算出してステップＳ２０９の処理に進む。ここで特定される代替経路は、抽出された移動手段の数に応じた数だけ求められ、代替経路の候補である。ステップＳ２０９の処理では代替経路選択手段３７４は、登録経路における時刻条件を満足するか否かを判別する。時刻条件を満足するとは、例えば、目的地または目的地の最寄り駅への到着時刻が所定の時刻範囲であるか否かである。

求められた代替経路が時刻条件を満足しない場合はステップＳ２１１の処理に進み最適経路の探索を行う。時刻条件を満足する代替経路がある場合は、ステップＳ２１０の処理で代替経路選択手段３７４は特定された代替経路が所定数あるか否かを判別する。時刻条件を満足しない場合は、ステップＳ２１１の処理に進み、少なくとも１つは代替経路があったか否かを判別する。１つも代替経路がなかった場合は、ステップＳ２１４の処理に進み最適経路の探索を行う。少なくとも１つの代替経路があった場合はステップＳ２１２の処理に進む。

少なくとも１つの代替経路があった場合、および、ステップＳ２１０の判別処理で所定数の代替経路がある場合、ステップＳ２１２の処理で経路探索サーバ３０は、利用者管理データベース３７を参照して登録利用者の通知先情報（例えば、メールアドレス）を取得する。次いで、ステップＳ２１３の処理に進み、代替経路選択手段３７４は、時刻表の更新通知と代替経路の情報を通知先のメールアドレスに送信する。また、ステップＳ２１０の判別処理において、代替経路が所定数に満たない場合にはステップＳ２０４の処理に戻る。

なお、代替経路数が所定数に満たないあるいは１つも代替経路が得られない場合には、類似の属性を変更して（例えば、属性情報に優先順位が付与されていた場合には、優先順位の低いものを除外する）再度代替経路を算出するようにしても良い。

このようにして通知された更新時刻表に基づく代替経路は、登録経路における電車の出発駅の出発時刻と所定の時刻範囲内の電車をベースに、電車の属性情報が類似するものであるから、登録経路と大きな差異のない経路になる可能性が極めて高く、例えば、登録経路が通勤経路である場合、時刻表が更新された場合の出発地（自宅）を出発する時間を容易に調整することができ、また、定期券の買い換えの必要性の有無などを判断することもできるようになる。

以上、詳細に説明したように、本発明の経路探索システムによれば、予め端末装置の利用者が登録した案内経路の情報と、更新された時刻表データに基づいて、登録経路と大きな差のない新たな代替経路の情報を提供することができるようになる。

本発明は、ナビゲーション機能を有する経路探索システムの他、交通機関の時刻表データや路線情報データを備えた時刻表の検索システムや路線検索システムなどにも適用することができる。

本発明の実施例にかかる経路探索システムの構成を示すシステム構成図である。 図１に示す経路探索システムの詳細な構成を示すブロック図である。 経路探索サーバに登録された登録経路の一例を示す模式図である。 図３に示す登録経路に対する時刻表更新に基づく代替経路の例を示す模式図である。 端末装置において所望の経路情報を登録する際の登録画面の一例を示す図である。 端末装置に送信された代替経路の情報を表示する表示画面の一例を示す図である。 探索用ネットワークデータに含まれる道路ネットワークのデータの概念を示す模式図である。 探索用ネットワークデータに含まれる交通ネットワークのデータの概念を示す模式図である。 本発明の実施例にかかる経路探索システムにおける経路登録の処理手順を示すフローチャートである。 本発明の実施例にかかる経路探索システムにおける時刻表更時の代替経路探索および通知の動作手順を示すフローチャートである。

符号の説明

１０・・・・経路探索システム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・処理要求手段
２４・・・・配信データ記憶手段
２５・・・・表示手段
２６・・・・操作入力手段
２６１・・・利用者・経路登録手段
２７・・・・表示制御手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・配信データ編集手段
３３・・・・代替経路探索手段
３４・・・・地図データベース（ＤＢ）
３５・・・・探索ネットワークデータ（ＤＢ）
３６・・・・時刻表データ（ＤＢ）
３７・・・・利用者管理データ（ＤＢ）
３７１・・・時刻表更新有無判別手段
３７２・・・属性情報抽出手段
３７３・・・移動手段抽出手段
３７４・・・代替経路選択手段
３８・・・・処理要求手段
３９・・・・経路探索手段

Claims (18)

1. 時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
   前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供することを特徴とする経路探索システム。
2. 前記端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含むことを特徴とする請求項１に記載の経路探索システム。
3. 前記経路探索システムは、代替経路選択手段を備え、代替経路選択手段は、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別し、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択し、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする請求項１に記載の経路探索システム。
4. 前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数あるか否かを判別し、少なくとも１つまたは所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択し、代替経路が少なくとも１つまたは所定数に満たない場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする請求項３に記載の経路探索システム。
5. 前記利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合、前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択し、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が代替経路を探索することを特徴とする請求項３に記載の経路探索システム。
6. 時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
   前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供することを特徴とする経路探索サーバ。
7. 前記端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含むことを特徴とする請求項６に記載の経路探索サーバ。
8. 前記経路探索サーバは、代替経路選択手段を備え、代替経路選択手段は、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別し、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択し、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする請求項６に記載の経路探索サーバ。
9. 前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数あるか否かを判別し、少なくとも１つまたは所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択し、代替経路が少なくとも１つまたは所定数に満たない場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とすることを特徴とする請求項８に記載の経路探索サーバ。
10. 前記利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段は、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合、前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択し、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が前記代替経路を探索することを特徴とする請求項８に記載の経路探索サーバ。
11. 時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて、前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
    前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段が、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出するステップと、前記代替経路探索手段が、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索するステップと、前記代替経路を前記端末装置に提供するステップと、を有することを特徴とする経路探索システムにおける経路探索方法。
12. 前記端末装置に提供する代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含むことを特徴とする請求項１１に記載の経路探索方法。
13. 前記経路探索システムは、代替経路選択手段を備え、代替経路選択手段が、前記代替経路探索手段が探索した代替経路が所定の時刻条件を満足するか否かを判別するステップと、前記時刻条件を満足する代替経路を、前記端末装置に提供する経路として選択するステップと、前記時刻条件を満足する代替経路が得られなかった場合には、前記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とするステップと、を有することを特徴とする請求項１１に記載の経路探索方法。
14. 前記代替経路選択手段が、代替経路候補が少なくとも１つまたは所定数あるか否かを判別するステップと、少なくとも１つまたは所定数所定数有る場合にはその代替経路を端末装置に提供する代替経路として選択するステップと、代替経路が少なくとも１つまたは所定数に満たない場合には、記更新された時刻表データを用いて前記出発地から目的地までの最適経路を探索して代替経路とするステップと、を有することを特徴とする請求項１３に記載の経路探索方法。
15. 前記利用者管理データベースに利用者が登録した属性情報に含まれる情報の優先度が登録されている場合、前記代替経路選択手段が、代替経路候補が少なくとも１つまたは所定数の前記代替経路が得られなかった場合に前記登録された属性情報の優先度に応じて属性情報に含まれる情報を選択するステップと、前記選択された属性情報に応じて前記移動手段抽出手段が移動手段を抽出し、前記代替経路探索手段が前記代替経路を探索することを特徴とする請求項１３に記載の経路探索方法。
16. 時刻表データを蓄積する時刻表データベースと、端末装置の利用者登録情報と所望の出発地から目的地までの登録経路情報とを記憶する利用者管理データベースと、前記登録経路に関する時刻表データの更新の有無を判別する時刻表更新有無判別手段と、前記登録経路情報から交通機関を用いた経路区間の属性情報を抽出する属性情報抽出手段と、前記属性情報に基づいて交通機関を用いた経路区間の移動手段を抽出する移動手段抽出手段と、更新された時刻表データに応じて前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索する代替経路探索手段と、を備え、
    前記時刻表更新有無判別手段が時刻表データに更新があると判別した場合、前記移動手段抽出手段は、更新された時刻表データに基づいて、前記登録経路における移動手段に対して所定の条件範囲内にある移動手段を抽出し、前記代替経路探索手段は、前記移動手段抽出手段が抽出した移動手段に基づいて前記登録経路に対する代替経路を探索して前記端末装置に提供する経路探索サーバに接続される端末装置であって、
    前記端末装置は、利用者登録情報と所望の出発地から目的地までの登録経路情報とを前記経路探索サーバに登録するための利用者・経路登録手段を含む操作入力手段を備えたことを特徴とする端末装置
17. 前記端末装置に提供される代替経路の情報は、代替経路の所要時間と、代替経路から算出される到着予想時刻または出発推奨時刻と、更新前の時刻表における到着時刻と前記到着予想時刻との時刻差を含み、前記端末装置は、前記代替経路の情報を受信する通信手段を有することを特徴とする請求項１６に記載の端末装置。
18. 前記利用者・経路登録手段は、前記属性情報に含まれる情報に優先度を設定し、前記経路探索サーバに登録可能になしたことを特徴とする請求項１６に記載の端末装置。

Images