(57)【特許請求の範囲】
【請求項１】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、前記乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、
前記経路探索手段は、前記経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索することを特徴とするナビゲーションシステム。
【請求項２】
前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする請求項１に記載のナビゲーションシステム。
【請求項５】
出発地と目的地を含む経路探索要求を経路探索サーバに送信し、経路探索サーバから受信した候補経路を表示する表示手段を備えた端末装置にネットワークを介して接続され、前記端末装置から受信した経路探索条件に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索サーバにおいて、
前記端末装置は、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件がユーザによって入力される操作入力手段を備え、
前記経路探索サーバは、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、
前記経路探索手段は、前記経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索することを特徴とする経路探索サーバ。
【請求項６】
前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする請求項５に記載の経路探索サーバ。
【請求項７】
前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする請求項５に記載の経路探索サーバ。
【請求項８】
前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする請求項５に記載の経路探索サーバ。
【請求項９】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路探索方法において、
前記ナビゲーションシステムは、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、前記乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、
前記経路探索条件に前記乗換回避許容コストが含まれる場合、前記ネットワークデータ編集手段により乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記乗換回避許容コストを加算する第１のステップと、
前記経路探索手段により、第１のステップにより加算された経路コストに基づいて最適経路を探索する第２のステップと、を有することを特徴とする経路探索方法。
【請求項１０】
前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする請求項９に記載の経路探索方法。
【請求項１１】
前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする請求項９に記載の経路探索方法。
【請求項１２】
前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする請求項９に記載の経路探索方法。
【請求項１３】
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、前記経路探索手段は、経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備え、前記操作入力手段により前記乗換回避許容コストを設定した経路探索条件を入力するようになしたことを特徴とする端末装置。
【請求項１４】
前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする請求項１３に記載の端末装置。
【請求項１５】
前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする請求項１３に記載の端末装置。
【請求項１６】
前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする請求項１３に記載の端末装置。
【請求項１７】
乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、出発地と目的地を含む経路探索条件および前記ネットワークデータ編集手段により編集した前記経路コストに基づき、交通機関を利用した経路を含む最適経路を探索する経路探索手段とを備える経路探索サーバにネットワークを介して接続される端末装置であって、
前記経路探索手段が探索した候補経路を表示する表示手段と、
前記表示手段に候補経路を表示する際のルート表示順序を、複数の指標の中からユーザが選択する選択手段と、
前記選択手段で選択した指標に対応する、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストをユーザが設定するための設定手段を含み、前記乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、を備え、
前記ネットワークデータ編集手段は、前記設定手段で設定した乗換回避許容コストを前記経路コストに加算することを特徴とする端末装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、徒歩や自動車あるいは公共交通機関を利用して、任意の出発地から目的地に至る候補経路を探索して案内するナビゲーションシステムに関するものであり、特に、交通機関を用いて任意の出発地から目的地に至る候補経路を探索する際に、交通機関の乗り継ぎ場所における乗り換えを回避するための許容範囲である乗換回避許容コストを指定し、乗り継ぎを含む経路コストに対して当該乗換回避許容コストを加算した経路コストに基づいて経路探索できるようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置に関するものである。
【背景技術】
【０００２】
従来から、地図データ、道路データを用いて、所望の出発地から目的地までの経路を探索して利用者を案内するナビゲーション装置、ナビゲーションシステムが知られている。このようなナビゲーション装置、ナビゲーションシステムとしては、自動車に搭載して運転者に経路を案内するカーナビゲーション装置、端末装置からネットワークを介して経路探索サーバに経路探索要求を送り、その結果を受信して経路案内を受ける通信型のナビゲーションシステムなどが実用化されている。
【０００３】
特に、通信型のナビゲーションシステムは、携帯電話などの携帯端末をナビゲーション端末として利用したシステムであって、歩行者用のナビゲーションシステムとしても用いられるものである。なお、経路探索サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や移動時間）をデータベースとして備えている。そして、経路案内サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路をナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。
【０００４】
さらに、歩行者用のナビゲーションシステムとしては、交通機関を含めた経路案内機能を付加することが好ましく、徒歩経路の探索と案内に加えて、経路探索サーバに交通機関の路線や運行時刻データを蓄積し、所望の出発駅から所望の目的駅までの経路（乗車候補列車）を、徒歩経路の探索と案内に加えて案内する機能を有するナビゲーションシステムが存在する。
【０００５】
このような交通機関を利用する経路を探索する経路探索システムは、経路探索用のデータとして、各交通機関の運行時刻データをデータベース化した運行時刻データベースと、車載用ナビゲーションシステムや歩行者用ナビゲーションシステムにおける道路ネットワークのデータと同様に交通路線の各駅をノードとし、駅間を双方向リンクとしてネットワーク化したデータの他に、各交通路線上を運行される交通手段ごとに各リンクの運行時刻、移動時間がリンクコストのデータとして加えられた交通ネットワークをデータベース化したデータを備えている。更に、運賃データが加えられ、探索した案内経路の運賃が合わせて案内されるシステムも存在する。
【０００６】
そして、ユーザが指定する出発日時、出発地、目的地、到着時刻などの経路探索条件に基づいて、これらのデータベースを参照して、乗り継ぎ（乗換え）を含めて出発地と目的地を結ぶ、利用可能な各交通手段（個々の電車や路線バス）を経路として順次たどり、経路探索条件に合致する案内経路（出発地駅、目的地駅、路線、列車などの交通手段）の候補を１つまたは複数提示するように構成される。経路探索条件としては更に、移動時間、乗り継ぎ回数、運賃などの条件を指定できるようにされているのが一般的である。
【０００７】
また、交通機関に関する検索、案内を行うシステムとして、徒歩経路の経路探索を伴わずに携帯電話などの端末装置から交通機関の路線情報や時刻表情報を案内する情報配信サーバに接続して所望の出発駅、出発時刻、目的駅などを指定して、乗車可能な路線や列車、電車などの交通手段の情報配信を受け、端末装置に表示することができる交通案内システムも存在する。一般に端末装置からこのような利用を行う場合には、ダウンロードしたい情報の存在する場所を特定するためのＵＲＬ（Uniform Resource Locator）やドメイン名などのアドレス情報を端末装置に入力して当該アドレスにより特定される情報配信サーバ（情報提供サイト）にアクセスして所望の情報をダウンロードする構成がとられている。
【０００８】
このような技術背景から、最適な路線経路を決定する技術が、例えば、下記の特許文献１（特開平３−５２０６７号公報）に「路線経路決定エキスパートシステム」として開示されている。この特許文献１に開示されたシステムは、路線経路の探索に必要な路線データ、乗り換えデータ、運行速度、運賃算出データといった知識を知識ベースに記憶し、入力した出発地点名と終着地点名の文字列をもとに、知識ベース内の知識と照らし合わせながら推論することで最適経路の決定を行うものである。
【０００９】
そして、出発地点から終着地点へ行くことができる経路のうち、乗り換え回数が最小となる経路の候補を選びだし、各経路に関して乗り換え時間を含む移動時間を算出し、最小となる経路を決定し、経路が決定されると運賃、路線距離を算出して表示を行うように構成されている。
【００１０】
また、交通機関の運行時刻表に照らし合わせて乗り継ぎ経路探索を行う技術が、例えば、下記の特許文献２（特開平１０−３３４３８７号公報）に「最適乗継系列探索方法およびシステム」として開示されている。
【００１１】
この特許文献２に開示されたシステムは、出発地、目的地、出発希望時刻、探索時間範囲を指定し、前記出発地および目的地より、経路探索の範囲を限定し、時刻表データから経路探索範囲外の乗継ノードを含む運行リンクを探索対象外とし、前記出発地、目的地が乗継ノードでない場合には、平均移動時間ネットワークを用いて最寄りの複数個の乗継ノードを見出し、連絡リンクを形成し、到着時刻順にソートされた時刻表データを用いて探索時間範囲内で運行リンクの付加により動的ネットワークを形成し、前記乗継ノードには到着した運行リンク番号と出発地出発時刻の組（運行情報）を要素として、出発地出発時刻の遅い順位ソートされた運行情報リストを登録することで最適乗継系列を探索するものである。すなわち、このシステムでは、系列探索を短時間に処理できるように、出発地と目的地とからあらかじめ探索地域を限定することによって無駄な系列探索を省くように構成されている。
【００１２】
さらに、本願の出願人は、出発時刻に幅を持たせた乗換え探索を行う技術として、既に特願２００７−１３０６５３号の発明についての特許出願を行っている。
【００１３】
この特願２００７−１３０６５３号（以下、「先願」という。）に開示された発明においては、出発地と目的地を含む経路探索要求に基づいて、経路探索用のネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、  出発地からの出発時刻の範囲を含む経路探索条件を入力する操作入力手段と、出発時刻の範囲を判別する時刻範囲判別手段と、時刻条件をシフトする時刻条件シフト手段と、案内経路ソート手段と、を備え、時刻条件シフト手段は、予め定められた条件に従って前記出発時刻範囲内において、前記時刻条件を順次異なる時刻条件に変更し、経路探索手段は前記時刻条件シフト手段が変更した時刻条件に基づいて最適経路を探索して候補経路として案内経路ソート手段に記憶し、該案内経路ソート手段は、前記候補経路を前記経路探索条件により指定された順にソートして出力するように構成されている。
【００１４】
このように構成された先願のナビゲーションシステムによれば、出発時刻の範囲を指定するだけで、指定した出発時刻範囲に含まれる複数の候補経路を探索することができ、それらの候補経路を所望の条件の順にソートした案内経路の情報を得ることができるようになるため、利用者はその候補経路の中から自身の要求にあった経路を容易に選択することができるようになる。
【特許文献１】特開平３−５２０６７号公報（第１図）
【特許文献２】特開平１０−３３４３８７号公報（図５、段落［００３８］、［００３９］）
【発明の開示】
【発明が解決しようとする課題】
【００１５】
前述した上記特許文献１あるいは特許文献２に開示された従来の乗り継ぎ探索は、いくつかの最適に近い経路候補の中から乗り換え回数が最小となる経路を選ぶのが一般的であった。このため、もともと経路候補として挙がった複数の案内経路の中から最適な経路を選択するので、あまり不適切な経路が選択されることはなかった。
【００１６】
しかしながら、先願のように所望の出発時刻範囲を条件とした経路探索を行う場合には、探索される経路候補が圧倒的に多くなる。また、厳密に乗り換え回数が最小になる経路を求めると、乗り換え回数は少ないが、乗り換えの待ち時間が非常に長い経路が探索されてしまうこともある。特に、遠方の目的地までの経路探索を行った場合には長距離列車を乗り継ぐ傾向が顕著になるため、待ち時間が非常に長くなる場合がある。上記特許文献１や特許文献２に開示された経路探索の手法ではこのような不都合を解消できないという問題点があった。
【００１７】
さらに、利用者の中には乗り換え回数が少ない経路を希望しつつも、乗り換え回数以外の他の条件、例えば、時間、運賃、あるいは徒歩距離などの条件とのバランスも考慮して総合的に最適な経路を得ることができる経路探索サービスの提供を受けたいというニーズも高まってきている。
【００１８】
本願の発明者は、上記の問題点を解消すべく種々検討を重ねた結果、交通機関の乗り継ぎ場所における乗り換えを回避するための許容範囲である乗換回避許容コストを指定させことにより、上記問題点を解消し得ることを想到して本発明を完成するに至ったものである。
【００１９】
すなわち、本発明は上記の問題点を解消することを課題とし、交通機関を用いて任意の出発地から目的地に至る候補経路を探索する際に、交通機関の乗り継ぎ場所における乗り換えを回避するための乗換回避コストの許容範囲である乗換回避許容コストを指定し、乗り継ぎを含む経路コストに対して当該乗換回避許容コストを加算した経路コストに基づいて最適経路を探索するようにしたナビゲーションシステム、経路探索サーバおよび経路探索方法ならびに端末装置を提供することを目的とするものである。
【課題を解決するための手段】
【００２０】
前記課題を解決するために、本願の請求項１にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおいて、
前記ナビゲーションシステムは、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、前記乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、
前記経路探索手段は、前記経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索することを特徴とする。
【００２２】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする。
【００２３】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする。
【００２４】
本願の請求項４にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする。
【００２５】
また、本願の請求項５にかかる発明は、
出発地と目的地を含む経路探索要求を経路探索サーバに送信し、経路探索サーバから受信した候補経路を表示する表示手段を備えた端末装置にネットワークを介して接続され、
前記端末装置は、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件がユーザによって入力される操作入力手段を備え、
前記経路探索サーバは、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記操作入力手段により入力された乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、
前記経路探索手段は、前記経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索することを特徴とする。
【００２７】
本願の請求項６にかかる発明は、請求項５にかかる経路探索サーバにおいて、前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする。
【００２８】
本願の請求項７にかかる発明は、請求項５にかかる経路探索サーバにおいて、前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする。
【００２９】
本願の請求項８にかかる発明は、請求項５にかかる経路探索サーバにおいて、前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする。
【００３０】
さらに、本願の請求項９にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備えたナビゲーションシステムにおける経路探索方法において、
前記ナビゲーションシステムは、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、前記乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対して前記操作入力手段により入力された乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、
前記経路探索条件に前記乗換回避許容コストが含まれる場合、前記ネットワークデータ編集手段により乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記乗換回避許容コストを加算する第１のステップと、
前記経路探索手段により、第１のステップにより加算された経路コストに基づいて最適経路を探索する第２のステップと、を有することを特徴とする。
【００３２】
本願の請求項１０にかかる発明は、請求項９にかかる経路探索方法において、前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする。
【００３３】
本願の請求項１１にかかる発明は、請求項９にかかる経路探索方法において、前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする。
【００３４】
本願の請求項１２にかかる発明は、請求項９にかかる経路探索方法において、前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする。
【００３５】
また、本願の請求項１３にかかる発明は、
出発地と目的地を含む経路探索要求に基づいて、経路探索用ネットワークデータを参照して交通機関を利用した経路を含む最適経路を探索する経路探索手段と、乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、前記経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、前記経路探索手段は、経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、前記経路探索手段が探索した候補経路を表示する表示手段と、を備え、前記操作入力手段により前記乗換回避許容コストを設定した経路探索条件を入力するようになしたことを特徴とする。
【００３７】
本願の請求項１４にかかる発明は、請求項１３にかかる端末装置において、前記乗換回避許容コストは、乗り換えを時間に換算した時間コストであることを特徴とする。
【００３８】
本願の請求項１５にかかる発明は、請求項１３にかかる端末装置において、前記乗換回避許容コストは、乗り換えを運賃に換算した運賃コストであることを特徴とする。
【００３９】
本願の請求項１６にかかる発明は、請求項１３にかかる端末装置において、前記乗換回避許容コストは、乗り換えを徒歩距離に換算した徒歩距離コストであることを特徴とする。
また、本願の請求項１７にかかる発明は、
乗換回避許容コストを設定した経路探索条件に基づく経路探索が要求された場合に、経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、出発地と目的地を含む経路探索条件および前記ネットワークデータ編集手段により編集した前記経路コストに基づき、交通機関を利用した経路を含む最適経路を探索する経路探索手段とを備える経路探索サーバにネットワークを介して接続される端末装置であって、
前記経路探索手段が探索した候補経路を表示する表示手段と、
前記表示手段に候補経路を表示する際のルート表示順序を、複数の指標の中からユーザが選択する選択手段と、
前記選択手段で選択した指標に対応する、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストをユーザが設定するための設定手段を含み、前記乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、を備え、
前記ネットワークデータ編集手段は、前記設定手段で設定した乗換回避許容コストを前記経路コストに加算することを特徴とする。
【発明の効果】
【００４０】
請求項１にかかる発明においては、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件が、ユーザによって入力される操作入力手段と、乗換回避許容コストを含設定した経路探索条件に基づく経路探索が要求された場合に、経路探索用ネットワークデータに含まれる乗り継ぎを含む経路コストに対し、乗り継ぎがあるごとに前記操作入力手段により入力された前記乗換回避許容コストを加算するネットワークデータ編集手段と、を備え、経路探索手段は、前記経路探索条件に前記乗換回避許容コストが含まれる場合、乗り継ぎを含む経路コストに対して前記ネットワークデータ編集手段により前記乗換回避許容コストを加算した経路コストに基づいて最適経路を探索するように構成した。
【００４１】
このような構成によれば、交通機関の乗り継ぎ場所における乗り換えの回数を少なくするための乗換回避許容コストを設定した経路探索条件、または、前記乗換回避許容コストを設定しない経路探索条件を入力するだけで、交通機関の乗り継ぎ場所における乗り換えが発生するごとに乗り継ぎを含む経路コストに対して指定した乗換回避許容コストを加算した経路コストに基づいて候補経路を探索することができ、乗り換える代わりに余計にかかる乗換回避コストが利用者の許容範囲を満たし、かつ乗り換えの回数を少なくした案内経路の情報を得ることができるようになる。したがって、利用者はさらに自身の要求にあった所望の経路を得ることができるようになる。
【００４４】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、乗換回避許容コストは、乗り換えを時間に換算した時間コストとするように構成した。
【００４５】
このような構成によれば、交通機関の乗り継ぎ場所における乗り換えを回避するための許容範囲である時間コストを指定するだけで、乗り継ぎを含む経路コストに対して指定した時間コストを加算した経路コストに基づいて候補経路を探索することができ、乗り換える代わりに余計にかかる時間コストが利用者の許容範囲を満たし、かつ乗り換えを回避した案内経路の情報を得ることができるようになる。したがって、利用者はさらに自身の要求にあった所望の経路を得ることができるようになる。これは、乗り換えを嫌う場合に、例えば乗り換えを１回するくらいなら１０分余計にかかっても乗り換えをしない電車の方を選ぶことに相当し、乗り換え１回を１０分のペナルティと見なし、出発地から目的地までにかかるトータルな所要時間が１０分余計にかかる経路を探索することになる。
【００４６】
請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、乗換回避許容コストは、運賃に換算された運賃コストとするように構成した。
【００４７】
このような構成によれば、交通機関の乗り継ぎ場所における乗り換えを回避するための許容範囲である運賃コストを指定するだけで、乗り継ぎを含む経路コストに対して指定した運賃コストを加算した経路コストに基づいて候補経路を探索することができ、乗り換える代わりに余計にかかる運賃コストが利用者の許容範囲を満たし、かつ乗り換えを回避した案内経路の情報を得ることができるようになる。したがって、利用者はさらに自身の要求にあった所望の経路を得ることができるようになる。
【００４８】
請求項４にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、乗換回避許容コストは、徒歩距離に換算された徒歩距離コストとするように構成した。
【００４９】
このような構成によれば、交通機関の乗り継ぎ場所における乗り換えを回避するための許容範囲である徒歩距離コストを指定するだけで、乗り継ぎを含む経路コストに対して指定した徒歩距離コストを加算した経路コストに基づいて候補経路を探索することができ、乗り換える代わりに余計にかかる徒歩距離コストが利用者の許容範囲を満たし、かつ乗り換えを回避した案内経路の情報を得ることができるようになる。したがって、利用者はさらに自身の要求にあった所望の経路を得ることができるようになる。
【００５０】
また、請求項５〜請求項８にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを構成する経路探索サーバを提供することができ、請求項９〜請求項１２にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを実現するための経路探索方法を提供することができるようになる。また、請求項１３〜請求項１７にかかる発明においては、それぞれ請求項１〜請求項４にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。
【発明を実施するための最良の形態】
【００５１】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【実施例】
【００５２】
図１は、本発明の実施例にかかるナビゲーションシステム１０の構成を示すシステム構成図である。図１に示すようにナビゲーションシステム１０は、ネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。このナビゲーションシステム１０は、各種カテゴリに属するＰＯＩ（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ：興味対象場所）の所在地やサービス内容、広告などの詳細情報を提供するＰＯＩ情報配信サーバ５０、地図データ、交通路線データや運行時刻表データ、音楽や各種画像などのコンテンツ、その他の情報を提供する各種の情報配信サーバ５１などを備えて構成されている。
【００５３】
経路探索サーバ３０はＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１からネットワーク１２を経由して必要なデータを取得して自身のデータベースに追加することができる。また、同様にしてＰＯＩ情報配信サーバ５０や他の情報配信サーバ５１に検索要求を送信して所望の検索結果を取得することもできる。
【００５４】
本発明にかかるナビゲーションシステム１０は、上記の構成に限られるものではなく、経路探索サーバ３０はナビゲーションサービス機能とともにＰＯＩ所在場所の地図を配信する地図配信サーバの機能を有していてもよい。また、端末装置２０も携帯電話を用いることができ、またＰＤＡや音楽プレイヤーや携帯ゲーム機などの携帯機器、あるいは、パーソナルコンピュータ（ＰＣ）であってもよい。
【００５５】
図１に示す経路探索サーバ３０は、地図データベース３４、経路探索用ネットワークデータベース３５を備え、端末装置２０から経路探索要求があると、経路探索用ネットワークデータベース３５を参照して経路探索する。そして経路探索の結果により得た案内経路（推奨経路）を端末装置２０に送信する一般的なナビゲーション機能を有している。また、端末装置２０から所望の地点やＰＯＩを指定して地図データの取得要求があると、地図データベース３４を参照して該当する地図データを読み出して端末装置２０に配信する。
【００５６】
端末装置２０が経路探索サーバ３０に経路探索を要求し、経路案内のサービスを受ける場合には、端末装置２０において所望の出発地や目的地などの経路探索条件を設定し、経路探索サーバ３０に経路探索要求を送信する。端末装置２０は、乗り換えを回避するための許容範囲である乗換回避許容コストを経路探索条件として経路探索を要求する場合には、許容できる乗換回避許容コストを設定することができる。ここで、乗換回避許容コストは次のように定義されている。
【００５７】
図３は、乗換回避許容コストの種別と各コストの許容範囲の対応関係を説明するための図である。図３に示すように、乗換回避許容コストとして利用者が指定できる３種類のコスト「時間」「運賃」「徒歩距離」について、利用者が許容できる値として４段階のレベルに対応する許容値を示している。乗換回避許容コストが、例えば、１回の乗り換えを時間的価値に置き換えた時間コストの場合には、「５分」「１０分」「１５分」「２０分」の４つの許容レベルの時間コストが設定されている。
【００５８】
これは、例えば、指定した時間コストが「１０分」の場合、目的地に到着するまでの所要時間が１０分余計にかかっても乗り換えをしない電車（経路）の方が良いと判断し、１回の乗り換えを１０分のペナルティとみなし、乗り継ぎを含む経路と乗り継ぎを含まない他の経路について出発地から目的地までにかかるトータルな所要時間を比較すると乗り継ぎを含む経路の方が１回の乗り換えにつき１０分余計にかかる経路として探索されることを意味する。
【００５９】
そして、１回の乗り換えあたりのペナルティをどのくらいの時間的価値とみなすかは、利用者によって好みがあるので、５分から２０分までの範囲の中で４段階の許容値を設定できるように構成されている。
そして端末装置２０から乗換回避許容コストを設定する際には、乗換回避許容コストが乗り換えを時間に換算した時間コストの場合では、「（乗り換えは）５分遅くなっても避ける」、「（乗り換えは）１０分遅くなっても避ける」のように指定する。
【００６０】
なお、時間的価値のほかに運賃コストや徒歩距離コストなどが１回の乗り換えを置き換える価値として用いることができ、それぞれ乗換回避許容コストとして設定する際には、「（乗り換えは）５００円高くなっても避ける」あるいは「（乗り換えは）５０ｍ歩いても避ける」などのように指定する。
【００６１】
経路探索サーバ３０は、端末装置２０から、乗換回避許容コストを設定した経路探索要求があると、指定された乗換回避許容コストを経路探索用ネットワークデータベース３５に含まれる経路コストに加算して候補経路を探索する。この時の経路探索は一般的なナビゲーションシステムで行われる設定条件指定の経路探索の手法で行うことができる。
【００６２】
このような経路探索を行えば、所望の乗換回避許容コスト内で目的地に到達できる候補経路を得ることができ、端末装置２０の利用者はさらに自身の要求にあった所望の経路を得ることができるようになる。
【００６３】
以下、具体例に基づいて本発明の実施例にかかるナビゲーションシステム１０を説明するが、その前に本発明にかかるナビゲーションシステム１０の詳細な構成を説明する。図２は、図１のナビゲーションシステム１０の詳細な構成を示すブロック図である。端末装置２０は、ナビゲーションサービスを受けることができる端末であり、制御手段２０１、通信手段２１、ＧＰＳ受信手段２２、探索要求手段２３、案内経路データ記憶手段２４、表示手段２５、操作入力手段２６を備えて構成されている。
【００６４】
端末装置２０において、制御手段２０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段２１はネットワーク１２を介して経路探索サーバ３０などと通信データを送受信するための通信インターフェースである。
【００６５】
ＧＰＳ受信手段２２はＧＰＳ衛星からの信号を受信して現在位置を緯度・経度で算出する。操作入力手段２６は、数字やアルファベットキーやその他の機能キー、選択キー、スクロールキー（上下左右の矢印キー）などからなり、端末装置２０を操作するための入力を行い、また、出発地、目的地などの経路探索条件の入力機能としても用いられる。表示手段２５は液晶表示パネルなどからなり、経路探索サーバ３０から配信（送信）された案内経路や推奨経路あるいは地図の表示に使用されるものである。また、表示手段２５はメニュー画面を表示し端末装置２０を操作するための入力手段としても機能する。
【００６６】
探索要求手段２３は、操作入力手段２６または表示手段２５により設定された出発地、目的地などの経路探索条件に基づいて経路探索要求を作成し、経路探索サーバ３０に送信する。
【００６７】
案内経路データ記憶手段２４は、経路探索サーバ３０から配信される経路探索結果である案内経路データなどを一時記憶するものであり、経路探索サーバ３０から端末装置２０に送信される案内経路、推奨経路などの案内経路データは地図データとともに案内経路データ記憶手段２４に記憶され、案内経路データ記憶手段２４に記憶された案内経路などの案内データや地図データは、必要に応じて読み出され、表示手段２５に表示される。
【００６８】
表示手段２５に地図を表示する場合、一般的には、ＧＰＳ受信手段２２で測位した端末装置２０の現在位置を含む一定の縮尺、一定の範囲の地図に、案内経路と、端末装置２０の現在位置を示すマークを重ね合わせて該現在位置マークが表示画面の中心になるように表示する。測位した位置情報には誤差が含まれるため、現在位置が案内経路からずれている場合には現在位置を案内経路上に補正するルートマッチング処理が行われる。また、経路探索サーバ３０から配信される案内経路データに音声ガイドのデータが付加されている場合は、例えば、交差点や分岐点（案内ポイント）に端末装置２０が近づいた際に、「この先、３００ｍ交差点です。左折して下さい」などの音声メッセージをスピーカから再生出力してユーザをガイドする。
【００６９】
図４は、本発明の実施例にかかる端末装置としての携帯電話の外観を示す図である。端末装置２０が携帯電話である場合、図４に示すように、液晶表示パネルなどからなる表示手段２５、テンキーやスクロールキーＳＫ（ランチャーキー）を有し、特定の数字キーなどにクリアキー、表示モード切り替えキーが割り当てられた操作入力手段２６を備えている。経路探索サーバ３０から送信された地図データや案内経路データは案内経路データ記憶手段２４に記憶され、必要に応じて案内経路データ記憶手段２４から読み出され、表示手段２５の表示画面２５１に表示される。
【００７０】
図５は、表示画面２５１に表示される経路探索条件入力画面５００の一例を示す図である。端末装置２０は、操作入力手段２６により入力された条件や操作に基づいて経路探索要求を経路探索サーバ３０に送信する。経路探索サーバ３０に経路探索要求する場合には、図５に示すように表示手段２５に表示されたメニューから、あるいは、操作入力手段２６から所望の出発地、目的地を設定して経路探索サーバ３０に送信する。
【００７１】
この経路探索条件入力画面５００には、出発地入力欄５０１、目的地入力欄５０２、利用日入力欄５０３、時刻入力欄５０４、時刻種別入力欄５０５、移動手段入力欄５０６、ルート表示順序入力欄５０７、乗換回避許容コスト入力欄５０８、徒歩設定入力欄５０９、使用路線入力欄５１０、現在時間で探索開始ボタン５１１、設定条件で探索開始ボタン５１２が設けられている。
【００７２】
出発地と目的地の設定は、出発地入力欄５０１、目的地入力欄５０２に住所や電話番号あるいは駅名称、ビル名称などの地点名称、緯度・経度などを入力して設定する。すなわち、この入力欄は、原則としてフリーワード入力が可能であるが、住所、電話番号、ＰＯＩ（Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）の名称などで設定することできる。また、出発地の入力には、ＧＰＳ受信手段２２で測位した端末装置２０の現在位置を用いるようにすることもできる。さらに、端末装置２０の表示手段２５に地図を表示させ、表示されている地図上でポイントを指定し緯度、経度の情報に変換する方法を用いてもよい。
【００７３】
利用日と時刻の設定は、利用日入力欄５０３、時刻入力欄５０４に運行時刻表データに従って探索を行うために実際に電車などの交通機関を利用する日付と時刻を入力して設定する。なお、利用日入力欄５０３、時刻入力欄５０４には、初期値として経路探索条件入力画面５００を表示させた日付と時間が設定されている。
【００７４】
時刻種別入力欄５０５では、時刻入力欄５０４に入力された時刻の種別について従来からの「出発」「到着」「終電」「始発」の条件をプルダウンメニュー５０５−１で選択設定することが可能である。これにより、「出発」または「到着」を選択すると出発時刻なのか到着時刻なのかを設定できる。また、「終電」とは最も出発を遅らせることができる経路、「始発」とはその日に出発して最も早く目的地に到着できる経路を要求する。
【００７５】
移動手段入力欄５０６では、経路探索時の移動手段を選択設定することが可能である。「乗物＋徒歩」を選択した場合は、使用路線欄５１０にて許可する乗り物（飛行機、新幹線、特急線、路線バスなど）を設定することができる。
【００７６】
ルート表示順序入力欄５０７では、ルート表示の順序について従来からの「所要時間が短い順」「運賃が安い順」「乗り換え回数が少ない順」「歩きが少ない（徒歩経路の距離が短い）順」の条件をプルダウンメニュー５０７−１で選択設定することが可能である。
【００７７】
ここで、「所要時間の短い順」では指定された出発時刻範囲を満たし、所要時間の短い順に経路が求まり、「運賃の安い順」では指定された出発時刻範囲を満たし、運賃の安い順に経路が求まる。また、「乗り換え回数の少ない順」では指定された出発時刻範囲を満たし、乗り換えの回数が少ない順に経路が求まり、「徒歩区間の距離の小さい順」では指定された出発時刻範囲を満たし、徒歩経路が少ない順に経路が求まる。
【００７８】
初期値は「乗り換え回数が少ない順」に設定されているが、この「乗り換え回数が少ない順」以外の条件を選択すると本発明が機能するようになる。
【００７９】
すなわち、「所要時間が短い順」が選択された場合には、乗換回避許容コストは乗り換えを時間に換算した時間コストとみなし、乗換回避許容コスト入力欄５０８にて指定される許容時間を加味したトータルな所要時間に基づいて候補経路を探索することになり、乗り換える代わりに余計にかかる時間コストが利用者の許容範囲を満たす案内経路の情報を得ることになる。
【００８０】
また、「運賃の安い順」が選択された場合には、乗換回避許容コストは運賃に換算された運賃コストとみなし、乗換回避許容コスト入力欄５０８にて指定される許容運賃を加味したトータルな所要運賃に基づいて候補経路を探索することになり、乗り換える代わりに余計にかかる運賃コストが利用者の許容範囲を満たす案内経路の情報を得ることになる。
【００８１】
また、「歩きが少ない（徒歩経路の距離が短い）順」が選択された場合には、乗換回避許容コストは徒歩距離に換算された徒歩距離コストとみなし、乗換回避許容コスト入力欄５０８にて指定される許容徒歩距離を加味したトータルな所要徒歩距離に基づいて候補経路を探索することになり、乗り換える代わりに余計にかかる徒歩距離コストが利用者の許容範囲を満たす案内経路の情報を得ることになる。
【００８２】
乗換回避許容コスト入力欄５０８では、利用者が許容できる乗換回避許容コストの許容値を選択設定することが可能である。図５では、ルート表示順序入力欄５０７において「所要時間が短い順」が選択された場合に利用者が選択設定することが可能な条件を示している。
【００８３】
すなわち、ルート表示順序入力欄５０７において「所要時間が短い順」が選択された場合には、乗換回避許容コスト入力欄５０８では、乗換回避許容コストについて「（乗り換えは）気にしない」「（乗り換えは）５分遅くなっても避ける」「（乗り換えは）１０分遅くなっても避ける」「（乗り換えは）１５分遅くなっても避ける」「（乗り換えは）２０分遅くなっても避ける」の条件をプルダウンメニュー５０８−１で選択設定することが可能である。初期値は「気にしない」に設定されているが、「気にしない」以外の条件を選択すると本発明が機能するようになる。また、乗換回避許容コストの入力は、数値入力方式にすることもできる。
【００８４】
徒歩設定入力欄５０９では、徒歩速度について従来からの「せかせか」「標準」「ゆっくり」の条件をプルダウンメニュー５０９−１で選択設定することが可能である。ここで、「せかせか」は時速６ｋｍ／ｈ、「標準」は時速５ｋｍ／ｈ、「ゆっくり」は時速４ｋｍ／ｈで徒歩区間の時間コストを見積もる。
【００８５】
必要な条件設定を終え、探索開始ボタン５１１または５１２を操作すると、経路探索要求が端末装置２０から経路探索サーバ３０に送信される。
【００８６】
また、図６は、表示画面２５１に表示される経路探索条件入力画面５００のその他の例を示す図である。図６では、ルート表示順序入力欄５０７において「運賃の安い順」が選択された場合に利用者が選択設定することが可能な条件を示している。
【００８７】
すなわち、ルート表示順序入力欄５０７において「運賃の安い順」が選択された場合には、乗換回避許容コスト入力欄５０８では、乗換回避許容コストについて「（乗り換えは）気にしない」「（乗り換えは）５００円高くなっても避ける」「（乗り換えは）１０００円高くなっても避ける」「（乗り換えは）１５００円高くなっても避ける」「（乗り換えは）２０００円高くなっても避ける」の条件をプルダウンメニュー５０８−２で選択設定することが可能である。なお、プルダウンメニュー５０８−２以外のその他の入力欄および探索開始ボタンは図５と同じである。
【００８８】
初期値は「気にしない」に設定されているが、「気にしない」以外の条件を選択すると本発明が機能するようになる。また、乗換回避許容コストの入力は、数値入力方式にすることもできる。
【００８９】
また、図７は、表示画面２５１に表示される経路探索条件入力画面５００のその他の例を示す図である。図７では、ルート表示順序入力欄５０７において「歩きが少ない（徒歩経路の距離が短い）順」が選択された場合に利用者が選択設定することが可能な条件を示している。
【００９０】
すなわち、ルート表示順序入力欄５０７において「歩きが少ない（徒歩経路の距離が短い）順」が選択された場合には、乗換回避許容コスト入力欄５０８では、乗換回避許容コストについて「（乗り換えは）気にしない」「（乗り換えは）５０ｍ歩いても避ける」「（乗り換えは）１００ｍ歩いても避ける」「（乗り換えは）２００ｍ歩いても避ける」「（乗り換えは）４００ｍ歩いても避ける」の条件をプルダウンメニュー５０８−３で選択設定することが可能である。なお、プルダウンメニュー５０８−３以外のその他の入力欄および探索開始ボタンは図５と同じである。
【００９１】
初期値は「気にしない」に設定されているが、「気にしない」以外の条件を選択すると本発明が機能するようになる。また、乗換回避許容コストの入力は、数値入力方式にすることもできる。
【００９２】
一方、経路探索サーバ３０は、図２に示すように、制御手段３０１、通信手段３１、探索要求記憶手段３２、経路探索手段３３、地図データベース３４、経路探索用ネットワークデータベース３５、ネットワークデータ編集手段３６、案内経路データ編集手段３７を備えて構成されている。
【００９３】
経路探索サーバ３０において、制御手段３０１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３１はネットワーク１２を介して端末装置２０やＰＯＩ情報配信サーバ５０、他の情報配信サーバ５１と通信するためのインターフェースである。
【００９４】
探索要求記憶手段３２は端末装置２０から送信される経路探索要求に含まれている経路探索条件を一時記憶するためのものである。
【００９５】
経路探索手段３３は、端末装置２０から送信される出発地、目的地などの経路探索条件や現在位置の情報に基づいて、探索用ネットワークデータベース３５を参照して、出発地から目的地までの経路探索を行う。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。このような構成は一般のナビゲーションシステムと同様のものである。
【００９６】
経路探索用ネットワークデータベース３５は、徒歩や自動車による移動経路を探索するための道路ネットワークデータと公共交通機関を利用した移動経路を探索するための交通ネットワークデータが蓄積されている。具体的には、道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、ノードデータ、リンクデータ、全てのリンクのコスト情報（距離や所要時間）であるリンクコストデータから構成され、データベース化されたものである。交通機関のネットワークデータも駅をノードとし、駅と駅を結ぶリンクと、リンクとなる電車等の各車両の時刻表データ（発車時刻、到着時刻、所要時間）をリンクコストデータとして蓄積したものである。
【００９７】
歩行者ナビゲーションシステムやカーナビゲーションシステムにおける経路探索のための道路ネットワークデータは以下のように構成されている。図８は、道路ネットワークのデータの概念を示す図である。例えば、道路が図８に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００９８】
すなわち、図８において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図８では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００９９】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図８において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【０１００】
図８ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【０１０１】
これに対して、交通機関の経路探索のための交通ネットワークデータは以下のように構成されている。図９は、交通ネットワークのデータの概念を示す図である。例えば、図９に示すように交通路線Ａ、Ｂ、Ｃからなる場合、各交通路線Ａ、Ｂ、Ｃに設けられた各駅（航空機の路線においては各空港）をノードとし、各ノード間を結ぶ区間を有向性のリンクで表し、ノードデータ（緯度・経度）、リンクデータ（リンク番号）をネットワークデータとしている。図９において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は交通路線の乗り継ぎ点（乗換え駅など）を示し、各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、交通路線の上り、下りそれぞれの方向を向いたリンクが存在するが、図９では図示を簡略化するため矢印の向きのリンクのみを図示している。
【０１０２】
しかしながら、交通ネットワークは道路ネットワークと比べリンクコストが基本的に異なる。すなわち、道路ネットワークではリンクコストは固定的、静的なものであったが、交通ネットワークでは、図９に示すように交通路線を運行する列車や航空機（以下個々の列車や航空機などの各経路を交通手段と称する）が複数ある。各交通手段毎にあるノードを出発する時刻と次のノードに到着する時刻とが定まっており（時刻表データ、運行データで規定される）、かつ、個々の経路が必ずしも隣接するノードにリンクしない場合がある。例えば、急行と各駅停車の列車のような場合である。このような場合には同じ交通路線上に異なる複数のリンクが存在することになり、またノード間の所要時間が交通手段により異なる場合もある。
【０１０３】
図９に例示する交通ネットワークにおいては、交通路線Ａの同じリンクに複数の交通手段（経路）Ａａ〜Ａｃ・・・、交通路線Ｃに複数の交通手段（経路）Ｃａ〜Ｃｃ・・・が存在することになる。従って、交通機関の運行ネットワークは、単純な道路ネットワークと異なり、ノード、リンク、リンクコストの各データは交通手段（個々の航空機や列車などの経路）の総数に比例したデータ量になる。このため交通ネットワークのデータは道路ネットワークのデータ量に比べて膨大なデータ量になる。従って、それに応じて、経路探索に要する時間も多くの時間が必要になる。
【０１０４】
このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定する必要がある。
【０１０５】
例えば、図９において、出発地を交通路線ＡのノードＡＸとしてある特定の出発時刻を指定して、交通路線ＣのノードＣＹを目的地とする経路探索を行う場合、交通路線Ａ上を運行する交通手段Ａａ〜Ａｃ・・・のうち出発時刻以降の全ての交通手段を順次出発時の経路として選択する。そして交通路線Ｃへの乗り継ぎノードへの到着時刻に基づいて、交通路線Ｃ上を運行する各交通手段Ｃａ〜Ｃｃ・・・のうち、乗り継ぎノードにおいて乗車可能な時刻以降の交通手段の全ての組み合わせを探索して各経路の所要時間や乗り換え回数などを累計して案内することになる。
【０１０６】
このようなネットワークデータを利用して経路探索サーバ３０は経路探索条件に従って、出発地から目的地までの複数の候補経路を探索し、その結果を案内経路データとして端末装置２０に送信する。経路探索条件に出発地の出発時刻が指定されている場合には出発地の出発時刻が案内経路データに含まれ、端末装置２０はこれらを表示手段２５に経路の詳細とともに表示することができる。案内経路に乗り換え駅が含まれる場合には、当該乗り換え駅で乗り換えるべき電車やその出発時刻も同様にして表示することができる。
【０１０７】
地図データベース３４は、ベクトル地図データを蓄積している。地図データベース３４に蓄積される地図データは所定の緯度・経度範囲で区分された単位地図データから構成されている。
【０１０８】
図１０は地図データの構成を示す図である。図１０に示すように、地図データは所定の緯度、経度単位で地図エリアが分けられ、メッシュ状の単位地図データＭ１１〜Ｍ３３のように構成されている。端末装置２０に配信される場合は、端末装置２０の現在位置ＰＰを含む単位地図データＭ２２を中心にして、その上下方向、左右方向、斜め方向に隣接する単位地図データＭ２１、Ｍ２３、Ｍ１２、Ｍ３２、Ｍ１１、Ｍ１３、Ｍ３１、Ｍ３３の合計９つの単位地図が配信される。
【０１０９】
端末装置２０が移動して地図データが不足する場合は、端末装置２０の移動方向を判別して経路探索サーバ３０は不足分の単位地図データを配信する。端末装置２０が特定の地点やＰＯＩ（興味対象場所：Ｐｏｉｎｔ  ｏｆ  Ｉｎｔｅｒｅｓｔ）の位置を指定して地図データの配信要求をした場合も同様である。案内経路のデータはこのベクトル地図データとともに端末装置２０に配信される。端末装置２０は、経路探索サーバ３０からこのようにして地図データおよび案内経路のデータを受信して、地図および案内経路を表示手段２５に表示する。
【０１１０】
ネットワークデータ編集手段３６は、本実施例において、端末装置２０の利用者が乗り換えを回避するための許容範囲である乗換回避許容コストを指定した経路探索を要求した場合、経路探索用ネットワークデータベース３５に含まれている乗り継ぎを含む経路コストに対して指定された乗換回避許容コストを加算するものである。このようにして加算された経路コストに基づいて経路探索を行うと、乗り換える代わりに余計にかかる経路コストが利用者の許容範囲を満たし、かつ乗り換えを回避した案内経路が選ばれる。
【０１１１】
案内経路データ編集手段３７は、経路探索手段３３が探索した案内経路（個々の列車などの交通手段）を端末装置２０に配信するためのデータに編集するためのものである。すなわち、案内経路データ編集手段３７は、経路探索手段３３が探索した最適経路あるいは複数の候補経路のデータを地図データベース３４から読み出された現在位置を含む地図データに埋め込む等の編集を行って案内経路データを作成する。
【０１１２】
端末装置２０への候補経路（探索結果）の出力は、端末装置２０が設定したルート表示順序に従ってソートして行われる。例えば、図５の経路探索条件入力画面５００に示したように出力順として「所要時間の短い順」が指定されている場合、案内経路データ編集手段３７は、一時記憶している複数の候補経路を出発地から目的地までの所要時間が短い順にソートする。
【０１１３】
案内経路データは、ベクターデータとして作成された案内経路に地図データが付加されて配信され、経路探索手段３３で探索された案内経路上の出発地、経路の屈曲点、交差点、目的地などのガイドポイントが設定され、それらのガイドポイントの位置座標（緯度・経度）、各ガイダンスポイントに関連する案内情報（直進や右左折のガイダンス情報）が含まれる。端末装置２０は、配信された地図データと案内経路データを受信し、地図および案内経路を表示し、ガイダンスポイントに到着した時点で所定のガイドを表示または音声で出力する。
【０１１４】
端末装置２０の利用者は、端末装置２０において経路探索サーバ３０に経路探索を依頼しようとする場合、操作入力手段２６を操作してメニュー画面や所定の入力画面を表示手段２５に表示して、出発地や目的地、乗り換え許容時間などの経路探索条件の入力を行う。また、端末装置２０は、経路探索サーバ３０から案内経路データと地図データを受信するとこれを案内経路データ記憶手段２４に一時記憶し、端末装置２０の現在位置を示す現在位置マークと、現在位置を含む所定の範囲の地図と案内経路を表示手段２５に表示する。現在位置が変化し、地図データが不足した場合には端末装置２０は経路探索サーバ３０に地図データを要求し、不足している地図データの配信を受ける。
【０１１５】
経路探索サーバ３０は、端末装置２０から経路探索要求があると、これを探索要求記憶手段３２に一時記憶する。そして経路探索手段３３は、探索要求記憶手段３２に記憶した経路探索要求に従って経路探索用ネットワークデータベース３５を参照して出発地から目的地までの複数の候補経路を探索する。ここで、端末装置２０の利用者が乗り換えを回避するための許容範囲である乗換回避許容コストを指定した経路探索を要求した場合には、経路探索用ネットワークデータベース３５に含まれている乗り継ぎを含む経路コストに対して指定された乗換回避許容コストを加算し、加算された経路コストを含む経路探索用ネットワークデータに基づいて経路探索を行う。
【０１１６】
そして、その候補経路を案内経路データに編集して地図データとともに端末装置２０に配信する。また、経路探索サーバ３０は、端末装置２０からの要求に従って要求された地図データを端末装置２０に配信する。
【０１１７】
次に、本発明の実施例にかかる経路探索サーバ３０における経路探索の動作手順を、図１１に基づいて説明する。図１１は、本発明の実施例にかかる経路探索サーバの動作手順を示すフローチャートである。
図１１に示す動作手順は、経路探索サーバ３０の制御手段３０１がＲＯＭに記憶された制御プログラムを実行することで実現される。
【０１１８】
先ず、ステップＳ９０１の処理で端末装置２０において図５に示す経路探索条件の入力画面に従って、出発地、目的地、出力順が入力され、ステップＳ９０２で乗換回避許容コストが入力される。入力された経路探索条件は経路探索サーバ３０に送信される。
経路探索サーバ３０は端末装置２０から経路探索要求を受信すると、ステップＳ９０３の処理においてこれを探索要求記憶手段３２に一時記憶する。
【０１１９】
ステップＳ９０３の処理で経路探索要求が探索要求記憶手段３２に記憶されると、ステップＳ９０４の処理おいて、経路探索要求においてルート表示順として「乗り換え回数が少ない順」が選択されているか否か判別する。ステップＳ９０４の判別処理において、「乗り換え回数が少ない順」が選択されていると判別されると通常の経路探索処理（乗換回避許容コストを加算しない経路探索処理）であり、ステップＳ９１１に進む。また、「乗り換え回数が少ない順」が選択されていないと判別されるとステップＳ９０５に進む。
【０１２０】
ステップＳ９０５では、経路探索要求においてルート表示順として「所要時間が短い順」が選択されているか否か判別する。ステップＳ９０５の判別処理において、「所要時間が短い順」が選択されていると判別されると、ステップＳ９０８に進み、「所要時間が短い順」が選択されていないと判別されるとステップＳ９０６に進む。
【０１２１】
ステップＳ９０６では、経路探索要求においてルート表示順として「運賃が安い順」が選択されているか否か判別する。ステップＳ９０６の判別処理において、「運賃が安い順」が選択されていると判別されると、ステップＳ９０９に進み、「運賃が安い順」が選択されていないと判別されるとステップＳ９０７に進む。
【０１２２】
ステップＳ９０７では、経路探索要求においてルート表示順として「歩きが少ない順」が選択されているか否か判別する。ステップＳ９０７の判別処理において、「歩きが少ない順」が選択されていると判別されると、ステップＳ９１０に進み、「歩きが少ない順」が選択されていないと判別されるとステップＳ９１１に進む。
【０１２３】
ネットワークデータ編集手段３６は、ルート表示順として「所要時間が短い順」を選択（乗換回避許容コストとして時間コストを指定）した経路探索要求を受信すると、ステップＳ９０８の処理において経路探索用ネットワークデータベース３５に含まれている乗り継ぎを含む経路コストに対して指定された時間コストを加算し、ステップＳ９１１に進む。
【０１２４】
また、ネットワークデータ編集手段３６は、ルート表示順として「運賃が安い順」を選択（乗換回避許容コストとして運賃コストを指定）した経路探索要求を受信すると、ステップＳ９０９の処理において経路探索用ネットワークデータベース３５に含まれている乗り継ぎを含む経路コストに対して指定された運賃コストを加算し、ステップＳ９１１に進む。
【０１２５】
さらに、ネットワークデータ編集手段３６は、ルート表示順として「歩きが少ない順」を選択（乗換回避許容コストとして徒歩距離コストを指定）した経路探索要求を受信すると、ステップＳ９１０の処理において経路探索用ネットワークデータベース３５に含まれている乗り継ぎを含む経路コストに対して指定された徒歩距離コストを加算し、ステップＳ９１１に進む。ステップＳ９０５〜ステップＳ９０７の判別処理の結果が何れもＮＯである場合は、通常の経路探索処理（乗換回避許容コストを加算しない経路探索処理）であり、ステップＳ９１１に進む。
【０１２６】
経路探索手段３３は、必要に応じてネットワークデータ編集手段３６によって乗換回避許容コストを加算した経路コストを含む経路探索用ネットワークデータに基づいてステップＳ９１１の処理において経路探索を行い、得られた候補経路を案内経路データ編集手段３７に送る。ステップＳ９１２の処理で案内経路データ編集手段３７は経路探索手段３３から送られた候補経路のデータを一時記憶する。
【０１２７】
なお、上記の経路探索手段３３による経路探索は一般の経路探索において用いられる移動手段指定（徒歩と交通機関併用）の経路探索であり、出発地から目的地まで道路ネットワーク、交通機関の運行ネットワークを辿る経路探索である。この経路探索において、複数の候補経路が探索されても、すべて案内経路データ編集手段３７に記憶しておく。
【０１２８】
ステップＳ９１２の処理で案内経路データが案内経路データ編集手段３７に記憶されると、ステップＳ９１３の処理おいて案内経路データ編集手段３７は一時記憶してある候補経路を指定された表示順序にソートして案内経路のデータを作成し、ステップＳ９１４の処理において作成した案内経路データを通信手段３１を介して端末装置２０に送信して処理を終了する。
【０１２９】
なお、上記実施例では、ステップＳ９０８ないしステップＳ９１０において三つの案内経路データの編集をそれぞれステップＳ９０５ないしステップＳ９０７の各判定処理に基づいて行っているが、これに限られることはなく、いずれか一つの案内経路データの編集のみをそれに対応する判定処理に基づいて行ってもよい。
【０１３０】
以上、詳細に説明したように、本発明にかかるナビゲーションシステムによれば交通機関の乗り継ぎ場所における乗り換えを回避するための許容範囲である乗換回避許容コストを指定するだけで、乗り継ぎを含む経路コストに対して指定した乗換回避許容コストを加算した経路コストに基づいて候補経路を探索することができ、乗り換える代わりに余計にかかる経路コストが利用者の許容範囲を満たし、かつ乗り換えを回避した案内経路の情報を得ることができるようになる。したがって、利用者はさらに自身の要求にあった所望の経路を得ることができるようにしたナビゲーションシステムを提供することができる。
【産業上の利用可能性】
【０１３１】
本実施例においては、端末装置と経路探索サーバとからなる通信型のナビゲーションシステムとして説明したが、本発明は通信型のナビゲーションシステムに限られることはなく、電車時刻表データや地図データの更新が管理可能であれば、端末装置と経路探索サーバが一体となったスタンドアロンで動作する携帯情報装置にデータをダウンロードして、携帯情報端末単独で経路案内を行う際に本発明を適用してもよい。
【０１３２】
また、本発明にかかるナビゲーションシステムは上記の構成に限られるものではなく、経路探索サーバは、歩行者に対するナビゲーション機能の他に自動車用のナビゲーション機能をあわせ持つサーバであってもよい。また、端末装置はＧＰＳ受信手段を持たない携帯電話であってもよい。ＧＰＳ受信手段を持たない携帯電話の場合、基地局に対する位置登録により通信エリアの位置情報を取得し、経路探索サーバはこの位置情報を携帯電話から受信して位置を判別すればよい。
【図面の簡単な説明】
【０１３３】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すシステム構成図である。
【図２】本発明の実施例におけるナビゲーションシステムの詳細な構成を示すブロック図である。
【図３】本発明の実施例にかかる乗換回避許容コストの種別と各コストの許容範囲の対応関係を説明するための図である。
【図４】本発明の実施例にかかる端末装置としての携帯電話の外観を示す図である。
【図５】本発明の実施例にかかる経路探索条件の入力画面の一例を示す画面構成図である。
【図６】本発明の実施例にかかる経路探索条件の入力画面のその他の例を示す画面構成図である。
【図７】本発明の実施例にかかる経路探索条件の入力画面のその他の例を示す画面構成図である。
【図８】道路ネットワークのデータの概念を示す模式図である。
【図９】交通ネットワークのデータの概念を示す模式図である。
【図１０】地図データの構成を示す模式図である。
【図１１】本発明の実施例にかかる経路探索サーバの動作手順を示すフローチャートである。
【符号の説明】
【０１３４】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２０１・・・制御手段
２１・・・・通信手段
２２・・・・ＧＰＳ受信手段
２３・・・・探索要求手段
２４・・・・案内経路データ記憶手段
２５・・・・表示手段
２５１・・・表示画面
２６・・・・操作入力手段
３０・・・・経路探索サーバ
３０１・・・制御手段
３１・・・・通信手段
３２・・・・探索要求記憶手段
３３・・・・経路探索手段
３４・・・・地図データベース
３５・・・・経路探索用ネットワークデータベース
３６・・・・ネットワークデータ編集手段
３７・・・・案内経路データ編集手段
【図１】
0004757847.tif 000002
【図２】
0004757847.tif 000003
【図３】
0004757847.tif 000004
【図４】
0004757847.tif 000005
【図５】
0004757847.tif 000006
【図６】
0004757847.tif 000007
【図７】
0004757847.tif 000008
【図８】
0004757847.tif 000009
【図９】
0004757847.tif 000010
【図１０】
0004757847.tif 000011
【図１１】
0004757847.tif 000012